I've been busy these last few years trying to get a clear
picture of the complexity of problems that arise from the use of
well-quasi-orders and well-structured transition systems. Here
is some of the material I co-authored on the subject:
A write-up on non-elementary complexity classes and
problems: Complexity Hierarchies Beyond
Elementary. Ultimately, I think the main point I try to make in the technical developments is that people should forget all the low-level details found in this paper—which are shown to have little to no impact at such high complexities—, and just use the classes without worrying.
The slides of a talk on the
subject. (Warning: those are heavy HTML5 slides.)
Highlights 2016, 14:51pm, September 8th, 2016, Université libre de Bruxelles, Brussels, Belgium.
I presented a joint work with R. Lazić on the complexity of coverability in ν-Petri nets, an extension of Petri nets with data management and creation capabilities. Here are the preprint and the slides.
ICALP 2016, 11:45am, July 12th, 2016, Sapienza University, Rome, Italy.
LICS 2016, 16:11pm, July 6th, 2016, Columbia University, New York, USA.
I presented the joint paper with R. Lazić on the complexity of coverability in ν-Petri nets, an extension of Petri nets with data management and creation capabilities. Here are the preprint and the slides.
I presented a joint work with R. Lazić on the complexity of coverability in ν-Petri nets, an extension of Petri nets with data management and creation capabilities. Here are the preprint and the slides.
Well-quasi-orders provide termination or finiteness arguments for many
algorithms, and miniaturised versions can furthermore be employed to
prove complexity upper bounds for those algorithms. We have however
an issue with these bounds: they go way beyond the familiar complexity
classes used in complexity theory. I discussed a definition of
complexity classes suitable for the task. In particular, unlike the
subrecursive classes they are based on, those classes support the
usual notions of reduction and completeness. The talk was based on the article Complexity hierarchies beyond Elementary.
Chalk talk on ideals in VAS reachability. The decidability of the reachability problem for vector addition systems is a notoriously difficult result. First shown by Mayr in 1981 after a decade of unsuccessful attempts and partial results, its proof has been simplified and refined several times, by Kosaraju and Lambert, and re-proven by very different techniques by Leroux in 2011. The principles behind the original proof remained however obscure.
In this seminar, I presented the ideas behind the algorithms of Mayr, Kosaraju, and Lambert (the KLM algorithm) in the light of ideals of well-quasi-orders. The interest here is that ideals provide a semantics to the structures manipulated in the KLM algorithm, bringing some new understanding to its proof of correctness. This approach is based on a joint work with Jérôme Leroux (LaBRI) presented at LICS'15.