The pre-NTS property is undecidable for context-free grammars

DOI10.1016/0020-0190(92)90082-7zbMath0779.68054OpenAlexW2093306186MaRDI QIDQ1208437

Louxin Zhang

Publication date: 16 May 1993

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

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Cites Work

• Unnamed Item
• Unnamed Item
• On weakly confluent monadic string-rewriting systems
• The equivalence and inclusion problems for NTS languages
• NTS languages are deterministic and congruential
• Thue systems as rewriting systems
• On deciding the confluence of a finite string-rewriting system on a given congruence class
• The equivalence of pre-NTS grammars is decidable

This page was built for publication: The pre-NTS property is undecidable for context-free grammars