The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
From MaRDI portal
Publication:5544289
DOI10.1145/321466.321473zbMath0162.02302MaRDI 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
Superlinear deterministic top-down tree transducers, The Equivalence Problem of Finite Substitutions on ab*c, with Applications, The unsolvability of some Petri net language problems, The decidability of equivalence for deterministic finite transducers, The equivalence problem of multitape finite automata, New techniques for proving the decidability of equivalence problem, Deciding equivalence of top-down XML transformations in polynomial time, On the equivalence of some transductions involving letter to letter morphisms on regular languages, The equivalence of finite valued transducers (on HDT0L languages) is decidable, Balance of many-valued transductions and equivalence problems, Probabilistic automata, An automaton generating series of graphs, Finite state relational programs, Analyse und Synthese von asynchronen ND-Automaten, Single-valued a-transducers, Some decision problems concerning sequential transducers and checking automata, The undecidability of some equivalence problems concerning ngsm's and finite substitutions, On the lengths of values in a finite transducer, A simple undecidable problem: Existential agreement of inverses of two morphisms on a regular language, Theory of formal grammars, The unsolvability of the equality problem for sentential forms of context-free grammars, Solvability of equivalence problem for program machines, On the Decidability of the Equivalence for k-Valued Transducers, Unnamed Item, On some transducer equivalence problems for families of languages, Restricted one-counter machines with undecidable universe problems, A note on finite-valued and finitely ambiguous transducers, Transductions and the parallel generation of languages†, New problems complete for nondeterministic log space, Cardinality problems of compositions of morphisms and inverse morphisms
