Solving word equations and beyond: developments over the past 20 years
University of Stuttgart
Jeudi 21 septembre, 15:30-16:30, Salle 3195, Pavillon André-Aisenstadt
Université de Montréal, 2920 Chemin de la Tour
Café avant 15:00-15:30
"WᴏʀᴅEǫᴜᴀᴛɪᴏɴ" describes an exciting and active research field in discrete mathematics, combinatorics on words, and theoretical computer science. A seminal result by Makanin in 1977 showed that the problem WᴏʀᴅEǫᴜᴀᴛɪᴏɴ is decidable. This result was the starting point for ongoing research: simplify the original (very long and very delicate) proof, determine the complexity of the problem, study equations in other algebraic structures. A natural algebraic structure is provided by partial commutation. This is of particular interest in computer science because it models concurrent behavior: say a and b are independent events, then we obtain a commutation relation ab=ba, but this is relation is partial: there is no reason for any other commutation between other events.
Equations in the context of partial commutation were in the focus since the mid 1980s; and decidability was eventually shown by Matiyasevich in 1996 and published in 1997. Since then there was considerable progress in the area. My talk is about a few developments over the past twenty years.