×

Semigroups with idempotent stabilizers and applications to automata theory. (English) Zbl 0725.20043

We show that, for every finite semigroup \(S\), there exists an effectively constructible finite semigroup \(S'\) such that \(S\) is a quotient of \(S'\) and such that the right stabilizers of the elements of \(S\) are idempotent and \(\mathcal R\)-trivial (i.e., they satisfy the identities \(x^ 2=x\) and \(xyx=xy\)). Note that the properties of the stabilizers in a semigroup arise in a number of contexts in semigroup theory, such as the connection between Mal’cev products and semidirect products. In particular, stabilizers control the local structure of the derived category of a monoid morphism. Our result is to be confronted with the construction of the Rhodes expansion, where the right stabilizers are \(\mathcal R\)-trivial, a weaker property. However, the Rhodes expansion of \(S\) contains the same groups as \(S\), while our construction may introduce new, abelian groups. More precisely, we prove that the inverse image of each idempotent in the projection of \(S'\) onto \(S\) divides the direct product of a rectangular band by an abelian group. Our construction is based on Rhodes’s construction, and our semigroup \(S'\) arises as the transition semigroup of a certain automaton. Our result has several interesting consequences. We first use it together with a result of I. Simon on path congruences to obtain a new, purely algebraic proof of a deep theorem of McNaughton on the equivalence between deterministic and non-deterministic automata to recognize sets of infinite words. Next, we give an algebraic proof of a theorem of Brown on conditions for the local finiteness of semigroups.
Reviewer: P.Weil (Paris)

MSC:

20M10 General structure theory for semigroups
20M35 Semigroups in automata theory, linguistics, etc.
68Q45 Formal languages and automata
20M05 Free semigroups, generators and relations, word problems
Full Text: DOI