 CARMA COLLOQUIUM
 Speaker: Volker Diekert, University of Stuttgart
 Title: Finding all solutions of equations in free groups and monoids with involution
 Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 4:00 pm, Thu, 14^{th} Aug 2014
 Abstract:
We present a PSPACEalgorithm to compute a finite graph of exponential
size that describes the set of all solutions of equations in free
groups with rational constraints. This result became possible due to
the recently invented recompression technique of Artur Jez. We show
that it is decidable in PSPACE whenever the set of all solutions is
finite. If the set of all solutions is finite, then the length of a
longest solution is at most doubly exponential.
This talk is based on a joint paper with Artur Jez and Wojciech
Plandowski (arXiv:1405.5133 and LNCS 2014, Proceedings CSR 2014, Moscow, June 7  11, 2014).
 [Permanent link]
