Word equations

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

Both are negotiable, but may be hard to change.


  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.
  3. Exponent of periodicity.
  4. Proofs on bounds on minimal solutions of integer programming:
  5. SLPs, LZ77, composition systems.
  6. Simple proof of the LZ77 representation for length-minimal solutions of word equations. Smallest SLP problem.
  7. Recompression in case of SLPs. Application: equality testing for SLPs. Smallest SLP problem by recompression.
  8. Smallest SLP problem by recompression.
  9. Data structures for equality testing of dynamic strings. Combinatorial algorithm for fully-SLP compressed pattern matching.
  10. Restricted cases: word equations with one variable, with two variables; quadratic equations.
  11. Equations in free groups: regular constraints, inversion, reductions. Positive theory of free groups is decidable .
  12. Equations in free group with regular constraints are in PSPACE (via reduction to the monoid case)
  13. Term unification: first order term unification is in P, second-order unification is undecidable.
  14. Monadic second-order unification, its relation to word equations, it is in NP.
  15. Context unification is in PSPACE.


There will be no more lists.
  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

Some lecture notes.

Notes, updated 19.01.16. No guarantee on correctness nor completeness.


The exam is held in classroom 105 on Tuesday, 2.02.2016. Please book you time in 1-hour slots individually, we shall make some pre-booking on 25th. If needed, it is also possible to make the exam on 01.02 (but please provide some reason). This is an oral exam, you will get three questions: one about definition and status of some problem (decidability/complexity), one about idea of a proof for some result and one about some task solved during classes (or a similar one).


Some of the topics presented during the lectures can be a good starting point for a MSc or PhD thesis. In particular, I have 2 PhD/MSc scholarships availabe within a recently awarded grant focsued on similar topics (details will be given soon).