9 citations · 25 across the 21 of their papers we have counts for
30 papers · 1 filter
Infinite-state Games with Energy Objectives Beyond Counters
Irmak Sağlam, Georg Zetzsche
In the theory of games on infinite-state arenas, there is a stark contrast between (i) recursion-based models such as pushdown systems and extensions on one hand, and (ii) counter-…
The complexity of downward closures of indexed languages
Richard Mandel, Corto Mascle, Georg Zetzsche
Indexed languages are a classical notion in formal language theory, which has attracted attention in recent decades due to its role in higher-order model checking: They are precise…
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…
A Complexity Dichotomy for Semilinear Target Sets in Automata with One Counter
Yousef Shakiba, Henry Sinclair-Banks, Georg Zetzsche
In many kinds of infinite-state systems, the coverability problem has significantly lower complexity than the reachability problem. In order to delineate the border of computationa…
The complexity of separability for semilinear sets and Parikh automata
Elias Rojas Collins, Chris Köcher, Georg Zetzsche
In a \emph{separability problem}, we are given two sets and from a class , and we want to decide whether there exists a set from a class such…
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…