Trevor Jack – Computational Complexity of Idempotent Membership in Partial Bijection Semigroups
Universidade NOVA de Lisboa
We prove that checking whether an idempotent is generated by given partial bijections on a finite set is a PSPACE-complete problem. This result yields as a corollary several new PSPACE-complete problems along with a new proof of Kozen's result regarding transformation semigroups.