Christian Hagenah
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Christian Hagenah has a total of 2 co-authors. Here are the top co-authors by number of shared publications:
- Claudio Gutierrez
University of Chile, Santiago, Chile
1 shared publication - Volker Diekert
University of Stuttgart, Stuttgart, Germany
1 shared publication
Latest Publications
- Open Access
The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE-Complete
It is known that the existential theory of equations in free groups is decidable. This is a famous result of Makanin. On the other hand it has been shown that the scheme of his algorithm is not primitive recursive. In this paper we present an algorithm that works in polynomial space, even in the more general setting where each variable has a rational constraint, that is, the solution has to respect a specification given by a regular word language. Our main result states that the existential theory of equations in free groups with rational constraints is PSPACE-complete. We obtain this result as a corollary of the corresponding statement about free monoids with involution.
Open AccessThe Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE-Complete
It is known that the existential theory of equations in free groups is decidable. This is a famous result of Makanin. On the other hand it has been shown that the scheme of his algorithm is not primitive recursive. In this paper we present an algorithm that works in polynomial space, even in the more general setting where each variable has a rational constraint, that is, the solution has to respect a specification given by a regular word language. Our main result states that the existential theory of equations in free groups with rational constraints is PSPACE-complete. We obtain this result as a corollary of the corresponding statement about free monoids with involution.