A simple undecidable problem: Existential agreement of inverses of two morphisms on a regular language

DOI10.1016/0022-0000(86)90032-2zbMath0615.68051OpenAlexW2010411091MaRDI QIDQ1820585

Yael Maon, Juhani Karhumäki

Publication date: 1986

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(86)90032-2

zbMATH Keywords

morphismsfinite language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Balance of many-valued transductions and equivalence problems, A note on decidability questions on presentations of word semigroups, On some transducer equivalence problems for families of languages, Unnamed Item, On the equivalence of some transductions involving letter to letter morphisms on regular languages

Cites Work

• Inverse morphic equivalence on languages
• On the decidability of homomorphism equivalence for languages
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item