FG1 Seminar talk

2018-06-29 (10:15)
Peter Mayr (University of Colorado in Boulder)
Computing with transformation semigroups

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).