RAIRO - Theoretical Informatics and Applications

Table of Contents - January 2005 - Volume 39, Issue 01 (Imre Simon, the tropical computer scientist)  

Research Article

Some results on C-varieties

Pin, Jean-Érica1 and Straubing, Howarda2

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; 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 (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:

  • 20M35;
  • 68Q70