14 citations · 86 across the 43 of their papers we have counts for
60 papers
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…
Fast Ramsey Quantifier Elimination in LIRA (with applications to liveness checking)
Kilian Lichtner, Pascal Bergsträßer, Moses Ganardi +2
Ramsey quantifiers have recently been proposed as a unified framework for handling properties of interests in program verification involving proofs in the form of infinite cliques,…
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 Counting Power of Transformers
Marco Sälzer, Chris Köcher, Alexander Kozachinskiy +2
Counting properties (e.g. determining whether certain tokens occur more than other tokens in a given input text) have played a significant role in the study of expressiveness of tr…