zbMATH — the first resource for mathematics

Partially ordered finite monoids and a theorem of I. Simon. (English) Zbl 0658.20035
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 J. Birget and J. Rhodes [J. Pure Appl. Algebra 32, 239-287 (1984; Zbl 0546.20055)]. Related results on finite \({\mathcal J}\)-trivial monoids were found by 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 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).
Reviewer: H.Mitsch

20M10 General structure theory for semigroups
68Q45 Formal languages and automata
06F05 Ordered semigroups and monoids
20M30 Representation of semigroups; actions of semigroups on sets
Full Text: DOI
[1] Krohn, K.B; Rhodes, J; Tilson, B, (), Chap. 8
[2] Birget, J.C; Rhodes, J, Almost finite expansions of arbitrary semigroups, J. pure appl. algebra, 32, 239-287, (1984) · Zbl 0546.20055
[3] Eilenberg, S, ()
[4] Knast, R, A semigroup characterization of dot-depth one languages, RAIRO inform. théor., (1984)
[5] Lallement, G, Semigroups and combinatorial applications, (1979), Wiley New York · Zbl 0421.20025
[6] Sakarovich, J; Simon, I, (), Chap. 6
[7] Pin, J.E, Variétés de languages formels, (1984), Masson Paris · Zbl 0636.68093
[8] Rhodes, J; Tilson, B, The two-sided paper, (1985), unpublished manuscript
[9] Simon, I, Hierarchies of events of dot-depth one, ()
[10] Simon, I, Piecewise testable events, (), 214-222
[11] Straubing, H, On finite J-trivial monoids, (), 107-110 · Zbl 0435.20036
[12] Thérien, D, Classification of finite monoids: the language approach, Theoret. comput. sci., 14, 195-208, (1981) · Zbl 0471.20055
[13] Thérien, D, Subword counting and nilpotent groups, () · Zbl 0572.20052
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.