Star-free languages are Church-Rosser congruential. (English) Zbl 1279.68147
Summary: 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.
MSC:
| 68Q45 | Formal languages and automata |
Keywords:
string rewriting; Church-Rosser system; star-free language; aperiodic monoid; local divisorReferences:
| [1] | Clifford, A. H.; Preston, G. B., The Algebraic Theory of Semigroups, Volume 1,2 (1967), American Mathematical Society, p. 1961 · Zbl 0178.01203 |
| [2] | Diekert, V.; Gastin, P., Pure future local temporal logics are expressively complete for Mazurkiewicz traces, Information and Computation, 204, 1597-1619 (2006), Conference version in LATIN 2004, LNCS 2976, 170-182, 2004 · Zbl 1113.03016 |
| [3] | Diekert, V.; Gastin, P., First-order definable languages, (Logic and Automata: History and Perspectives. Logic and Automata: History and Perspectives, Texts in Logic and Games (2008), Amsterdam University Press), 261-306 · Zbl 1234.03024 |
| [4] | V. Diekert, M. Kufleitner, B. Steinberg, The Krohn-Rhodes Theorem and Local Divisors. ArXiv e-prints, Nov. 2011.; V. Diekert, M. Kufleitner, B. Steinberg, The Krohn-Rhodes Theorem and Local Divisors. ArXiv e-prints, Nov. 2011. · Zbl 1263.68116 |
| [5] | Ehrenfeucht, A., An application of games to the completeness problem for formalized theories, Fundamenta Mathematicae, 49, 129-141 (1961) · Zbl 0096.24303 |
| [6] | Fernández López, A.; Tocón Barroso, M., The local algebras of an associative algebra and their applications, (Misra, J., Applicable Mathematics in the Golden Age (2002), Narosa), 254-275 |
| [7] | J.A.W. Kamp, Tense logic and the theory of linear order. Ph.D. Thesis, University of California, Los Angeles (California), 1968.; J.A.W. Kamp, Tense logic and the theory of linear order. Ph.D. Thesis, University of California, Los Angeles (California), 1968. |
| [8] | Krohn, K.; Rhodes, J., Algebraic theory of machines. I: prime decomposition theorem for finite semigroups and machines, Transactions of the American Mathematical Society, 116, 450-464 (1965) · Zbl 0148.01002 |
| [9] | McNaughton, R.; Narendran, P.; Otto, F., Church-Rosser Thue systems and formal languages, Journal of the ACM, 35, 2, 324-344 (1988) · Zbl 0652.68093 |
| [10] | McNaughton, R.; Papert, S., Counter-Free Automata (1971), The MIT Press · Zbl 0232.94024 |
| [11] | K. Meyberg, Lectures on algebras and triple systems. Technical report, University of Virginia, Charlottesville, 1972.; K. Meyberg, Lectures on algebras and triple systems. Technical report, University of Virginia, Charlottesville, 1972. · Zbl 0253.17017 |
| [12] | Niemann, G., Church-Rosser Languages and Related Classes (2002), Kassel University Press |
| [13] | Niemann, G.; Otto, F., The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages, Information and Computation, 197, 1-21 (2005) · Zbl 1075.68046 |
| [14] | Niemann, G.; Waldmann, J., Some regular languages that are Church-Rosser congruential, (Revised Papers from the 5th International Conference on Developments in Language Theory. Revised Papers from the 5th International Conference on Developments in Language Theory, DLT’01 (2002), Springer-Verlag: Springer-Verlag London, UK), 330-339 · Zbl 1073.68049 |
| [15] | K. Reinhardt, D. Thérien, Some more regular languages that are Church Rosser congruential, in: 13. Theorietag, Automaten und Formale Sprachen, Herrsching, 2003, pp. 97-103.; K. Reinhardt, D. Thérien, Some more regular languages that are Church Rosser congruential, in: 13. Theorietag, Automaten und Formale Sprachen, Herrsching, 2003, pp. 97-103. |
| [16] | Rhodes, J.; Steinberg, B., The \(q\)-theory of finite semigroups, (Springer Monographs in Mathematics (2009), Springer) · Zbl 1186.20043 |
| [17] | Schützenberger, M. P., On finite monoids having only trivial subgroups, Information and Control, 8, 190-194 (1965) · Zbl 0131.02001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
