A language theoretic interpretation of the Schützenberger representations with applications to certain varieties of languages (Q795178)

Let A be a finite set and \(A^+\) the free semigroup generated by A. A finite semigroup S recognizes the language \(X\subseteq A^+\) iff there exists a morphism \(\phi:A^+\to S\) such that X is the union of equivalence classes of the congruence \(\phi \phi^{-1}\). A class V of finite semigroups is called an S-variety (or a pseudovariety) if for any \(S,T\in V,\quad S\times T\in V\) and V contains all morphic images of subsemigroups of S. If V is an S-variety and \({\mathcal V}\) a class of subsets of \(A^+\), then \(V\leftrightarrow {\mathcal V}\) means that \({\mathcal V}\) consists of all languages \(X\subseteq A^+\) which are recognized by semigroups in V. M-varieties and G-varieties are defined similarly for monoids and groups respectively and the corresponding classes of recognizable languages consist of subsets of \(A^*\) (the free monoid generated by A). Using a graph theoretic interpretation of the Schützenberger representation of semigroups the author develops a general technique for describing languages in \({\mathcal V}\), \({\mathcal V}\leftrightarrow V\), when V is some special variety (in particular, a certain M-variety of unions of groups from the given G-variety or a certain S-variety of semigroups S such that eSe is in the given G-variety for all idempotents e of S).