Regular languages are Church-Rosser congruential
From MaRDI portal
Publication:5895070
DOI10.1145/2808227zbMATH Open1426.68142arXiv1202.1148OpenAlexW2175851206MaRDI QIDQ5895070FDOQ5895070
Authors: Volker Diekert, Manfred Kufleitner, Klaus Reinhardt, Tobias Walter 
Publication date: 2 August 2018
Published in: Journal of the ACM (Search for Journal in Brave)
Abstract: This paper proves a long standing conjecture in formal language theory. It shows that all regular languages are Church-Rosser congruential. The class of Church-Rosser congruential languages was introduced by McNaughton, Narendran, and Otto in 1988. A language L is Church-Rosser congruential, if there exists a finite confluent, and length-reducing semi-Thue system S such that L is a finite union of congruence classes modulo S. It was known that there are deterministic linear context-free languages which are not Church-Rosser congruential, but on the other hand it was strongly believed that all regular language are of this form. Actually, this paper proves a more general result.
Full work available at URL: https://arxiv.org/abs/1202.1148
Recommendations
- Regular languages are Church-Rosser congruential
- Parikh-reducing Church-Rosser representations for some classes of regular languages
- scientific article; zbMATH DE number 2087236
- An almost-confluent congruential language which is not Church-Rosser congruential
- Star-free languages are Church-Rosser congruential
Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Thue and Post systems, etc. (03D03) Semigroups in automata theory, linguistics, etc. (20M35)
Cited In (5)
This page was built for publication: Regular languages are Church-Rosser congruential
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5895070)
