Gleichungen mit regulären Randbedingungen über freien Gruppen

Abstract

Wir beweisen, daß das Erfüllbarkeitsproblem für Gleichungen mit regulären Randbedingungen über freien Gruppen PSPACE-vollständig ist. Wir zeigen auch, daß eine minimale Lösung einer solchen Gleichung höchstens eine doppelt exponentielle Länge hat und in 2-DEXPTIME berechnet werden kann. Wir reduzieren zuerst das Problem Gleichungen mit regulären Randbedingungen über einer freien Gruppen zu lösen auf das Problem Gleichungen mit regulären Randbedingungen über freien Monoiden mit einer Anti-Involution zu lösen. Anschließend stellen wir einen Algorithmus vor, der in PSPACE entscheidet, ob diese Gleichungen lösbar sind und einen Algorithmus, der in 2-DEXPTIME eine Lösung berechnet, wenn die Gleichung lösbar ist.

We prove that the satisfiability problem for equations with regular constraints over free groups is PSPACE-complete. We also show that a minimal solution of such an equation has at most a double exponential length and can be computed in 2-DEXPTIME. We first reduce the problem to solve equations with regular constraints over free groups to the problem to solve equations with regular constraints over monoids with an anti-involution. Then we present an algorithm that decides in PSPACE whether these equations are solvable and an algorithm that computes a solution in 2-DEXPTIME if the equation in solvable.