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 , where 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},
volume = {39},
year = {2005},
pages = {239-262},
doi = {10.1051/ita:2005014},
mrnumber = {2132590},
zbl = {1083.20059},
language = {en},
url = {http://dml.mathdoc.fr/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, Tome 39 (2005) pp. 239-262. doi : 10.1051/ita:2005014. http://gdmltest.u-ga.fr/item/ITA_2005__39_1_239_0/
[1] ,, and, Regular languages in . J. Comput. Syst. Sci. 44 (1992) 478-499. | Zbl 0757.68057
[2] , 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] , 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] and, On pseudovarieties. Adv. Math. 19 (1976) 413-418. | Zbl 0351.20035
[5] , Equational description of pseudovarieties of homomorphisms. Theor. Inform. Appl. 37 (2003) 243-254. | Numdam | Zbl 1045.20049
[6] and, Infinite Words. Pure and Applied Mathematics 141 2004. | Zbl 1094.68052
[7] , A variety theorem without complementation. Russian Math. (Izvestija vuzov. Matematika) 39 (1995) 80-90.
[8] , Syntactic semigroups, in Handbook of formal languages, edited by G. Rozenberg and A. Salomaa. Springer-Verlag 1 (1997) 679-746.
[9] , Algebraic tools for the concatenation product. Theoret. Comput. Sci. 292 (2003) 317-342. | Zbl 1064.68057
[10] , and, Some results on the generalized star-height problem. Inform. Comput. 101 (1992) 219-250. | Zbl 0769.68066
[11] and, Profinite semigroups, mal'cev products and identities. J. Algebra 182 (1996) 604-626. | Zbl 0857.20040
[12] and, Polynomial closure and unambiguous product. Theory Comput. Syst. 30 (1997) 1-39. | Zbl 0872.68119
[13] and, Semidirect products of ordered semigroups. Commun. Algebra 30 (2002) 149-169. | Zbl 1003.06009
[14] , The Birkhoff theorem for finite algebras. Algebra Universalis 14 (1982) 1-10. | Zbl 0484.08007
[15] , Hierarchies of Events with Dot-Depth One. Ph.D. Thesis, University of Waterloo, Waterloo, Ontario, Canada (1972).
[16] , 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] , Finite automata, formal logic, and circuit complexity. Birkhäuser Boston Inc., Boston, MA (1994). | MR 1269544 | Zbl 0816.68086
[18] , On logical descriptions of regular languages, in LATIN 2002. Springer, Berlin, Lect. Notes Comput. Sci. 2286 (2002) 528-538. | Zbl 1059.03034