On the decidability of homomorphism equivalence for languages
From MaRDI portal
Publication:1251076
DOI10.1016/0022-0000(78)90002-8zbMath0389.68042OpenAlexW2071271929MaRDI QIDQ1251076
Publication date: 1978
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(78)90002-8
Related Items
Some decision problems concerning semilinearity and commutation., Systèmes entiers d'équations sur un alphabet fini et conjecture d'Ehrenfeucht, The equivalence of finite valued transducers (on HDT0L languages) is decidable, Balance of many-valued transductions and equivalence problems, Equivalence problem of mappings relative to languages, Unnamed Item, Every finitely generated submonoid of a free monoid has a finite Malcev's presentation, On the equivalence problem for deterministic multitape automata and transducers, Polynomial size test sets for context-free languages, Test sets and checking words for homomorphism equivalence, New techniques for proving the decidability of equivalence problem, 2DST mappings of languages and related problems, On some transducer equivalence problems for families of languages, Multiplicities: A deterministic view of nondeterminism, Efficient constructions of test sets for regular and context-free languages, Equations over finite sets of words and equivalence problems in automata theory, A note on undercover relation, HDTOL matching of computations of multitape automata, Some decidability results about regular and pushdown translations, A homomorphic characterization of time and space complexity classes of languages†, Unnamed Item, A simple undecidable problem: Existential agreement of inverses of two morphisms on a regular language, Synchronizable deterministic pushdown automata and the decidability of their equivalence, Finite transducers and rational transductions, Checking sets, test sets, rich languages and commutatively closed languages, Dominoes over a free monoid, Systems of equations over a free monoid and Ehrenfeucht's conjecture, On the equivalence of some transductions involving letter to letter morphisms on regular languages, The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids, Inverse morphic equivalence on languages, On test sets for checking morphism equivalence on languages with fair distribution of letters, Test sets for morphisms with bounded delay, On the equivalence problem of compositions of morphisms and inverse morphisms on context-free languages
Cites Work
