Star-free languages are Church-Rosser congruential
From MaRDI portal
Publication:714818
DOI10.1016/J.TCS.2012.01.028zbMATH Open1279.68147arXiv1111.4300OpenAlexW1975372170MaRDI QIDQ714818FDOQ714818
Authors: Volker Diekert, Manfred Kufleitner, Pascal Weil 
Publication date: 11 October 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1111.4300
Recommendations
Cites Work
- Title not available (Why is that?)
- An application of games to the completeness problem for formalized theories
- On finite monoids having only trivial subgroups
- The \(\mathfrak q\)-theory of finite semigroups.
- Title not available (Why is that?)
- Von Neumann regularity in Jordan triple systems
- Pure future local temporal logics are expressively complete for Mazurkiewicz traces
- Church-Rosser Thue systems and formal languages
- First-order definable languages
- Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines
- The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
- The Krohn-Rhodes theorem and local divisors
- Title not available (Why is that?)
Cited In (9)
- Representations of relatively free profinite semigroups, irreducibility, and order primitivity
- Title not available (Why is that?)
- A survey on the local divisor technique
- Regular languages are Church-Rosser congruential
- Characterizing classes of regular languages using prefix codes of bounded synchronization delay
- Parikh-reducing Church-Rosser representations for some classes of regular languages
- Locally countable pseudovarieties
- An almost-confluent congruential language which is not Church-Rosser congruential
- On the irreducibility of pseudovarieties of semigroups.
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)
