|
Organizers |
Tameness of the Pseudovariety R
by
Jorge Almeida
University of Porto
Steinberg and the author have introduced the notion of a tame pseudovariety . They also have shown that the semidirect product of any finite number of tame pseudovarieties has decidable membership problem, thus providing a strong motivation for establishing tameness of pseudovarieties. For instance: by Ash's theorem, the pseudovariety G of all finite groups is tame; the author has shown that the pseudovariety Gp of all finite p-groups is tame; Rhodes has announced that the pseudovariety A of all finite aperiodic semigroups is tame, which will yield the computability of the Krohn-Rhodes (group or p-group) complexity; a few other examples have been given by Steinberg, Trotter, Zeitoun, and the author.
Three basic ingredients intervene in proving tameness of a pseudovariety V. The first is the choice of a suitable signature \sigma consisting of implicit operations with reasonable computability properties. Often, \sigma involves only the basic operation of weak inversion (reducing to the \omega-power in the aperiodic case) besides multiplication. The other two ingredients are the word problem for free objects over V with respect to the signature \sigma and an abstract \sigma-reducibility property with similarities with the algorithmic property of hyperdecidability which was introduced earlier by the author.
In this talk, we illustrate these ideas with the pseudovariety R of all finite Re-trivial semigroups. This improves on results of Silva and the author who have shown that R is hyperdecidable for strongly connected graphs.
Date received: May 12, 2000
Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caec-28.