The decidability of the DOL-DTOL equivalence problem

DOI10.1016/0022-0000(81)90020-9zbMath0491.68048OpenAlexW1983745639MaRDI QIDQ1167540

Keijo Ruohonen

Publication date: 1981

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(81)90020-9

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Word problems, etc. in computability and recursion theory (03D40)

Related Items (6)

The equivalence problem for DF0L languages and power series. ⋮ On generalized DT0L systems and their fixed points ⋮ Lindenmayer Systems ⋮ The language equivalence problem for HD0L systems having D0L growths ⋮ On D0L power series ⋮ On morphically generated formal power series

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on language equations involving morphisms
• The decidability of the FOL-DOL equivalence problem
• Elementary homomorphisms and a solution of the DOL sequence equivalence problem
• The unsolvability of the equality problem for sentential forms of context-free grammars
• Direct proofs of the undecidability of the equivalence problem for sentential forms of linear context-free grammars and the equivalence problem for OL systems
• On sentential forms of context-free grammars
• The equivalence problem for deterministic TOL-systems is undecidable
• Description of developmental languages using recurrence systems
• The decidability of the equivalence problem for DOL-systems
• On the decidability of the OL-DOL equivalence problem
• On the decidability of some equivalence problems for DOL-systems

This page was built for publication: The decidability of the DOL-DTOL equivalence problem