Displaying similar documents to “Imre Simon : an exceptional graduate student”

On Varieties of Literally Idempotent Languages

Ondřej Klíma, Libor Polák (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

A language is literally idempotent in case that if and only if , for each , . Varieties of literally idempotent languages result naturally by taking all literally idempotent languages in a classical (positive) variety or by considering a certain closure operator on classes of languages. We initiate the systematic study of such varieties. Various classes of literally idempotent languages can be characterized using syntactic methods. A starting example is the class of all finite unions...

A conjecture on the concatenation product

Jean-Eric Pin, Pascal Weil (2001)

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

Similarity:

In a previous paper, the authors studied the polynomial closure of a variety of languages and gave an algebraic counterpart, in terms of Mal’cev products, of this operation. They also formulated a conjecture about the algebraic counterpart of the boolean closure of the polynomial closure – this operation corresponds to passing to the upper level in any concatenation hierarchy. Although this conjecture is probably true in some particular cases, we give a counterexample in the general...

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.

Some results on 𝒞 -varieties

Jean-Éric Pin, Howard Straubing (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et 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 ( a 1 a 2 ⋯ a k ) + , where a 1 , ... , a k are distinct letters. Next, we generalize...