Rational Constraints in Free Groups: A PSPACE-Complete Problem

Title: Rational Constraints in Free Groups: A PSPACE-Complete Problem

Abstract: This research article explores the existential theory of equations with rational constraints in free groups. It presents an algorithm that works in polynomial space, even in the more general setting where each variable has a rational constraint. The main result states that the existential theory of equations in free groups with rational constraints is PSPACE-complete. This is achieved as a corollary of the corresponding statement about free monoids with involution.

The research question at the heart of this study is: How can we efficiently solve the existential theory of equations with rational constraints in free groups?

The methodology employed in this study involves reducing the case of equations with rational constraints in free groups to the case of equations with regular constraints in free monoids with involution. This reduction helps to avoid an exponenti al blow-up and allows for the handling of negations using positive rational constraints.

The results obtained in this study show that the existential theory of equations in free groups with rational constraints is PSPACE-complete. This is achieved by presenting an algorithm that works in polynomial space, even in the more general setting where each variable has a rational constraint.

The implications of these results are significant for the field of theoretical computer science. They provide a better understanding of the complexity of solving equations with rational constraints in free groups and contribute to the ongoing efforts to develop efficient algorithms for solving such problems.

Link to Article: https://arxiv.org/abs/0103018v1 Authors: arXiv ID: 0103018v1