WHEN CHURCH-ROSSER BECOMES CONTEXT FREE
From MaRDI portal
Publication:3401476
DOI10.1142/S0129054107005339zbMath1183.68344MaRDI QIDQ3401476
Martin Kutrib, Andreas Malcher
Publication date: 29 January 2010
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
context-free languages; arithmetic hierarchy; Church-Rosser languages; strongly context-free languages
68Q45: Formal languages and automata
Related Items
Left-to-right regular languages and two-way restarting automata, ON THE DESCRIPTIONAL COMPLEXITY OF THE WINDOW SIZE FOR DELETING RESTARTING AUTOMATA, On the Descriptional Complexity of the Window Size for Deterministic Restarting Automata, Reversible Limited Automata, When input-driven pushdown automata meet reversiblity
Cites Work
- Unnamed Item
- Unnamed Item
- Complexity of certain decision problems about congruential languages
- Growing context-sensitive languages and Church-Rosser languages
- The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
- Une généralisation des ensembles de Dyck
- Church-Rosser Thue systems and formal languages
- Recursive Unsolvability of a problem of Thue