Lehrstuhl Mathematik & InformatikComplexity Analysis: Finite Transformation Monoids
Abstract. We examine the computational complexity of some problems from algebraic automata theory and from the field of communication complexity: testing Green's relations (- relations that are fundamental in monoid theory -), checking the property of a finite monoid to have only Abelian subgroups, and determining the deterministic communication complexity of a regular language. By well-known algebraizations, these problems are closely linked with each other. We show that all of them are PSPACE-complete.