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 Abstract: 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], www.math.unibe.ch
© Copyright 2024 ExpyDoc
