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 languages are of this form. This paper solves the conjecture affirmatively by actually proving a more general result.
A version with full proofs can be found on arXiv:1202.1148 [4].
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Book, R., Otto, F.: String-Rewriting Systems. Springer (1993)
Buntrock, G., Otto, F.: Growing context-sensitive languages and Church-Rosser languages. Information and Computation 141, 1–36 (1998)
Diekert, V., Gastin, P.: First-order definable languages. In: Logic and Automata: History and Perspectives. Texts in Logic and Games, pp. 261–306. Amsterdam University Press (2008)
Diekert, V., Kufleitner, M., Reinhardt, K., Walter, T.: Regular languages are Church-Rosser congruential. ArXiv e-prints, arXiv:1202.1148 (February 2012)
Diekert, V., Kufleitner, M., Steinberg, B.: The Krohn-Rhodes Theorem and Local Divisors. ArXiv e-prints, arXiv:1111.1585 (November 2011)
Diekert, V., Kufleitner, M., Weil, P.: Star-free languages are Church-Rosser congruential. Theoretical Computer Science (2012), doi:10.1016/j.tcs.2012.01.028
Jantzen, M.: Confluent String Rewriting. EATCS Monographs on Theoretical Computer Science, vol. 14. Springer (1988)
Lothaire, M.: Combinatorics on Words. Encyclopedia of Mathematics and its Applications, vol. 17. Addison-Wesley (1983)
McNaughton, R., Narendran, P., Otto, F.: Church-Rosser Thue systems and formal languages. J. ACM 35(2), 324–344 (1988)
Narendran, P.: Church-Rosser and related Thue systems. Doctoral dissertation, Dept. of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY, USA (1984)
Niemann, G.: Church-Rosser Languages and Related Classes. Kassel University Press, PhD thesis (2002)
Niemann, G., Otto, F.: The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages. Inf. Comput. 197, 1–21 (2005)
Niemann, G., Waldmann, J.: Some Regular Languages That Are Church-Rosser Congruential. In: Kuich, W., Rozenberg, G., Salomaa, A. (eds.) DLT 2001. LNCS, vol. 2295, pp. 330–339. Springer, Heidelberg (2002)
Reinhardt, K., Thérien, D.: Some more regular languages that are Church Rosser congruential. In: 13. Theorietag, Automaten und Formale Sprachen, Herrsching, Germany, pp. 97–103 (2003)
Woinowski, J.R.: Church-Rosser Languages and Their Application to Parsing Problems. PhD Thesis, TU Darmstadt (2001)
Woinowski, J.R.: The context-splittable normal form for Church-Rosser language systems. Inf. Comput. 183, 245–274 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Diekert, V., Kufleitner, M., Reinhardt, K., Walter, T. (2012). Regular Languages Are Church-Rosser Congruential. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds) Automata, Languages, and Programming. ICALP 2012. Lecture Notes in Computer Science, vol 7392. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31585-5_19
Download citation
DOI: https://doi.org/10.1007/978-3-642-31585-5_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31584-8
Online ISBN: 978-3-642-31585-5
eBook Packages: Computer ScienceComputer Science (R0)