The equivalence problem for deterministic TOL-systems is undecidable

DOI10.1016/0020-0190(72)90039-7zbMath0267.68033OpenAlexW2057195216MaRDI QIDQ2562694

Grzegorz Rozenberg

Publication date: 1972

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(72)90039-7

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Thue and Post systems, etc. (03D03)

Related Items (14)

Extension of tabled 0L-systems and languages ⋮ Similarity in DTOL and related problems† ⋮ The decidability of the DOL-DTOL equivalence problem ⋮ The language equivalence problem for HD0L systems having D0L growths ⋮ A limit theorem for set of subwords in deterministic TOL laguages ⋮ Doubly deterministic tabled OL systems ⋮ Classes of formal grammars ⋮ The equivalence problem for languages defined by transductions on D0L languages ⋮ Concentration dependent OL systems ⋮ 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 ⋮ Characterization of unary developmental languages ⋮ DOL sequences ⋮ The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids

Cites Work

• A variant of a recursively unsolvable problem
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The equivalence problem for deterministic TOL-systems is undecidable