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
topHow 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.
- 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.
- 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.
- S. Eilenberg and M.-P. Schützenberger, On pseudovarieties. Adv. Math.19 (1976) 413–418.
- M. Kunc, Equational description of pseudovarieties of homomorphisms. Theor. Inform. Appl.37 (2003) 243–254.
- 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.
- J.-É. Pin, H. Straubing and D. Thérien, Some results on the generalized star-height problem. Inform. Comput.101 (1992) 219–250.
- J.-É. Pin and P. Weil, Profinite semigroups, mal'cev products and identities. J. Algebra182 (1996) 604–626.
- J.-É. Pin and P. Weil, Polynomial closure and unambiguous product. Theory Comput. Syst.30 (1997) 1–39.
- J.-É. Pin and P. Weil, Semidirect products of ordered semigroups. Commun. Algebra30 (2002) 149–169.
- J. Reiterman, The Birkhoff theorem for finite algebras. Algebra Universalis14 (1982) 1–10.
- 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.
- H. Straubing, Finite automata, formal logic, and circuit complexity. Birkhäuser Boston Inc., Boston, MA (1994).
- H. Straubing, On logical descriptions of regular languages, in LATIN 2002. Springer, Berlin, Lect. Notes Comput. Sci.2286 (2002) 528–538.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.