Friday, December 03, 2010

Pushdown Automata and Vector Addition Systems

Philippe Schnoebelen just sent me an email announcing the forthcoming event Pushdown Automata and Vector Addition Systems: A New Look At Two Classical Problems, which will be held at LSV in Cachan on January 20, 2011.Quoting from the web page for this one-day event:
This special event focuses on two recent major claims/results:
  • a new proof, by P. Jančar, for the decidability of equivalence for deterministic pushdown automata, first established by G. Sénizergues, and
  • a new proof, by J. Leroux, for the decidability of accessibility in vector addition systems, or equivalently in Petri nets, first established by E. Mayr (and S. R. Kosaraju).
Our aim here is to provide an exceptional opportunity for Jančar and Leroux to provide an in-depth presentation of their proofs in front of a large audience of expert specialists as well as younger researchers interested in the field. This will be a unique occasion for the kind of interaction and attention to details that is only possible in a 3-hour tutorial format.
This sounds like a very interesting event. If you happen to be in Paris at around that time, do make a point of attending it. For those of us who cannot be there,  Jančar and Leroux have posted write-ups of their results here and here.