9 papers · 1 filter
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…
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-…
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…
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…
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 Power of Hard Attention Transformers on Data Sequences: A Formal Language Theoretic Perspective
Pascal BergsträÃer, Chris Köcher, Anthony Widjaja Lin +1
Formal language theory has recently been successfully employed to unravel the power of transformer encoders. This setting is primarily applicable in Natural Language Processing (NL…