Orderable pseudovarieties

Room FC1 030, DMat-FCUP
Friday, 15 June, 2018 - 14:30

Pseudovarieties of ordered semigroups have been introduced as a refined algebraic classifying tool for regular languages in the sense of Eilenberg's Correspondence Theorem. Forgetting the order, each such pseudovariety generates a pseudovariety of semigroups. A natural question is which pseudovarieties of semigroups arise in this way from non-selfdual pseudovarieties of ordered semigroups which, for the purpose of the talk, we call orderable.

A notable example of an orderable pseudovariety is the class of all finite J-trivial semigroups, which is expressed by saying that every such semigroup is a quotient of a subsemigroup of a finite ordered monoid in which 1 is minimum (Straubing-Thérien). It is well known that this result is intimately related with Simon's characterization of piecewise testable languages. Similar examples appear more generally as intermediate steps in concatenation hierarchies of regular languages but seem to be rare in other contexts.

Motivated by this question, we explored many important examples of pseudovarieties and realized that orderability turns out to fail for many familiar large pseudovarieties. Several results of this kind can be obtained by investigating the action of the associated relatively free profinite semigroups on their minimum ideals, establishing group mapping-like properties in the sense of Rhodes. Such negative examples are given by the Krohn-Rhodes complexity pseudovarieties as well as the pseudovarieties of all finite semigroups with groups from prescribed pseudovarieties. If the minimum ideal has no torsion, it is harder, if not impossible to apply our technique. It is thus for smaller familiar pseudovarieties that there is a better chance of observing our property.

This talk is meant as a survey of this problem. It is based on joint work with O. Klíma (Masaryk University, Brno, Czech Republic).


Jorge Almeida



PDF File: