Volker Diekert : Solving word equations and beyond: developments over the past 20 years

- Auteur :Mohamed Lokbani - Colloques

Solving word equations and beyond: developments over the past 20 years


Volker Diekert

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.

Partager :
  • Envoyer
  • Imprimer