We introduce a hierarchy of fast-growing complexity classes and show its suitability for
completeness statements of many nonelementary problems. This hierarchy allows the …

We consider first-order logic over the subword ordering on finite words where each word is
available as a constant. Our first result is that the Σ 1 theory is undecidable (already over two …

Well-structured systems, aka WSTS, are computational models where the set of possible
configurations is equipped with a well-quasi-ordering which is compatible with the transition …

Elegant and general algorithms for handling upwards-closed and downwards-closed
subsets of WQOs can be developed using the filter-based and ideal-based representation …

This paper studies the boundedness and termination problems for vector addition systems
equipped with one stack. We introduce an algorithm, inspired by the Karp & Miller algorithm …

We study the reachability problem for networks of finite-state automata communicating over
unbounded perfect channels. We consider communication topologies comprising both …

Harvey Friedman's gap condition on embeddings of finite labelled trees plays an important
role in combinatorics (proof of the graph minor theorem) and mathematical logic (strong …

In automotive/avionic/robot systems, consolidating multiple domains on a powerful SoC is
an important trend. From the perspectives of safety and security, each of these domains must …

We show that the coverability problem in ν-Petri nets is complete for'double Ackermann'time,
thus closing an open complexity gap between an Ackermann lower bound and a hyper …

When a system sends messages through a lossy channel, then the language encoding all
sequences of messages can be abstracted by its downward closure, ie the set of all (not …