RAIRO - Theoretical Informatics and Applications (RAIRO: ITA)

Issue		Theoret. Informatics Appl. Volume 39, Number 1, January-March 2005 Imre Simon, the tropical computer scientist
Page(s)		239 - 262
DOI		10.1051/ita:2005014

Theoret. Informatics Appl. 39, 239-262 (2005)
DOI: 10.1051/ita:2005014

Some results on $\cal C$ -varieties

Jean-Éric Pin¹ and Howard Straubing²

¹ 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_1a_2\cdots a_k)^+$ , where $a_1,\ldots,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.

What is OpenURL?

Some results on -varieties

Some results on $\cal C$ -varieties