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
² Department of Computer Science, Boston College, Chestnut Hill, MA 02167, USA; straubin@cs.bc.edu

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₁a₂...a_k)⁺, where a₁,...,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.