## 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.
### Lectures

- Historical sketch: why the problem was considered, what was achieved and what not. Connections to number theory, grup theory, unification.
- Word equations (in free semigroups): decidability in PSPACE.
- Exponent of periodicity.
Proofs on bounds on minimal solutions of integer programming:
- SLPs, LZ77, composition systems.
- Simple proof of the LZ77 representation for length-minimal solutions of word equations.
Smallest SLP problem.
- Recompression in case of SLPs. Application: equality testing for SLPs.
Smallest SLP problem by recompression.
- Smallest SLP problem by recompression.
- Data structures for equality testing of dynamic strings.
Combinatorial algorithm for fully-SLP compressed pattern matching.
- Restricted cases: word equations with one variable, with two variables; quadratic equations.
- Equations in free groups: regular constraints, inversion, reductions. Positive theory of free groups is decidable .
- Equations in free group with regular constraints are in PSPACE (via reduction to the monoid case)
- Term unification: first order term unification is in P, second-order unification is undecidable.
- Monadic second-order unification, its relation to word equations, it is in NP.
- Context unification is in PSPACE.

### Tasks

There will be no more lists.

- Sheet 1.
- Sheet 2.
- Sheet 3.
- Sheet 4.
- Sheet 5.
- Sheet 6.
- Sheet 7.
- Sheet 8.
- Sheet 9 (corrected).
- Sheet 10 (corrected).
- 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.

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

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).
### Theses

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).