duaLab Open problems

Variety (Formal language theory)

Contents

A variety of languages is a class of regular languages closed under Boolean operations, quotients and inverse images of monoid homomorphisms. By Eilenberg's variety theorem, varieties of languages correspond to varieties of finite monoids. See Eilenberg, Automata, Languages, and Machines, Vol. B, and Pin, Varieties of Formal Languages.

1. Local variety theorem

Theorem 1.1 (Local Eilenberg theorem)☆

Fix a finite alphabet $\Sigma$. The following complete lattices are isomorphic:

  • local varieties over $\Sigma$: sets of regular languages over $\Sigma$ closed under Boolean operations and the derivatives $w^{-1}L$ and $Lw^{-1}$ for $w\in\Sigma^*$;
  • local pseudovarieties: sets of $\Sigma$-generated finite monoids closed under quotients and subdirect products;
  • quotients of the free profinite monoid $\widehat{\Sigma^*}$;
  • semi-Galois subcategories of the semi-Galois category of finite $\Sigma$-sets.

See Gehrke, Grigorieff and Pin, §1 of Adámek, Milius, Myers and Urbat and §5.2 of Uramoto.

2. Topos-theoretic reformulation

Theorem 2.1 (Hyperconnected quotients)☆

Fix a finite alphabet $\Sigma$, and let $(\mathcal E_{\mathrm{of}},\mathcal R)$ be the Boolean-ringed topos of regular languages. The complete lattice of hyperconnected quotients of $\mathcal E_{\mathrm{of}}$ is isomorphic to the four lattices of Theorem 1.1. The isomorphism sends a quotient to the local variety of regular languages it recognizes.

A quotient recognizes $L$ when the Myhill–Nerode right congruence $\sim_L$ lies in the internal filter of the local state classifier that classifies the quotient.

Compare p. 44 of the slides Local state classifier for algebraic language theory and p. 60 of the slides Topoi of automata.

Proof

The hyperconnected quotients of $\mathcal E_{\mathrm{of}}$ correspond to the filters $F$ of finite-index right congruences on $\Sigma^*$ closed under $\rho\mapsto w^{-1}\rho$ (Theorem 4.1). The recognized class $\{L\mid{\sim_L}\in F\}$ is closed under Boolean operations and left quotients. It is also closed under right quotients, since $Lx^{-1}$ is a union of $\sim_L$-classes and so ${\sim_{Lx^{-1}}}\supseteq{\sim_L}$. A finite-index right congruence is the intersection of the Nerode congruences of its classes, so $F$ is determined by its recognized class. Conversely, let $V$ be a local variety and $L_1,\dots,L_n\in V$. Each class of ${\sim_{L_1}}\cap\cdots\cap{\sim_{L_n}}$ is a Boolean combination of right quotients $L_ix^{-1}$, so it lies in $V$. Hence $V$ is the class recognized by the filter generated by the $\sim_L$ with $L\in V$.

Remark 2.2 (One-sided closure)

The slides use internal Boolean subalgebras of $\mathcal R$, which are closed only under $L\mapsto a^{-1}L$. Such a subalgebra need not be a local variety. For $\Sigma=\{a,b\}$, the subalgebra $\{\varnothing,\Sigma^*,a\Sigma^*,\{\varepsilon\}\cup b\Sigma^*\}$ does not contain $(a\Sigma^*)a^{-1}=\{\varepsilon\}\cup a\Sigma^*$. The quotient it generates recognizes exactly the local variety it generates.

4. References