1. Word equations: basic definition. Logspace algorithm. SLP-based algorithm.
  2. PSPACE algorithm
  3. Some basic word combinatorics.
  4. Exponent of periodicity
  5. Quadratic equations
  6. Word equations with one variable
  7. Word equations with two variables
  8. Equations without constants: Lyndon-Schützenberge Theorem. Saarela's results.
  9. Defect Theorem.
  10. Bounds for number of solutions of one-variable equation.
  11. Equations in Free groups: reduction to semigroups with regualr constraints and inversion.
  12. Decidability of positive theory of free groups. Information about decidability.
  13. Equations in terms: undecidability of second-order unification. PSPACE algorithm for context unificaton.
Ostatnia modyfikacja: środa, 2 października 2024, 18:16