Résumé | More than 30 years after their inception, the decidability proofs for
reachability in vector addition systems (VAS) still retain much of
their mystery. These proofs rely crucially on a decomposition of runs
successively refined by Mayr, Kosaraju, and Lambert, which appears
rather magical.
This talk offers a justification for this decomposition technique, by
showing that it emerges naturally in the study of the ideals of well
quasi ordered sets. A lot of applications of this recent breakthrough is
expected on various VAS extensions. This is a joint work with Sylvain
Schmitz.
PART I (45 minutes): Ideals for well quasi ordered sets.
PART II (45 minutes): Ideals of the VAS runs. |