Biordered set languages (Q1917712)

If \(A\) is a non-empty set and \(M\) is a monoid and \(L\subseteq A^*\), then one says that the language \(L\) is recognized by \(M\) if there is a surjective homomorphism of monoids \(\phi\colon A^*\to M\) such that \(L=P\phi^{-1}\) for some subset \(P\subseteq M\). (Usually it is assumed that both \(A\) and \(M\) are finite, but that is not necessary.) This paper studies recognizable languages \(L\) such that \(P\) is a biordered set, specifically, such that \(L=E\phi^{-1}\), where \(E\) is a biordered subset of the idempotent set \(E(M)\) of \(M\). Biordered sets arise in the characterization of regular semigroups and help describe the idempotent structure [see \textit{K. S. S. Nambooripad}, Structure of regular semigroups I (Mem. Am. Math. Soc. 224, 1979; Zbl 0457.20051)]. If \(L\subseteq A^*\) is any language which can be recognized by idempotents, i.e., \(L\) is the inverse image of some subset of the idempotents of a recognizing monoid, then let \(\delta_L\) be the smallest congruence on \(A^*\) containing \(\{(w,w^2):w\in L\}\). Let \(\delta_L\colon A^*\to A/\delta_L\) be the quotient morphism. Furthermore, for any language \(L\) let \(M(L)\) denote the syntactic monoid of \(L\), i.e., \(M(L)=A^*/P_L\) where \(w_1P_Lw_2\) iff for all \(u,v\in A^*\), \(uw_1v\in L\) exactly when \(uw_2v\in L\). Let \(\eta_L\colon A^*\to M(L)\) be the quotient morphism. Then the paper proves results such as the following. Theorem: If \(L\) is a biordered set language, then \(L=E\delta_L^{-1}\) for some biordered subset \(E\subseteq E(A^*/\delta_L)\). Theorem: The following are equivalent: (i) \(L\) is a biordered language. (ii) \(L\delta_L\) is a biordered subset of \(E(A^*/\delta_L)\). (iii) \(L\eta_L\) is a biordered subset of \(E(M(L))\). (iv) If \(M\) is any monoid recognizing \(L\) by its idempotents, then \(L=E\phi^{-1}\) for some biordered set \(E\subseteq E(M)\), where \(\phi\colon A^*\to M\) is the morphism involved. If \(L\) is a biordered set language, the band closure \(L^c\) of \(L\) is the smallest language containing \(L\) whose syntactic monoid is a band, i.e., consists entirely of idempotents. The paper goes on to give a succinct characterization of \(L^c\), and it describes a construction of biordered set languages from band languages.