- 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
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]