Displaying similar documents to “Equational description of pseudovarieties of homomorphisms”

Some results on -varieties

Jean-Éric Pin, Howard Straubing (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

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 , where are distinct letters....

Equational description of pseudovarieties of homomorphisms

Michal Kunc (2003)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

The notion of pseudovarieties of homomorphisms onto finite monoids was recently introduced by Straubing as an algebraic characterization for certain classes of regular languages. In this paper we provide a mechanism of equational description of these pseudovarieties based on an appropriate generalization of the notion of implicit operations. We show that the resulting metric monoids of implicit operations coincide with the standard ones, the only difference being the actual interpretation...

Regular languages definable by Lindström quantifiers

Zoltán Ésik, Kim G. Larsen (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

In our main result, we establish a formal connection between Lindström quantifiers with respect to regular languages and the double semidirect product of finite monoids with a distinguished set of generators. We use this correspondence to characterize the expressive power of Lindström quantifiers associated with a class of regular languages.

Regular languages definable by Lindström quantifiers

Zoltán Ésik, Kim G. Larsen (2003)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

In our main result, we establish a formal connection between Lindström quantifiers with respect to regular languages and the double semidirect product of finite monoids with a distinguished set of generators. We use this correspondence to characterize the expressive power of Lindström quantifiers associated with a class of regular languages.