Consider equations over words from over some signature Σ. This problem was
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.
Last couple of years brough a significantly simpler algorithm for this
problem. In particular, generalisations that allow a description of all
solutions, they generalise to equations with regular constraints, inversion,
equations in free group, etc. In some restricted cases even polynomial
algorithms were found.
Interestingly, it turned out that this problem is deeply connected with
grammar compression of strings. In particular, the approach of compressing the
solution of the instance and manipulation of the compressed representation
turned out to be very fruitful, also in other areas.
An important generalisation of word equtions are equations over terms. A
classic result shows that a (first order) term unification is decidable (in
polynoami ltime). However, already the second-order unification (in which case
the variables take arguments that are used in the substitutions) is
undecidable for terms. Still, some restricted variants of second order
unification, most notably context unification, are decidable.
Durng 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 etc. Since those results use
grammar compression, I will also show the most important tools from this area.
Lastly, I would like to sketch some possible further research directions.
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;
* knowledge in string algorithsm and combinatorics is helpful and welcomed, but not assumed;
* general konwledge 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. M. Lothaire, Combinatorics on words, Cambridge Mathematical Library, Cambridge University Press, ISBN: 9780521599245
3. Some contemporary research papers.
W problemie rownań słow rozważamy rownania 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).
W ciągu ostatnich kilku lat dowod rozstrzygalności stał się istotnie prostszy.
Warianty algorytmu pozwalają też na opisanie wszystkich rozwiazań, uogolniają
się do innych obiektow (rownania z więzami regularnymi, rownania w grupach
wolnych, itp.). Niektore ograniczone przypadki (np. rownania z dwoma
zmiennymi) pozwalają na wielomianowe algorytmy.
Co ciekawe, dość nieoczekiwanie okazało się, że problem ten jest głeboko
związany z kompresją (gramatykową) słow. Wprowadzona tu po raz pierwszy
technika przekształcania skompresowanej postaci rozwiązania okazała się bardzo
przydatna w wielu problemach.
Ważnym uogolnieniem rownań w słowach są rownania w ktorych rozważamy termy.
Klasyczny wynik dotyczący unifikacji (pierwszego rzędu) mowi, iż unifikacja
termow możliwa jest w czasie wielomianowym. Sytuacja zmienia się, gdy
dopuścimy, aby zmienne reprezentowały funkcje, a nie tylko zamknięte termy. W
ogolności problem ten jest nierozstrzygalny, ale w wielu ograniczonych
przypadkach pozostaje jednak rozstrzygalny (np. unifikacja kontekstowa).
W czasie wykładu chciałbym przedstawić kilka (klasycznych oraz nowych) wynikow
dotycząch rownań słow i ich uogolnień: rostrzygalność, generacja rozwiązań,
itp. Jako że wszystkie te metody bazują obecnie na kompresji gramatykowej,
przedstawię też kilka podstawowych faktow dotyczących tej kompresji. Ponadto
mam nadzieję pokazać kilka potencjalnych kierunkow dalszego rozwoju.
Mam nadzieję, że wykłąd stanowić będzie dobre wprowadzenie do pracy
magisterskiej lub doktoratu w powiazanych dziedzinach. W szczegolności,
tematyka wykładu powiązana jest z tematyką otrzymanego właśnie przez mnie
grantu, w ramach ktorego przewidziane są dwa stypendia
magisterskie/doktoranckie.
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;
* znajmość algorytmow tekstowych będzie chwilami pomocna, ale nieobowiązkowa;
* ogolne 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. M. Lothaire, Combinatorics on words, Cambridge Mathematical Library, Cambridge University Press, ISBN: 9780521599245
3. Kilka wspołczesnych prac naukowych.
