Solving equations in free (semi)groups

Mathematisches Institut, Sidlerstrasse 5, CH-3012 Bern
Philosophischnaturwissenschaftliche Fakultät
Departement Mathematik und Statistik
Mathematisches Institut
Mathematical Colloquia
Monday, 07 March 2016
17:15 h, Lecture Room B 78
Dr. Artur Jez, University of Wroclaw
Solving equations in free (semi)groups
In this talk I will present an algorithm for solving equations in free semigroups; I will also
comment on the extensions needed to make it work also for free groups. In both cases the
algorithm can be also used to obtain a finite graph-like representation of all solutions.
The result is obtained by employing a simple technique of local recompression. The technique
is based on local modification of variables (replacing $X$ by $aX$ or $Xa$) and iterative
replacement of pairs of letters occurring in the equation by a `fresh' letter, which can be seen
as a bottom-up compression of the solution of the given equation. The algorithm obtained
using this technique is better than the known ones in terms of computational complexity,
simplicity of formulation and proof length.
Sekretariat, Mathematisches Institut, Sidlerstrasse 5, CH-3012 Bern, Tel. +41 (0)31 631 88 21, Fax +41 (0)31 631 85 10
[email protected],