The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE-Complete

Details The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE-Complete The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE-Complete

2001-03-26

arxiv.org/abs/cs/0103018v1

Computer Science

Data Structures and Algorithms

45 pages. LaTeX source

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE-Complete does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE-Complete, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE-Complete will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-32893