We prove that the reachability problem for two-dimensional vector addition systems with
states is NL-complete or PSPACE-complete, depending on whether the numbers in the input …

Whether the reachability problem for branching vector addition systems, or equivalently the
provability problem for multiplicative exponential linear logic, is decidable has been a long …

This document is dedicated to the algorithmic complexity of well-quasi-orders, with a
particular focus on their applications in verification, where they allow to tackle systems …

We prove that non-emptiness of timed register pushdown automata is decidable in doubly
exponential time. This is a very expressive class of automata, whose transitions may involve …

We present a real-time user-independent computer vision system that processes a
sequence of images of a front-facing human face and recognises a set of facial expressions …

The resource-bounded alternating-time temporal logic RB±ATL combines strategic
reasoning with reasoning about resources. Its model-checking problem is known to be …

Vector addition systems with states (VASS) are a popular model for concurrent systems.
However, many decision problems have prohibitively high complexity. Therefore, it is …

This book is about algorithms that run on objects that are infinite, but finite up to certain
symmetries. Under a suitably chosen notion of symmetry, such objects–called orbit-finite …

This is a survey on the satisfiability problem for XPath on data trees. Data trees are finite
trees whose every node carries a label from a finite alphabet and a data value from an …

Energy and resource management problems are important in areas such as embedded
systems or autonomous systems. They are concerned with the question whether a given …