Some results on C-varieties
LIAFA, Université Paris VII and CNRS, Case 7014, 2 Place
Jussieu, 75251 Paris Cedex 05, France; Jean-Eric.Pin@liafa.jussieu.fr
2 Department of Computer Science, Boston College, Chestnut Hill, MA 02167, USA; firstname.lastname@example.org
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.
Mathematics Subject Classification: 20M35 / 68Q70
© EDP Sciences, 2005