2
$\begingroup$

Let $\mathcal Rat(A)$ denote the class of rational (or regular) languages over the alphabet $A$, a subset $\mathcal V(A) \subseteq \mathcal Rat(A)$ is called a variety of (rational) languages iff

  1. closed under boolean operations
  2. closed under quotients, i.e. if $L \in \mathcal V(A)$, then so is

    $u^{-1}L = \{ w \in A^* : uw \in L \}$ and $Lu^{-1} = \{ w \in A^* : wu \in L \}$.

  3. closed under inverse images of morphisms, i.e. if $\varphi : A^* \to B^*$ is a morphism and $L \in \mathcal V(B)$ for some variety of languages $\mathcal V(B)$, then $\varphi^{-1}(L) \in \mathcal V(A)$.

On the other side, a (pseudo-)variety of finite monoids $\mathbf V$ is a class of finite monoids such that

  1. it is closed under quotient, i.e. if $\varphi : M \to N$ is a surjective morphism and $M \in \mathbf V$, so $N \in \mathbf V$.
  2. closed under subalgebras, i.e. if $N$ is a subalgebra of $M$ and $M \in \mathbf V$ so $N \in \mathbf V$
  3. closed under finite products, i.e. for $M,N \in \mathbf V$ also $M \times N \in \mathbf V$.

Now according to Eilenberg, there is a bijective correspondence between the class of (pseudo-)varieties of finite monoids and the class of all varieties of rational languages, given by $$ \mathbf V \to \{ L \subseteq A : L\mbox{ is recognized by some monoid of }\mathbf V \}. $$ where a language $L$ is recognized by some monoid $M$ iff there exists a morphism $\varphi : A^* \to M$ and a subset $F \subseteq M$ such that $L = \varphi^{-1}(F)$.

Now my question is where comes condition 3. in the definition of variety of languages from? I tried to prove it for the class given above, if $\varphi : A^* \to B^*$ is a morphism, and $L \in \mathcal V(B)$ for some variety, then $L$ is recognized by some $\psi : B^* \to M$ and $F \subseteq M$. So $\varphi^{-1}(L) = \varphi^{-1}(\psi^{-1}(F))$, then $\psi \circ \phi : A^* \to M$ recognizes $\phi^{-1}(L)$, but I cannot conclude that $M \in \mathbf V$, which is necessary for $\mathcal V(A)$. Had I overlooked something in the definition of condition 3, maybe that $\mathcal V(B)$ has to be a variety over the same pseudovariety but different alphabets? But I nowhere find in the literature such a condition, it is just stated in this general form "for some variety $\mathcal V(B)$"?

$\endgroup$

1 Answer 1

3
$\begingroup$

I think the confusion comes from the fact that a variety of languages is not $\mathcal V(A)$ for some fixed $A$, it is a mapping $\mathcal V: \mathit{Alphabets}\to \mathit{Sets~of~Languages}$, mapping each alphabet $A$ to a set of languages $\mathcal V(A)$.

Now it makes sense to say that $\mathcal V$ is closed under inverse morphisms.

The bijection of Eilenberg is actually between $\mathbf{V}$ and $\mathcal V$ (so no alphabet is fixed on either side), which solves the problem in your proof.

$\endgroup$
1
  • 1
    $\begingroup$ Said differently $\mathcal V$ is a contravariant functor from the category of fg free monoids to the category of Boolean algebras. $\endgroup$ Commented Oct 7, 2013 at 16:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .