When Church-Rosser becomes context free

DOI10.1142/S0129054107005339MaRDI QIDQ3401476zbMATH OpenFDO

Authors Martin Kutrib, Andreas Malcher

Publication date 29 January 2010

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054107005339

zbMATH Keywords

arithmetic hierarchyChurch-Rosser languagescontext-free languagesstrongly context-free languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
• scientific article; zbMATH DE number 1189300
• Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages
• scientific article; zbMATH DE number 2086618
• Church-Rosser systems with respect to formal languages

Cites work

• Church-Rosser Thue systems and formal languages
• Complexity of certain decision problems about congruential languages
• Growing context-sensitive languages and Church-Rosser languages
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Recursive unsolvability of a problem of Thue
• The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
• Une généralisation des ensembles de Dyck

Cited in

(17)

• McNaughton families of languages.
• The context-splittable normal form for Church-Rosser language systems.
• The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
• An almost-confluent congruential language which is not Church-Rosser congruential
• scientific article; zbMATH DE number 1722715 (Why is no real title available?)
• On the Descriptional Complexity of the Window Size for Deterministic Restarting Automata
• Reversible limited automata
• When input-driven pushdown automata meet reversiblity
• Church–Rosser Made Easy
• scientific article; zbMATH DE number 1189300 (Why is no real title available?)
• scientific article; zbMATH DE number 2050944 (Why is no real title available?)
• scientific article; zbMATH DE number 2080229 (Why is no real title available?)
• scientific article; zbMATH DE number 2086618 (Why is no real title available?)
• scientific article; zbMATH DE number 2087237 (Why is no real title available?)
• Left-to-right regular languages and two-way restarting automata
• On the descriptional complexity of the window size for deleting restarting automata
• Star-free languages are Church-Rosser congruential

This page was built for publication: When Church-Rosser becomes context free

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3401476)