|
Organizers |
A polynomially computable idempotent in the kernel of the free profinite semigroup
by
M.V. Volkov
Ural State University, Ekaterinburg, Russia
Coauthors: Jorge Almeida (University of Porto, Porto, Portugal)
The free profinite semigroup F(A) over a finite set A is the projective limit of all finite A-generated semigroups. Since the semigroups F(A) contain - in an encoded form - all information about finite semigroups, their structure has proved to play an important role in finite semigroup theory. Being equipped with a natural topology, F(A) is a compact topological semigroup, and as such, it has the kernel KA, that is, the least closed ideal. For |A| > 1, no concrete element of KA was known until very recently; first (still unpublished) constructions were independently found by Reilly and Zhang and by the authors. In the talk we discuss what means constructing an element of F(A) and exhibit an algorithm that computes the value of an idempotent element from KA in any finite semigroup S in polynomial (as a function of |S|) time, a feature not provided by any known construction so far. As an application we deduce polynomial algorithms for testing membership in certain semigroup pseudovarieties.
Date received: May 24, 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 # caee-72.