Some results on 𝒞-varieties
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 1, pp. 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.

DOI : 10.1051/ita:2005014
Classification : 20M35, 68Q70 
@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},
     pages = {239--262},
     publisher = {EDP-Sciences},
     volume = {39},
     number = {1},
     year = {2005},
     doi = {10.1051/ita:2005014},
     mrnumber = {2132590},
     zbl = {1083.20059},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita:2005014/}
}
TY  - JOUR
AU  - Pin, Jean-Éric
AU  - Straubing, Howard
TI  - Some results on $\mathcal {C}$-varieties
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2005
SP  - 239
EP  - 262
VL  - 39
IS  - 1
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita:2005014/
DO  - 10.1051/ita:2005014
LA  - en
ID  - ITA_2005__39_1_239_0
ER  - 
%0 Journal Article
%A Pin, Jean-Éric
%A Straubing, Howard
%T Some results on $\mathcal {C}$-varieties
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2005
%P 239-262
%V 39
%N 1
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita:2005014/
%R 10.1051/ita:2005014
%G en
%F 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) no. 1, pp. 239-262. doi : 10.1051/ita:2005014. http://archive.numdam.org/articles/10.1051/ita:2005014/

[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

[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

[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

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

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

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

[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

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

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

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

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

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

[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

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

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

Cité par Sources :