# Some results on $\mathcal{C}$-varieties

Jean-Éric Pin; Howard Straubing

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2005)

- Volume: 39, Issue: 1, page 239-262
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topPin, Jean-Éric, and Straubing, Howard. "Some results on $\mathcal {C}$-varieties." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 39.1 (2005): 239-262. <http://eudml.org/doc/244768>.

@article{Pin2005,

abstract = {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_1a_2\cdots a_k)^+$, where $a_1,\ldots ,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.},

author = {Pin, Jean-Éric, Straubing, Howard},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {monoid morphisms; varieties; regular languages; finitely generated free monoids; length-preserving morphisms; finite monoids; stamps; identities},

language = {eng},

number = {1},

pages = {239-262},

publisher = {EDP-Sciences},

title = {Some results on $\mathcal \{C\}$-varieties},

url = {http://eudml.org/doc/244768},

volume = {39},

year = {2005},

}

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

PB - EDP-Sciences

VL - 39

IS - 1

SP - 239

EP - 262

AB - 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_1a_2\cdots a_k)^+$, where $a_1,\ldots ,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.

LA - eng

KW - monoid morphisms; varieties; regular languages; finitely generated free monoids; length-preserving morphisms; finite monoids; stamps; identities

UR - http://eudml.org/doc/244768

ER -

## References

top- [1] D.A.M. Barrington, K.J. Compton, H. Straubing and D. Thérien, Regular languages in $n{c}^{1}$. J. Comput. Syst. Sci. 44 (1992) 478–499. Zbl0757.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. Zbl1031.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. Zbl0359.94067
- [4] S. Eilenberg and M.-P. Schützenberger, On pseudovarieties. Adv. Math. 19 (1976) 413–418. Zbl0351.20035
- [5] M. Kunc, Equational description of pseudovarieties of homomorphisms. Theor. Inform. Appl. 37 (2003) 243–254. Zbl1045.20049
- [6] D. Perrin and J.-É. Pin, Infinite Words. Pure and Applied Mathematics 141 2004. Zbl1094.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. Zbl1064.68057
- [10] J.-É. Pin, H. Straubing and D. Thérien, Some results on the generalized star-height problem. Inform. Comput. 101 (1992) 219–250. Zbl0769.68066
- [11] J.-É. Pin and P. Weil, Profinite semigroups, mal’cev products and identities. J. Algebra 182 (1996) 604–626. Zbl0857.20040
- [12] J.-É. Pin and P. Weil, Polynomial closure and unambiguous product. Theory Comput. Syst. 30 (1997) 1–39. Zbl0872.68119
- [13] J.-É. Pin and P. Weil, Semidirect products of ordered semigroups. Commun. Algebra 30 (2002) 149–169. Zbl1003.06009
- [14] J. Reiterman, The Birkhoff theorem for finite algebras. Algebra Universalis 14 (1982) 1–10. Zbl0484.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. Zbl0316.68034
- [17] H. Straubing, Finite automata, formal logic, and circuit complexity. Birkhäuser Boston Inc., Boston, MA (1994). Zbl0816.68086MR1269544
- [18] H. Straubing, On logical descriptions of regular languages, in LATIN 2002. Springer, Berlin, Lect. Notes Comput. Sci. 2286 (2002) 528–538. Zbl1059.03034

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.