Consider equations over words over an alphabet Σ. This problem was initially studied due to its connection with Hilbert's 10th problem and connections with
group theory. Contrary to early intuitions, it was shown to be decidable
by Makanin in his seminal result.
Modern approach to this problem are based on compression which leads to much simpler solution and in particular does not depend on word combinatorics.
Over the years, several generalisations of the problem were considered, those include description of all solutions, equations with (regular) constraints, equations with inversion, equations in free group, generalisation to term equations (context unification), etc.
In most cases the known algorithms generalise to those setting, sometimes trivially and sometimes in an involved way.
On the other hand, simplified variants were also investigated, those include equations with one or two variables (for which polynomial-time algorithms are known) or quadratic word equations (which have a very simple linear-space algorithm).
Lastly, combinatorial properties of solutions of word equations were also investigated, mostly in the case of equations without constants. Several characterizations of various equations classes were obtained.
During this lecture I would like to present a couple of classical and new
results for word equations and their generalisations: decidability of
satisfiability, generation of all solutions, algorithms for restricted variants
(quadratic, one variable, two variables), combinatorial properties of solutions sets (mostly in case of constant-free equations).
The lecture can be in English, depending on the audience.
Requirements:
* basic knowledge of algebra (groups);
* basic knowledge of computational complexity classes, in particular non-deterministic ones and space classes;
* knowledge in string algorithms and combinatorics is helpful and welcomed, but not assumed;
* general knowledge and skills in discrete mathematics.
Literature:
1. M. Lothaire, Algebraic combinatorics on words, Encyclopedia of Mathematics and its Applications 90, Cambridge University Press, ISBN 978-0-521-81220-7
2. Some contemporary research papers.
W problemie równań słów rozważamy równania nad słowami z ustalonego alfabetu
Σ. Problem ten był intensywnie badany ze względu na swoje związki z 10.
problemem Hilberta oraz teorią grup. Wbrew oczekiwaniom, okazał się
rozstrzygalny (słynny algorytm Makanina).
Współczesne podejście do tego problemu opiera się na kompresji, która prowadzi do znacznie prostszego rozwiązania i mniej opiera się na kombinatoryce słów.
Na przestrzeni lat rozważano kilka uogólnień tego problemu, w tym opis wszystkich rozwiązań, równania z więzami (regularnymi), równania z inwersją, równania w grupach wolnych, uogólnienie na równania termów (unifikacja kontekstów), itd.
W większości przypadków znane algorytmy uogólniają się do tych scenariuszy, czasem trywialnie, a czasem w trudny sposób.
Z drugiej strony, badane są również warianty uproszczone, takie jak równania z jedną lub dwiema zmiennymi (dla których znane są algorytmy wielomianowe) lub równania kwadratowe (dla których istnieje bardzo prosty algorytm w liniowej pamieci).
Badane są również własności kombinatoryczne rozwiązań równań słownych, głównie w przypadku równań bez stałych. Uzyskano kilka charakterystyk różnych klas równań.
W czasie wykładu chciałbym przedstaw kilka (klasycznych oraz nowych) wyników
dotyczących równań słów i ich uogólnień: rozstrzygalność, generowanie rozwiązań,
ograniczone przypadki (równania kwadratowe, równania z jedną zmienną, równania z dwoma zmiennymi),
własności kombinatoryczne zbiorów rozwiązań (głównie w przypadku równań bez stałych).
Wykład może być prowadzony po angielsku (w zależności od preferencji
słuchaczy).
Wymagania:
* podstawowa znajomość algebry (grupy);
* podstawowa znajomość klas złożoności obliczeniowej, w tym klas niedeterministycznych oraz klas pamięciowych;
* znajomość algorytmów tekstowych i kombinatoryki słów będzie momentami pomocna, ale jest nieobowiązkowa;
* ogólne obycie z matematyki dyskretnej.
Literatura:
1. M. Lothaire, Algebraic combinatorics on words, Encyclopedia of Mathematics and its Applications 90, Cambridge University Press, ISBN 978-0-521-81220-7
2. Kilka współczesnych prac naukowych.
