Benutzerhandbuch Datenschutzhinweis Impressum Kontakt





Finding All Solutions of Equations in Free Groups and Monoids with Involution


Jeż,  Artur
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar

Diekert, V., Jeż, A., & Plandowski, W. (2014). Finding All Solutions of Equations in Free Groups and Monoids with Involution. In E. Hirsch, S. Kuznetsov, J.-E. Pin, & N. Vereshchagin (Eds.), Computer Science - Theory and Applications (pp. 1-15). Berlin: Springer. doi:10.1007/978-3-319-06686-8_1.

The aim of this paper is to describe the set of all solutions of equations in free groups and monoids with involution in the presence of rational constraints. This became possible due to the recently invented recompression technique of the second author. He successfully applied the recompression technique for pure word equations without involution or rational constraints. In particular, his method could not be used as a black box for free groups (even without rational constraints). Actually, the presence of an involution (inverse elements) and rational constraints complicates the situation and some additional analysis is necessary. Still, the recompression technique is powerful enough to simplify proofs for many existing results in the literature. In particular, it simplifies proofs that solving word equations is in PSPACE (Plandowski 1999) and the corresponding result for equations in free groups with rational constraints (Diekert, Hagenah and Gutiérrez 2001). As a byproduct we obtain a direct proof that it is decidable whether or not the solution set is finite.