The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
From MaRDI portal
Publication:5544289
DOI10.1145/321466.321473zbMath0162.02302OpenAlexW1966515438MaRDI QIDQ5544289
Publication date: 1968
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/321466.321473
Related Items (54)
A note on finite-valued and finitely ambiguous transducers ⋮ Transductions and the parallel generation of languages† ⋮ The equivalence of finite valued transducers (on HDT0L languages) is decidable ⋮ Decision Problems of Tree Transducers with Origin ⋮ P systems with protein rules ⋮ Multi-sequential Word Relations ⋮ Balance of many-valued transductions and equivalence problems ⋮ The equivalence problem for deterministic MSO tree transducers is decidable ⋮ Decision problems of tree transducers with origin ⋮ Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines ⋮ Minimality and deadlockness of multitape automata ⋮ The unsolvability of some Petri net language problems ⋮ Visibly pushdown transducers ⋮ On the decidability of the valuedness problem for two-way finite transducers ⋮ Equivalence Checking Problem for Finite State Transducers over Semigroups ⋮ On the containment and equivalence problems for two-way transducers ⋮ Probabilistic automata ⋮ New techniques for proving the decidability of equivalence problem ⋮ An automaton generating series of graphs ⋮ On the Decidability of the Equivalence for k-Valued Transducers ⋮ Finite state relational programs ⋮ The Equivalence Problem of Finite Substitutions on ab*c, with Applications ⋮ On some transducer equivalence problems for families of languages ⋮ Superlinear deterministic top-down tree transducers ⋮ One-way resynchronizability of word transducers ⋮ Multi-Sequential Word Relations ⋮ Nondeterministic Streaming String Transducers ⋮ New problems complete for nondeterministic log space ⋮ The unsolvability of the equality problem for sentential forms of context-free grammars ⋮ Solvability of equivalence problem for program machines ⋮ Restricted one-counter machines with undecidable universe problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Analyse und Synthese von asynchronen ND-Automaten ⋮ Single-valued a-transducers ⋮ On the Containment and Equivalence Problems for GSMs, Transducers, and Linear CFGs ⋮ A Survey on Decidable Equivalence Problems for Tree Transducers ⋮ Some decision problems concerning sequential transducers and checking automata ⋮ Unnamed Item ⋮ Extended symbolic finite automata and transducers ⋮ Deciding equivalence of top-down XML transformations in polynomial time ⋮ The undecidability of some equivalence problems concerning ngsm's and finite substitutions ⋮ The decidability of equivalence for deterministic finite transducers ⋮ Origin-equivalence of two-way word transducers is in PSPACE ⋮ On Synthesis of Resynchronizers for Transducers ⋮ A simple undecidable problem: Existential agreement of inverses of two morphisms on a regular language ⋮ Cardinality problems of compositions of morphisms and inverse morphisms ⋮ Copyful Streaming String Transducers ⋮ Finite transducers and rational transductions ⋮ Theory of formal grammars ⋮ On the equivalence of some transductions involving letter to letter morphisms on regular languages ⋮ A Pattern Logic for Automata with Outputs ⋮ The equivalence problem of multitape finite automata ⋮ On the lengths of values in a finite transducer
This page was built for publication: The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
