Partially ordered finite monoids and a theorem of I. Simon (Q1111705): Difference between revisions

A semigroup S is called \({\mathcal J}\)-trivial if Green's relation \({\mathcal J}\) is the identity on S, and a monoid M is called partially ordered (p.o.) if M admits a partial order \(\leq\) such that the identity of M is the maximum element of M and such that ac\(\leq bd\) in M whenever \(a\leq b\) and \(c\leq d\). It is immediate that every p.o. monoid is \({\mathcal J}\)-trivial, but that the converse is false. In this paper it is shown however that every finite \({\mathcal J}\)-trivial monoid is a homomorphic image of a finite p.o. monoid. The proof of this beautiful result is based on the ideal structure of finite \({\mathcal J}\)-trivial monoids and owes much to the theory of semigroup extensions studied by \textit{J. Birget} and \textit{J. Rhodes} [J. Pure Appl. Algebra 32, 239-287 (1984; Zbl 0546.20055)]. Related results on finite \({\mathcal J}\)-trivial monoids were found by \textit{H. Straubing} [Semigroup Forum 19, 107-110 (1980; Zbl 0435.20036)]. As a result of this theorem a completely new proof of the theorem of \textit{I. Simon} [Lect. Notes Comput. Sci. 33, 214-222 (1975; Zbl 0316.68034)] is obtained which characterizes those recognizable languages whose syntactic monoids are \({\mathcal J}\)-trivial (namely, the piecewise testable ones).