Regular languages are Church-Rosser congruential

DOI10.1145/2808227MaRDI QIDQ5895070zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/1202.1148, https://dspace.lboro.ac.uk/2134/31954

zbMATH Keywords

regular languagesemigroupstring rewritingChurch-Rosser systemlocal divisor

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Thue and Post systems, etc. (03D03) Semigroups in automata theory, linguistics, etc. (20M35)

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.

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

Cited in

(5)

• scientific article; zbMATH DE number 2087236 (Why is no real title available?)
• Star-free languages are Church-Rosser congruential
• Regular languages are Church-Rosser congruential
• Parikh-reducing Church-Rosser representations for some classes of regular languages
• An almost-confluent congruential language which is not Church-Rosser congruential

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)