Word Equations: Theory and Applications

14^th March 2019, 14:00
Prof. Dirk Nowotka
Kiel University

Abstract

The investigation of the algorithmic problem of solving equations in free semigroups (word equations) originated in the attempt to use it as a device to prove the undecidability of Hilbert's 10th problem in the 1960/70s.
As it has turned out, however, solving word equations is, although algorithmically demanding, decidable.
This problem has developed into a research area of its own with quite some progress and yet still very interesting open questions. Adding to that interest is the fact that this very theoretical research has started to make quite some impact on the practical field of software verification. Namely, so called string solvers are increasingly used in analysing software for security aspects.
Here, the existential theory of word equations is enriched with predicates like length and rational constraints.

In my talk I will give an overview of how the area of word equations has developed, I will introduce some recent results and sketch out the current state of the art, mention open problems, and draw the connection to practical applications.