Star-free languages are Church-Rosser congruential

DOI10.1016/J.TCS.2012.01.028zbMATH Open1279.68147OpenAlexW1975372170MaRDI QIDQ714818FDOQ714818

Authors Volker Diekert, Manfred Kufleitner, Pascal Weil

Publication date 11 October 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.4300

zbMATH Keywords

string rewritingaperiodic monoidChurch-Rosser systemlocal divisorstar-free language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: The class of Church-Rosser congruential languages has been introduced by McNaughton, Narendran, and Otto in 1988. A language L is Church-Rosser congruential (belongs to CRCL), if there is a finite, confluent, and length-reducing semi-Thue system S such that L is a finite union of congruence classes modulo S. To date, it is still open whether every regular language is in CRCL. In this paper, we show that every star-free language is in CRCL. In fact, we prove a stronger statement: For every star-free language L there exists a finite, confluent, and subword-reducing semi-Thue system S such that the total number of congruence classes modulo S is finite and such that L is a union of congruence classes modulo S. The construction turns out to be effective.

Recommendations

• scientific article; zbMATH DE number 2087236
• Regular languages are Church-Rosser congruential
• Regular languages are Church-Rosser congruential
• Parikh-reducing Church-Rosser representations for some classes of regular languages
• When Church-Rosser becomes context free

Cites work

• scientific article; zbMATH DE number 2087236 (Why is no real title available?)
• scientific article; zbMATH DE number 3284302 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines
• An application of games to the completeness problem for formalized theories
• Church-Rosser Thue systems and formal languages
• First-order definable languages
• On finite monoids having only trivial subgroups
• Pure future local temporal logics are expressively complete for Mazurkiewicz traces
• The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
• The Krohn-Rhodes theorem and local divisors
• The \(\mathfrak q\)-theory of finite semigroups.
• Von Neumann regularity in Jordan triple systems

Cited in

(10)

• An almost-confluent congruential language which is not Church-Rosser congruential
• On the irreducibility of pseudovarieties of semigroups.
• Representations of relatively free profinite semigroups, irreducibility, and order primitivity
• A survey on the local divisor technique
• Regular languages are Church-Rosser congruential
• Regular languages are Church-Rosser congruential
• Parikh-reducing Church-Rosser representations for some classes of regular languages
• Locally countable pseudovarieties
• Characterizing classes of regular languages using prefix codes of bounded synchronization delay
• scientific article; zbMATH DE number 2087236 (Why is no real title available?)

This page was built for publication: Star-free languages are Church-Rosser congruential

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