A NOTE ON THE EXISTENTIAL THEORY OF EQUATIONS IN PLAIN GROUPS
Author(s):
VOLKER DIEKERT Universität Stuttgart,
Institut für Informatik, Breitwiesenstr. 20–22,
70565 Stuttgart, Germany MARKUS LOHREY Universität Stuttgart,
Institut für Informatik, Breitwiesenstr. 20–22,
70565 Stuttgart, Germany
History:
Received 31 October 2000 Revised 25 April 2001
Abstract:
Based on a PSPACE-completeness result for free monoids with involution
[4] it is shown that the existential theory of equations with rational
constraints in plain groups is PSPACE-complete. As a corollary this
settles a question from [16].
