1 Regular Languages and Varieties

Let A be a finite alphabet. Let L be a language of \(A^*\) and let x and y be words of \(A^*\). The quotient \(x^{-1}Ly^{-1}\) of L by x and y is defined by the formula

$$ x^{-1}Ly^{-1} = \{ u \in A^* \mid xuy \in L\}. $$

A lattice of languages of \(A^*\) is a set \(\mathcal {L}\) of languages of \(A^*\) containing \(\emptyset \) and \(A^*\) and closed under finite union and finite intersection. It is closed under quotients if every quotient of a member of \(\mathcal {L}\) is also in \(\mathcal {L}\). A Boolean algebra of languages is a lattice of languages closed under complement.

A class of languages is a correspondence \(\mathcal {C}\) which associates with each alphabet A a set \(\mathcal {C}(A^*)\) of regular languages of \(A^*\). A variety of languages is a class of languages \(\mathcal {V}\) closed under Boolean operations, quotients and inverses of morphisms. This means that, for each alphabet A, \(\mathcal {V}(A^*)\) is a Boolean algebra of regular languages closed under quotients and that if \(\varphi : A^* \rightarrow B^*\) is a monoid morphism, then \(L\in \mathcal {V}(B^*)\) implies \(\varphi ^{-1}(L)\in \mathcal {V}(A^*)\).

A variety of finite monoids is a class of finite monoids which is closed under taking submonoids, homomorphic images and finite direct products. Eilenberg’s variety theorem [6] gives a bijective correspondence between varieties of monoids and varieties of languages. Let \(\mathbf {V}\) be a variety of finite monoids and, for each alphabet A, let \(\mathcal {V}(A^*)\) be the set of all languages of \(A^*\) whose syntactic monoid is in \(\mathbf {V}\). Then \(\mathcal {V}\) is a variety of languages. Furthermore, the correspondence \(\mathbf {V}\rightarrow \mathcal {V}\) is a bijection between varieties of monoids and varieties of languages.

A language L is commutative if any word obtained by permuting the letters of a word of L also belongs to L. A variety of languages is commutative if all of its languages are commutative, or equivalently, if all the monoids of the corresponding variety of finite monoids are commutative.

A renaming or length-preserving morphism is a morphism \(\varphi \) from \(A^*\) into \(B^*\), such that, for each word u, the words u and \(\varphi (u)\) have the same length. It is equivalent to require that, for each letter a, \(\varphi (a)\) is also a letter, that is, \(\varphi (A) \subseteq B\). Similarly, a morphism is length-decreasing if the image of each letter is either a letter or the empty word. Finally, a morphism is length-multiplying if all letters have images of the same length, that is, if \(\varphi (A) \subseteq B^k\) for some integer k.

2 The Shuffle Operation

Recall that the shuffle product (or simply shuffle) of two languages \(L_1\) and \(L_2\) over A is the language

$$\begin{aligned} \begin{aligned} L_1 \mathop {\llcorner \!\llcorner \!\!\!\lrcorner }L_2 = \{ w&\in A^* \mid w = u_1v_1 \cdots u_nv_n \text { for some words } u_1, \ldots , u_n, \\&v_1, \ldots , v_n \text { of } A^* \text { such that } u_1 \cdots u_n \in L_1 \text { and } v_1 \cdots v_n \in L_2\}. \end{aligned} \end{aligned}$$

The shuffle product defines a commutative and associative operation over the set of languages over A.

Zoltán Ésik has long been interested in the shuffle operation. In a series of papers with Bertol or with Bloom [3,4,5, 8, 9], he studied the free shuffle algebra and proved that the equational theory of shuffle has no finite axiomatization. This was probably the reason why he got interested in the conjecture proposed by Perrot [12] in 1978.

Perrot wanted to characterize the varieties of languages closed under shuffle. He was able to characterize all commutative varieties closed under shuffle, but failed to characterize the noncommutative ones. However, he conjectured that the only noncommutative variety of languages closed under shuffle is the variety of all regular languages.

This conjecture remained open for twenty years, until Zoltán Ésik, in collaboration with another famous Hungarian-born computer scientist, Imre Simon, managed to solve the conjecture positively [11]. Their proof is very ingenious and was the starting point of further development.

3 Logic on Words

In December 2001, Ésik and Ito published a BRICS report entitled Temporal logic with cyclic counting and the degree of aperiodicity of finite automata. In this paper, which was published in 2003 [10], the authors studied an enrichment of temporal logic involving cyclic counting and they provided an algebraic characterization of the corresponding class of regular languages. An instance of Eilenberg’s variety theorem? Not quite, because this class is closed under inverses of length-preserving morphisms, but is not closed under inverses of arbitrary morphisms.

The next year (2002), Ésik published another BRICS report, entitled Extended temporal logic on finite words and wreath product of monoids with distinguished generators, which became a DLT paper in 2003 [7]: in this paper, he further developed his idea of enriching temporal logic, in the spirit of Wolper [15]. He managed to give an algebraic characterization of several fragments by using monoids with distinguished generators. This led to a series of new results as well as a unified and elegant proof of known results.

It turns out that a similar idea was developed independently and at the same time by Straubing [14]. This gave rise to the theory of \(\mathcal {C}\)-varieties, which is an extension of Eilenberg’s variety theory. The letter \(\mathcal {C}\) refers to a class of morphisms (called \(\mathcal {C}\) -morphisms) between free monoids (for instance length-preserving morphisms, length-decreasing or length-multiplying morphisms). Now a \(\mathcal {C}\)-variety of languages is defined as a variety of languages except that it is only closed under inverses of \(\mathcal {C}\)-morphisms.

The corresponding algebraic objects are no longer monoids, but stamps, that are surjective monoid morphisms \(\varphi :A^* \rightarrow M\) from a finitely generated free monoid \(A^*\) onto a finite monoid M.

4 Back to the Shuffle Operation

In 1995, I proposed another extension of Eilenberg’s variety theorem [13]. A positive variety of languages is defined exactly like a variety of languages, except that it is not closed under complement. In other words, for each alphabet A, \(\mathcal {V}(A^*)\) is not required to be a Boolean algebra of languages, but only a lattice of languages. For the algebraic counterpart, one needs to consider ordered monoids instead of monoids.

The question now arises to describe all positive varieties closed under shuffle. Some progress in this direction can be found in [1], but the first step, namely the commutative case, was clarified only recently, in a paper of Jorge Almeida, Zoltán Ésik and myself [2].

I am sure that Zoltán would have liked to further investigate this type of questions among the numerous topics he was interested in. I deeply miss him, as a scientist and as a personal friend.