Word equations

Lecture: Monday, 12:15-14:00, room 140
Classes: Monday, 14:15-16:00, room 5

Lectures

1. Historical sketch: why the problem was considered, what was achieved and what not. Connections to number theory, grup theory, unification.
2. Word equations (in free semigroups): decidability in PSPACE.
   • "Recompression: a simple and powerful technique for word equations", Chapters 2–3.
3. Exponent of periodicity.
• "Recompression: a simple and powerful technique for word equations", Chapters 4, 8.
• "Complexity of Makanin’s Algorithm".
Proofs on bounds on minimal solutions of integer programming:
• "A bound on solutions of linear integer equalities and inequalities".
• "On the Complexity of Integer Programming".
4. SLPs, LZ77, composition systems.
5. Simple proof of the LZ77 representation for length-minimal solutions of word equations. Smallest SLP problem.
   • "Application of Lempel-Ziv Encodings to the Solution of Word Equations".
   • "Application of Lempel–Ziv factorization to the approximation of grammar-based compression".
   • "The Smallest Grammar Problem".
6. Recompression in case of SLPs. Application: equality testing for SLPs. Smallest SLP problem by recompression.
   • "Faster Fully Compressed Pattern Matching by Recompression".
7. Smallest SLP problem by recompression.
   • "Approximation of grammar-based compression via recompression".
8. Data structures for equality testing of dynamic strings. Combinatorial algorithm for fully-SLP compressed pattern matching.
   • "Maintaining Dynamic Sequences under Equality Tests in Polyiogarithmic Time".
   • "Dynamic Pattern Matching".
   • "Processing Compressed Texts: A Tractability Border".
9. Restricted cases: word equations with one variable, with two variables; quadratic equations.
• "Efficient Solving of the Word Equations in One Variable"
• "On Word Equations in One Variable"
• "One-Variable Word Equations in Linear Time"
10. Equations in free groups: regular constraints, inversion, reductions. Positive theory of free groups is decidable .
• "The existential theory of equations with rational constraints in free groups is PSPACE-complete" (Sections 2-3)
• "Existential and Positive Theories of Equations in Graph Products" (Section 6)
11. Equations in free group with regular constraints are in PSPACE (via reduction to the monoid case)
• "Finding All Solutions of Equations in Free Groups and Monoids with Involution"
12. Term unification: first order term unification is in P, second-order unification is undecidable.
13. Monadic second-order unification, its relation to word equations, it is in NP.
14. Context unification is in PSPACE.

Tasks

1. Sheet 1.
2. Sheet 2.
3. Sheet 3.
4. Sheet 4.
5. Sheet 5.
6. Sheet 6.
7. Sheet 7.
8. Sheet 8.
9. Sheet 9 (corrected).
10. Sheet 10 (corrected).
11. Sheet 11.

Papers to Tasks

• Probably the simplest proof of exponential bound for solutions of smallest solutions of integer programming .pdf
• Probably the best upper-bound on smallest solutions of integer programming .pdf. It does not contain the proof for all minimal solutions, but supposedly this is easy to generalise.
• Yao's paper on addition chains .pdf. The best bounds up to date.

Some lecture notes.

Exam

Theses