a1 LIAFA, Université Paris VII and CNRS, Case 7014, 2 Place Jussieu, 75251 Paris Cedex 05, France; Jean-Eric.Pin@liafa.jussieu.fr
a2 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.
(Online publication March 15 2005)
Mathematics Subject Classification: