Algebra Seminar talk
2018-06-29 (10:15)
Peter Mayr (University of Colorado in Boulder)
Computing with transformation semigroups
Abstract:
Given a permutation group by generators, many of its properties like size, membership,... can be determined
in polynomial time using Sims' stabilizer chains. In contrast, the known algorithms for the corresponding
problems for transformation semigroups often rely on an enumeration of the R-classes of the semigroup,
which already requires exponential time (Mitchell, et al 2017). Still there are only relatively few hardness
results that guarantee that these problems essentially cannot be solved more efficiently. The first and most
notable exception is that the membership problem for transformation semigroups is known to be PSPACE-complete
(Kozen, 1977).
We investigate the computational complexity for determining various properties of a transformation semigroup S on n letters given by its generators. For example, checking whether a specified element in S is regular turns out to be PSPACE-complete. On the other hand by considering the action of $S$ on tuples and using graph algorithms we obtain polynomial time algorithms for the following: existence of a left or right zero, nilpotence, whether S is a band, completely regular or a Clifford semigroup, whether S satisfies a fixed identity...
This is join work with Trevor Jack (CU Boulder).