RUB » LMI » Mitarbeiter » H. Simon » Publications in Proceedings » Complexity Analysis: Finite Transformation Monoids

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