WHEN CHURCH-ROSSER BECOMES CONTEXT FREE

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)

zbMATH Keywords

context-free languagesarithmetic hierarchyChurch-Rosser languagesstrongly context-free languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (5)

On the Descriptional Complexity of the Window Size for Deterministic Restarting Automata ⋮ Left-to-right regular languages and two-way restarting automata ⋮ Reversible Limited Automata ⋮ When input-driven pushdown automata meet reversiblity ⋮ ON THE DESCRIPTIONAL COMPLEXITY OF THE WINDOW SIZE FOR DELETING RESTARTING AUTOMATA

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

This page was built for publication: WHEN CHURCH-ROSSER BECOMES CONTEXT FREE