4 papers
Bounded treewidth, multiple context-free grammars, and downward closures
C. Aiswarya, Pascal Baumann, Prakash Saivasan +2
The reachability problem in multi-pushdown automata (MPDA) has many applications in static analysis of recursive programs. An example is safety verification of multi-threaded recur…
Well-Quasi-Orderings on Word Languages
Nathan Lhote, Aliaume Lopez, Lia Schütze
The set of finite words over a well-quasi-ordered set is itself well-quasi-ordered. This seminal result by Higman is a cornerstone of the theory of well-quasi-orderings and has fou…
Verifying Unboundedness via Amalgamation
Ashwani Anand, Sylvain Schmitz, Lia Schütze +1
Well-structured transition systems (WSTS) are an abstract family of systems that encompasses a vast landscape of infinite-state systems. By requiring a well-quasi-ordering (wqo) on…
On the Length of Strongly Monotone Descending Chains over
Sylvain Schmitz, Lia Schütze
A recent breakthrough by Künnemann, Mazowiecki, Schütze, Sinclair-Banks, and Wegrzycki (ICALP, 2023) bounds the running time for the coverability problem in -dimensional vecto…