# Some results on C-varieties

Jean-Éric Pin; Howard Straubing

RAIRO - Theoretical Informatics and Applications (2010)

- 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 C-varieties." RAIRO - Theoretical Informatics and Applications 39.1 (2010): 239-262. <http://eudml.org/doc/92759>.

@article{Pin2010,

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 (a1a2...ak)+, where a1,...,ak 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},

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

language = {eng},

month = {3},

number = {1},

pages = {239-262},

publisher = {EDP Sciences},

title = {Some results on C-varieties},

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

volume = {39},

year = {2010},

}

TY - JOUR

AU - Pin, Jean-Éric

AU - Straubing, Howard

TI - Some results on C-varieties

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

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 (a1a2...ak)+, where a1,...,ak 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/92759

ER -

## References

top- D.A.M. Barrington, K.J. Compton, H. Straubing and D. Thérien, Regular languages in nc1. J. Comput. Syst. Sci.44 (1992) 478–499. Zbl0757.68057
- 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
- 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
- S. Eilenberg and M.-P. Schützenberger, On pseudovarieties. Adv. Math.19 (1976) 413–418. Zbl0351.20035
- M. Kunc, Equational description of pseudovarieties of homomorphisms. Theor. Inform. Appl.37 (2003) 243–254. Zbl1045.20049
- D. Perrin and J.-É. Pin, Infinite Words. Pure and Applied Mathematics141 2004.
- J.-É. Pin, A variety theorem without complementation. Russian Math. (Izvestija vuzov. Matematika)39 (1995) 80–90.
- J.-É. Pin, Syntactic semigroups, in Handbook of formal languages, edited by G. Rozenberg and A. Salomaa. Springer-Verlag 1 (1997) 679–746.
- J.-É. Pin, Algebraic tools for the concatenation product. Theoret. Comput. Sci.292 (2003) 317–342. Zbl1064.68057
- J.-É. Pin, H. Straubing and D. Thérien, Some results on the generalized star-height problem. Inform. Comput.101 (1992) 219–250. Zbl0769.68066
- J.-É. Pin and P. Weil, Profinite semigroups, mal'cev products and identities. J. Algebra182 (1996) 604–626. Zbl0857.20040
- J.-É. Pin and P. Weil, Polynomial closure and unambiguous product. Theory Comput. Syst.30 (1997) 1–39. Zbl0872.68119
- J.-É. Pin and P. Weil, Semidirect products of ordered semigroups. Commun. Algebra30 (2002) 149–169. Zbl1003.06009
- J. Reiterman, The Birkhoff theorem for finite algebras. Algebra Universalis14 (1982) 1–10. Zbl0484.08007
- I. Simon, Hierarchies of Events with Dot-Depth One. Ph.D. Thesis, University of Waterloo, Waterloo, Ontario, Canada (1972).
- 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
- H. Straubing, Finite automata, formal logic, and circuit complexity. Birkhäuser Boston Inc., Boston, MA (1994). Zbl0816.68086
- 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.