Formations of Monoids, Congruences, and Formal Languages

Published in Volume XXV, Issue 2, 2015, pages 171-209, doi: 10.7561/SACS.2015.2.171

Authors: A. Ballester-Bolinches, E. Cosme-Llópez, R. Esteban-Romero, J.J.M.M. Rutten

Abstract

The main goal in this paper is to use a dual equivalence in automata theory started in [25] and developed in [3] to prove a general version of the Eilenberg-type theorem presented in [4]. Our principal results confirm the existence of a bijective correspondence between three concepts; formations of monoids, formations of languages and formations of congruences. The result does not require finiteness on monoids, nor regularity on languages nor finite index conditions on congruences. We relate our work to other results in the field and we include applications to non-r-disjunctive languages, Reiterman’s equational description of pseudovarieties and varieties of monoids

Full Text (PDF)

References

[1] J. Adémek, S. Milius, R. Myers, and H. Urbat. Generalized Eilenberg theorem I: Local varieties of languages. In Anca Muscholl, editor, Foundations of Software Science and Computation Structures, volume 8412 of Lecture Notes in Computer Science, pages 366–380, 2014. doi: 10.1007/978-3-642-54830-7_24.

[2] J. Almeida. Profinite semigroups and applications. In Structural theory of Automata, Semigroups, and Universal Algebra, pages 7–18, 2003. doi:10.1007/1-4020-3817-8_1.

[3] A. Ballester-Bolinches, E. Cosme-Llópez, and J. Rutten. The dual equivalence of equations and coequations for automata. Information and Computation, 244:49–75, 2015. doi:10.1016/j.ic.2015.08.001.

[4] A. Ballester-Bolinches, J.-É. Pin, and X. Soler-Escrivà. Formations of finite monoids and formal languages: Eilenberg’s theorem revisited. Forum Mathematicum, 26(6):1731–1761, 2012. doi:10.1515/ forum-2012-0055.

[5] G. Birkhoff. On the structure of abstract algebras. Mathematical Proceedings of the Cambridge Philosophical Society, 31:433–454, 1935.

[6] S. Eilenberg. Automata, languages and machines (Vol. B). Pure and applied mathematics. Academic Press, 1976.

[7] M. Gehrke. Stone duality and the recognisable languages over an algebra. In Kurz et al., editor, Algebra and Coalgebra in Computer Science (CALCO 2009), volume 5728 of Lecture Notes in Computer Science, pages 236–250, 2009. doi:10.1007/978-3-642-03741-2_17.

[8] M. Gehrke. Duality and recognition. In Murlak and Sankowski, edi- tors, Mathematical Foundations of Computer Science, volume 6907 of Lecture Notes in Computer Science, pages 3–18, 2011. doi:10.1007/ 978-3-642-22993-0_3.

[9] M. Gehrke, S. Grigorieff, and J.-É. Pin. Duality and equational theory of regular languages. In Proceedings of the International Colloquium on Automata, Languages, and Programming, ICALP, volume 5126 of Lecture Notes in Computer Science, pages 246–257, 2008. doi: 10.1007/978-3-540-70583-3_21.

[10] G. Grätzer. Universal algebra. Mathematics and Statistics. Springer, 2008.

[11] P. A. Grillet. Semigroups: an introduction to the structure theory. Marcel Dekker, Inc., New York, 1995.

[12] Y. Q. Guo, C. M. Reis, and G. Thierrin. Relatively f-disjunctive languages. Semigroup Forum, 37:289–299, 1988. doi:10.1007/ BF02573141.

[13] L. Henkin. A problem on inverse mapping systems. Proceedings of the American Mathematical Society, 1(2):224–225, 1950. doi:10.2307/ 2031926.

[14] S. P. Kogalovskiĭ. On Birkhoff’s theorem. Uspekhi Matematicheskikh Nauk, 20(5):206–207, 1965.

[15] Y. Liu, K. P. Shum, and Y. Q. Guo. Relatively regular languages and thin codes. European Journal of Combinatorics, 29:261–267, 2008. doi:10.1016/j.ejc.2006.09.002.

[16] H. Neumann. Varieties of groups. Ergebnisse der Mathematik und ihrer Grenzgebiete. Springer-Verlag, 1967.

[17] J.-É. Pin. Varieties of formal languages. North Oxford, London and Plenum, New York, 1986. Translation of Variétés de langages formels, Masson, 1984.

[18] J.-É. Pin. Profinite methods in automata theory. In Susanne Albers and Jean-Yves Marion, editors, 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science, pages 31–50, Freiburg, Germany, February 2009. IBFI Schloss Dagstuhl. URL: https://hal.inria.fr/inria-00359677.

[19] Jean-Eric Pin. Syntactic semigroups. In Grzegorz Rozenberg and Arto Salomaa, editors, Handbook of Formal Languages, pages 679–746. Springer, 1997. doi:10.1007/978-3-642-59136-5_10.

[20] N. Pippenger. Regular languages and stone duality. Theory of Computing Systems, 30(2):121–134, 1997. doi:10.1007/BF02679444.

[21] C. M. Reis and H. J. Shyr. Some properties of disjunctive languages on a free monoid. Information and Control, 37(3):334–344, 1978. doi: 10.1016/S0019-9958(78)90578-8.

[22] J. Reiterman. The Birkhoff theorem for finite algebras. Algebra universalis, 14(1):1–10, 1982. doi:10.1007/BF02483902.

[23] J. Rhodes and B. Steinberg. The q-theory of finite semigroups. Springer Monographs in Mathematics. Springer, New York, 2009. doi:10.1007/ b104443.

[24] L. Ribes and P. Zaleskiĭ. Profinite groups, volume 40 of Ergebnisse der Mathematik und ihrer Grenzgebiete. Springer, Berlin-Heidelberg-New York, 2000. doi:10.1007/978-3-642-01642-4_2.

[25] J.J.M.M. Rutten, A. Ballester-Bolinches, and E. Cosme-Llópez. Varieties and covarieties of languages (preliminary version). In D. Kozen and M. Mislove, editors, Proceedings of MFPS XXIX, volume 298 of Electronic Notes in Theoretical Computer Science, pages 7–28, 2013. doi:10.1016/j.entcs.2013.09.005.

[26] L. A. Shemetkov and A. N. Skiba. Formations of algebraic systems. Modern Algebra, Moscow, 1989. In Russian, with an English summary.

[27] H. Straubing. Families of recognizable sets corresponding to certain varieties of finite monoids. Journal of Pure and Applied Algebra, 15(3):305– 318, 1979. doi:10.1016/0022-4049(79)90024-0.

[28] D. Thérien. Classification of regular languages with congruences. PhD thesis, Department of Computer Science, University of Waterloo, 1980. Waterloo, Ontario, Canada.

[29] D. Thérien. Classification of finite monoids: the language approach. Theoretical Computer Science, 14(2):195–208, 1981. doi:10.1016/0304-3975(81)90057-8.

[30] D. Zhang, Y. Guo, and K. P. Shum. On some decompositions of r- disjunctive languages. Bulletin of the Malaysian Mathematical Sciences Society, 2(3):727–746, 2014.

Bibtex

@article{sacscuza:ballester-bolinches2015fomcafl,
  title={Formations of Monoids, Congruences, and Formal Languages},
  author={A. Ballester-Bolinches and E. Cosme-Llópez and R. Esteban-Romero and J.J.M.M. Rutten},
  journal={Scientific Annals of Computer Science},
  volume={25},
  number={2},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2015},
  pages={171--209},
  doi={10.7561/SACS.2015.2.171},
  publisher={``A.I. Cuza'' University Press}
}