Równania w Słowach

Wykład: wtorek, 14–16, sala 140
Ćwiczenia: wtorek, 16–18, sala 5

Listy zadań, notatki.

Plan wykładów

1. Równania w słowach: historia, podstawowe własności. SLP. Prosty algorytm używający SLP.
• "Recompression: a simple and powerful technique for word equations", Rozdziały 1–2.
• "Application of Lempel-Ziv Encodings to the Solution of Word Equations".
2. Algorytm działający w PSPACE.
• "Recompression: a simple and powerful technique for word equations", Rozdziały 2–3.
3. Wykładnik periodyczności: wstęp i dowód dla słów jednoliterowych.
   • "Recompression: a simple and powerful technique for word equations", Rozdziały 4, 8.
   • "A bound on solutions of linear integer equalities and inequalities".
4. Okresowość, słowa prymitywne. Wykładnik periodyczności: ogólny przypadek.
• "Complexity of Makanin’s Algorithm".
Równania kwadratowe. Powody. Algorytm Plotkina. Uwaga o równaniach kwadratowych w grupie wolnej.
5. Równania z jedną zmienną. Algorytm kombinatoryczny o czasie działania O(n log n).
   • "Efficient Solving of the Word Equations in One Variable"
6. Równania z jedną zmienną: kombinatoryczny algorytm o czasie działania O(n + #X log n).
   • "On Word Equations in One Variable"
7. Równania z jedną zmienną: algorytm o czasie działania O(n + #X log n) oparty o kompresję.
   • "One-Variable Word Equations in Linear Time"
8. Równania z dwoma zmiennymi. Czemu, własności. Informacja o algorytmie wielomianowym.
9. Równania bez stałych. Równania komutacji. Twierdzenie Lyndon–Schützenberger.
   • Word equations qhere a power equals a product of powers
   • Alternative proof of the Lyndon–Schützenberger Theorem
10. Równania w grupie wolnej: redukcja do równań w słowach z inwersją i więzami regularnymi.
    • "The existential theory of equations with rational constraints in free groups is PSPACE-complete" (Rozdziały 2–3)
11. Nierozstrzygalność teorii równań w słów. Informacja o rozstrzygalności dla grupy wolnej. Rozstrzygalność teorii pozytywnej dla grupy wolnej.
    • "Existential and Positive Theories of Equations in Graph Products" (Section 6)
12. Algorytm rozwiązujący równania w grupie wolnej z inwolucją, skończona reprezentacja wszystkich rozwiązań.
• "Finding All Solutions of Equations in Free Groups and Monoids with Involution"
13. Monadyczna unifikacja drugiego rzędu: jej związki z równaniami w słowach i przynależność do NP.
    • "The Complexity of Monadic Second-Order Unification"
14. Combinatorial algorithm for fully-SLP compressed pattern matching.
    • "Processing Compressed Texts: A Tractability Border".
15. Data structures for equality testing of dynamic strings.
    • "Maintaining Dynamic Sequences under Equality Tests in Polylogarithmic Time".
    • "Dynamic Pattern Matching".

Egzamin: