Partially ordered finite monoids and a theorem of I. Simon
type: Item
instance of: scholarly article
title: Partially ordered finite monoids and a theorem of I. Simon
zbMATH Open document ID: 0658.20035
DOI: 10.1016/0021-8693(88)90067-1
author: Howard Straubing
author: Denis Thérien
published in: Journal of Algebra
publication date: 1988-01-01T00:00:00Z
review text: 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).
Mathematics Subject Classification ID: 20M10
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 06F05
Mathematics Subject Classification ID: 20M30
zbMATH DE Number: 4075401
zbMATH Keywords: partially ordered monoid
zbMATH Keywords: Green's relation
zbMATH Keywords: finite p.o. monoid
zbMATH Keywords: finite \({\mathcal J}\)-trivial monoids
zbMATH Keywords: semigroup extensions
zbMATH Keywords: recognizable languages
zbMATH Keywords: syntactic monoids
zbMATH Keywords: piecewise testable
reviewed by: H. Mitsch
MaRDI profile type: Publication
full work available at URL: 0021-8693(88)90067-1
OpenAlex ID: W2060549391
cites work: Q5570933
cites work: Almost finite expansions of arbitrary semigroups
cites work: Q4132170
cites work: Q3853827
cites work: Q3659988
cites work: Q3776657
cites work: Q4077455
cites work: On finite \(\mathcal J\)-trivial monoids
cites work: Classification of finite monoids: the language approach
cites work: Q3689383
description: scientific article; zbMATH DE number 4075401