Direct proofs of the undecidability of the equivalence problem for sentential forms of linear context-free grammars and the equivalence problem for OL systems

DOI10.1016/0020-0190(72)90018-XzbMath0249.68029MaRDI QIDQ2556750

Grzegorz Rozenberg

Publication date: 1972

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (5)

On equality of multiplicity sets of regular languages ⋮ Grammars with valuations - a discrete model for self-organization of biopolymers ⋮ The decidability of the DOL-DTOL equivalence problem ⋮ Description of developmental languages using recurrence systems ⋮ Some decidability problems of sentential formst †

Cites Work

• The equivalence problem for deterministic TOL-systems is undecidable
• On 0L-Languages
• Unnamed Item
• Unnamed Item

This page was built for publication: Direct proofs of the undecidability of the equivalence problem for sentential forms of linear context-free grammars and the equivalence problem for OL systems