Some results on 𝒞-varieties
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 39 (2005) no. 1, p. 239-262

In an earlier paper, the second author generalized Eilenberg’s variety theory by establishing a basic correspondence between certain classes of monoid morphisms and families of regular languages. We extend this theory in several directions. First, we prove a version of Reiterman’s theorem concerning the definition of varieties by identities, and illustrate this result by describing the identities associated with languages of the form (a 1 a 2 a k ) + , where a 1 ,...,a k are distinct letters. Next, we generalize the notions of Mal’cev product, positive varieties, and polynomial closure. Our results not only extend those already known, but permit a unified approach of different cases that previously required separate treatment.

@article{ITA_2005__39_1_239_0,
     author = {Pin, Jean-\'Eric and Straubing, Howard},
     title = {Some results on $\mathcal {C}$-varieties},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     publisher = {EDP-Sciences},
     volume = {39},
     number = {1},
     year = {2005},
     pages = {239-262},
     doi = {10.1051/ita:2005014},
     zbl = {1083.20059},
     mrnumber = {2132590},
     language = {en},
     url = {http://www.numdam.org/item/ITA_2005__39_1_239_0}
}
Pin, Jean-Éric; Straubing, Howard. Some results on $\mathcal {C}$-varieties. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 39 (2005) no. 1, pp. 239-262. doi : 10.1051/ita:2005014. http://www.numdam.org/item/ITA_2005__39_1_239_0/

[1] D.A.M. Barrington, K.J. Compton, H. Straubing and D. Thérien, Regular languages in nc 1 . J. Comput. Syst. Sci. 44 (1992) 478-499. | Zbl 0757.68057

[2] M. Branco, Varieties of languages, in Semigroups, Algorithms, Automata and Languages, edited by G.M.S. Gomes, J.-É. Pin and P. Silva. World Scientific (2002) 91-132. | Zbl 1031.20052

[3] S. Eilenberg, Automata, languages, and machines. Vol. B. Academic Press, Harcourt Brace Jovanovich Publishers, New York, (1976). With two chapters (“Depth decomposition theorem” and “Complexity of semigroups and morphisms”) by Bret Tilson. Pure Appl. Math. 59. | Zbl 0359.94067

[4] S. Eilenberg and M.-P. Schützenberger, On pseudovarieties. Adv. Math. 19 (1976) 413-418. | Zbl 0351.20035

[5] M. Kunc, Equational description of pseudovarieties of homomorphisms. Theor. Inform. Appl. 37 (2003) 243-254. | Numdam | Zbl 1045.20049

[6] D. Perrin and J.-É. Pin, Infinite Words. Pure and Applied Mathematics 141 2004. | Zbl 1094.68052

[7] J.-É. Pin, A variety theorem without complementation. Russian Math. (Izvestija vuzov. Matematika) 39 (1995) 80-90.

[8] J.-É. Pin, Syntactic semigroups, in Handbook of formal languages, edited by G. Rozenberg and A. Salomaa. Springer-Verlag 1 (1997) 679-746.

[9] J.-É. Pin, Algebraic tools for the concatenation product. Theoret. Comput. Sci. 292 (2003) 317-342. | Zbl 1064.68057

[10] J.-É. Pin, H. Straubing and D. Thérien, Some results on the generalized star-height problem. Inform. Comput. 101 (1992) 219-250. | Zbl 0769.68066

[11] J.-É. Pin and P. Weil, Profinite semigroups, mal'cev products and identities. J. Algebra 182 (1996) 604-626. | Zbl 0857.20040

[12] J.-É. Pin and P. Weil, Polynomial closure and unambiguous product. Theory Comput. Syst. 30 (1997) 1-39. | Zbl 0872.68119

[13] J.-É. Pin and P. Weil, Semidirect products of ordered semigroups. Commun. Algebra 30 (2002) 149-169. | Zbl 1003.06009

[14] J. Reiterman, The Birkhoff theorem for finite algebras. Algebra Universalis 14 (1982) 1-10. | Zbl 0484.08007

[15] I. Simon, Hierarchies of Events with Dot-Depth One. Ph.D. Thesis, University of Waterloo, Waterloo, Ontario, Canada (1972).

[16] I. Simon, Piecewise testable events, in Proc. 2nd GI Conf., edited by H. Brackage. Springer-Verlag, Berlin, Heidelberg, New York. Lect. Notes Comp. Sci. 33 (1975) 214-222. | Zbl 0316.68034

[17] H. Straubing, Finite automata, formal logic, and circuit complexity. Birkhäuser Boston Inc., Boston, MA (1994). | MR 1269544 | Zbl 0816.68086

[18] H. Straubing, On logical descriptions of regular languages, in LATIN 2002. Springer, Berlin, Lect. Notes Comput. Sci. 2286 (2002) 528-538. | Zbl 1059.03034