The Unsolvability of the Equivalence Problem for $\varepsilon $-Free NGSM’s with Unary Input (Output) Alphabet and Applications
From MaRDI portal
Publication:4167584
DOI10.1137/0207042zbMath0386.68054OpenAlexW2170953202MaRDI QIDQ4167584
Publication date: 1978
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0207042
Formal languages and automata (68Q45) Directed graphs (digraphs), tournaments (05C20) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)
Related Items (40)
A note on finite-valued and finitely ambiguous transducers ⋮ A note on the equivalence problem of rational formal power series ⋮ The equivalence of finite valued transducers (on HDT0L languages) is decidable ⋮ Separability of rational relations in \(A^* \times \mathbb N^m\) by recognizable relations is decidable ⋮ Equivalence of Finite-Valued Symbolic Finite Transducers ⋮ Decision problems of tree transducers with origin ⋮ Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines ⋮ On the decidability of some problems about rational subsets of free partially commutative monoids ⋮ Cyclic automata ⋮ The unsolvability of some Petri net language problems ⋮ Equivalence Checking Problem for Finite State Transducers over Semigroups ⋮ Identities and transductions ⋮ On the containment and equivalence problems for two-way transducers ⋮ On the structure of linear apex NLC graph grammars ⋮ New techniques for proving the decidability of equivalence problem ⋮ On the Decidability of the Equivalence for k-Valued Transducers ⋮ The Equivalence Problem of Finite Substitutions on ab*c, with Applications ⋮ On some transducer equivalence problems for families of languages ⋮ Decidability problems for unary output sequential transducers ⋮ One-way resynchronizability of word transducers ⋮ On partially blind multihead finite automata. ⋮ Alphabetic and synchronized tree transducers ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the Containment and Equivalence Problems for GSMs, Transducers, and Linear CFGs ⋮ Some decision problems concerning sequential transducers and checking automata ⋮ Extended symbolic finite automata and transducers ⋮ On the Decidability of the Equivalence for a Certain Class of Transducers ⋮ The undecidability of some equivalence problems concerning ngsm's and finite substitutions ⋮ On Synthesis of Resynchronizers for Transducers ⋮ Unnamed Item ⋮ Finite transducers and rational transductions ⋮ SOME DECISION QUESTIONS CONCERNING THE TIME COMPLEXITY OF LANGUAGE ACCEPTORS ⋮ Decision problems among the main subfamilies of rational relations ⋮ On the equivalence of some transductions involving letter to letter morphisms on regular languages ⋮ Algorithms for determining the smallest number of nonterminals (states) sufficient for generating (accepting) a regular language \(R \) with \(R_{1}\subseteq R\subseteq R_{2}\) for given regular languages \(R_{1},R_{2}\). ⋮ On the power of synchronization in parallel computations ⋮ On the lengths of values in a finite transducer
This page was built for publication: The Unsolvability of the Equivalence Problem for $\varepsilon $-Free NGSM’s with Unary Input (Output) Alphabet and Applications
