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, 14th Aug 2014 Abstract: We present a PSPACE-algorithm 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]