Georg Zetzsche
Mailing address
Georg Zetzsche
Max Planck Institute for Software Systems
Paul-Ehrlich Strasse G 26
67663 Kaiserslautern
Germany
Email
g e o r g (at) m p i - s w s . o r g
Mastodon
@gz@chaos.social
 Physical address
MPI-SWS
Room 406
Paul-Ehrlich-Str. 26
D-67663 Kaiserslautern
Germany

Since November 2018, I am a tenure-track faculty member at the Max Planck Institute for Software Systems (MPI-SWS) in Kaiserslautern, where I head the Models of Computation group.

From November 2017 until October 2018, I was a postdoc at IRIF, Université Paris-Diderot, funded by a fellowship of the Fondation Sciences Mathématiques de Paris and hosted by Olivier Serre.

From November 2015 until October 2017, I was a postdoc at the LSV Cachan, funded by a fellowship of the DAAD (German Academic Exchange Service), hosted by Philippe Schnoebelen, and the project VERICONISS by Stefan Göller.

Before that, I obtained a PhD with Prof. Dr. Roland Meyer in the Concurrency Theory Group in Kaiserslautern. I defended my dissertation on June 19th, 2015. Until December 2010, I studied Computer Science (with a minor in Mathematics) at Universität Hamburg.

My research is concerned with theoretical foundations of verification and synthesis of software systems. More specifically, I am interested in decidability and complexity issues of infinite-state systems. One current focus is synthesis of finite-state abstractions of infinite-state systems (separability problems, downward closures, Parikh images), which can be used as correctness certificates or as building blocks for decision procedures.

In addition, I am working on decision problems for infinite groups, where I seek to apply methods from verification and gain insights on how to devise infinite-state models with pleasant analysis properties.

Recent invited talks

News

Awards and Grants: Group Members: Former Members:
Publications [ back to top ]
Accepted

The Power of Hard Attention Transformers on Data Sequences: A Formal Language Theoretic Perspective
with Pascal Bergsträßer, Chris Köcher, and Anthony W. Lin
Accepted for NeurIPS 2024

Separability in Büchi VASS and Singly Non-Linear Systems of Inequalities
with Pascal Baumann, Eren Keskin, and Roland Meyer
Accepted for ICALP 2024

An efficient quantifier elimination procedure for Presburger arithmetic
with Christoph Haase, Krishna S., Khushraj Madnani, and Om Swostik Mishra
Accepted for ICALP 2024

Slice closures of indexed languages and word equations with counting constraints
with Laura Ciobanu
Accepted for LICS 2024

Verifying unboundedness via amalgamation
with Ashwani Anand, Sylvain Schmitz, and Lia Schütze
Accepted for LICS 2024

Conference contributions

Directed Regular and Context-Free Languages
with Moses Ganardi and Irmak Sağlam
Proceedings of STACS 2024
Abstract
We study the problem of deciding whether a given language is directed. A language $L$ is \emph{directed} if every pair of words in $L$ have a common (scattered) superword in $L$. Deciding directedness is a fundamental problem in connection with ideal decompositions of downward closed sets. % A language $L$ is directed if and only if the ideal %decomposition of $L$'s downward closure consists of exactly one ideal. Another motivation is that deciding whether two \emph{directed} context-free languages have the same downward closures can be decided in polynomial time, whereas for general context-free languages, this problem is known to be $\coNEXP$-complete. We show that the directedness problem for regular languages, given as NFAs, belongs to $\AC^1$, and thus polynomial time. Moreover, it is $\NL$-complete for fixed alphabet sizes. Furthermore, we show that for context-free languages, the directedness problem is $\PSPACE$-complete.

Reachability in Continuous Pushdown VASS
with A. R. Balasubramanian, Rupak Majumdar, and Ramanathan S. Thinniyam
Proceedings of POPL 2024
Abstract
Pushdown Vector Addition Systems with States (PVASS) consist of finitely many control states, a pushdown stack, and a set of counters that can be incremented and decremented, but not tested for zero. Whether the reachability problem is decidable for PVASS is a long-standing open problem. We consider continuous PVASS, which are PVASS with a continuous semantics. This means, the counter values are rational numbers and whenever a vector is added to the current counter values, this vector is first scaled with an arbitrarily chosen rational factor between zero and one. We show that reachability in continuous PVASS is NEXPTIME-complete. Our result is unusually robust: Reachability can be decided in NEXPTIME even if all numbers are specified in binary. On the other hand, NEXPTIME-hardness already holds for coverability, in fixed dimension, for bounded stack, and even if all numbers are specified in unary.

Ramsey Quantifiers in Linear Arithmetics
with Pascal Bergsträßer, Moses Ganardi, and Anthony W. Lin
Proceedings of POPL 2024
Abstract
We study Satisfiability Modulo Theories (SMT) enriched with the so-called Ramsey quantifiers, which assert the existence of cliques (complete graphs) in the graph induced by some formulas. The extended framework is known to have applications in proving program termination (in particular, whether a transitive binary predicate is well-founded), and monadic decomposability of SMT formulas. Our main result is a new algorithm for eliminating Ramsey quantifiers from three common SMT theories: Linear Integer Arithmetic (LIA), Linear Real Arithmetic (LRA), and Linear Integer Real Arithmetic (LIRA). In particular, if we work only with existentially quantified formulas, then our algorithm runs in polynomial time and produces a formula of linear size. One immediate consequence is that checking well-foundedness of a given formula in the aforementioned theory defining a transitive predicate can be straightforwardly handled by highly optimized SMT-solvers. We show also how this provides a uniform semi-algorithm for verifying termination and liveness with completeness guarantee (in fact, with an optimal computational complexity) for several well-known classes of infinite-state systems, which include succinct timed systems, one-counter systems, and monotonic counter systems. Another immediate consequence is a solution to an open problem on checking monadic decomposability of a given relation in quantifier-free fragments of LRA and LIRA, which is an important problem in automated reasoning and constraint databases. Our result immediately implies decidability of this problem with an optimal complexity (coNP-complete) and enables exploitation of SMT-solvers. It also provides a termination guarantee for the generic monadic decomposition algorithm of Veanes et al. for LIA, LRA, and LIRA. We report encouraging experimental results on a prototype implementation of our algorithms on micro-benchmarks.

Regular Separators for VASS Coverability Languages
with Chris Köcher
Proceedings of FSTTCS 2023
Abstract
We study regular separators of vector addition systems (VASS, for short) with coverability semantics. A regular language $R$ is a \emph{regular separator} of languages $K$ and $L$ if $K\subseteq R$ and $L\cap R=\emptyset$. It was shown by Czerwi\'{n}ski, Lasota, Meyer, Muskalla, Kumar, and Saivasan~(CONCUR 2018) that it is decidable whether, for two given VASS, there exists a regular separator. In fact, they show that a regular separator exists if and only if the two VASS languages are disjoint. However, they provide a triply exponential upper bound and a doubly exponential lower bound for the size of such separators and leave open which bound is tight. We show that if two VASS have disjoint languages, then there exists a regular separator with at most doubly exponential size. Moreover, we provide tight size bounds for separators in the case of fixed dimensions and unary/binary encodings of updates and NFA/DFA separators. In particular, we settle the aforementioned question. The key ingredient in the upper bound is a structural analysis of separating automata based on the concept of \emph{basic separators}, which was recently introduced by Czerwi\'{n}ski and the second author. This allows us to determinize (and thus complement) without the powerset construction and avoid one exponential blowup.

Counter Machines With Infrequent Reversals
with Alain Finkel, Krishna S., Khushraj Madnani, and Rupak Majumdar
Proceedings of FSTTCS 2023
Abstract
Bounding the number of reversals in a counter machine is one of the most prominent restrictions to achieve decidability of the reachability problem. Given this success, we explore whether this notion can be relaxed while retaining decidability. To this end, we introduce the notion of an $f$-reversal-bounded counter machine for a monotone function $f\colon \N\to \N$. In such a machine, every run of length $n$ makes at most $f(n)$ reversals. Our first main result is a dichotomy theorem: We show that for every monotone function $f$, one of the following holds: Either (i)~$f$ grows so slowly that every $f$-reversal bounded counter machine is already $k$-reversal bounded for some constant $k$ or (ii)~$f$ belongs to $\Omega(\log(n))$ and reachability in $f$-reversal bounded counter machines is undecidable. This shows that classical reversal bounding already captures the decidable cases of $f$-reversal bounding for any monotone function $f$. The key technical ingredient is an analysis of the growth of small solutions of iterated compositions of Presburger-definable constraints. In our second contribution, we investigate whether imposing $f$-reversal boundedness improves the complexity of the reachability problem in vector addition systems with states (VASS). Here, we obtain an analogous dichotomy: We show that either (i)~$f$ grows so slowly that every $f$-reversal-bounded VASS is already $k$-reversal-bounded for some constant $k$ or (ii)~$f$ belongs to $\Omega(n)$ and the reachability problem for $f$-reversal-bounded VASS remains Ackermann-complete. This result is proven using run amalgamation in VASS. Overall, our results imply that classical restriction of reversal boundedness is a robust one.

Priority Downward Closures
with Ashwani Anand
Proceedings of CONCUR 2023
Abstract
When a system sends messages through a lossy channel, then the language encoding all sequences of messages can be abstracted by its downward closure, i.e. the set of all (not necessarily contiguous) subwords. This is useful because even if the system has infinitely many states, its downward closure is a regular language. However, if the channel has congestion control based on priorities assigned to the messages, then we need a finer abstraction: The downward closure with respect to the priority embedding. As for subword-based downward closures, one can also show that these priority downward closures are always regular. While computing finite automata for the subword-based downward closure is well understood, nothing is known in the case of priorities. We initiate the study of this problem and provide algorithms to compute priority downward closures for regular languages, one-counter languages, and context-free languages.

Monus Semantics in Vector Addition Systems with States
with Pascal Baumann, Khushraj Madnani, and Filip Mazowiecki
Proceedings of CONCUR 2023
Abstract
Vector addition systems with states (VASS) are a popular model for concurrent systems. However, many decision problems have prohibitively high complexity. Therefore, it is sometimes useful to consider overapproximating semantics in which these problems can be decided more efficiently. We study an overapproximation, called monus semantics, that slightly relaxes the semantics of decrements: A key property of a vector addition systems is that in order to decrement a counter, this counter must have a positive value. In contrast, our semantics allows decrements of zero-valued counters: If such a transition is executed, the counter just remains zero. It turns out that if only a subset of transitions is used with monus semantics (and the others with classical semantics), then reachability is undecidable. However, we show that if monus semantics is used throughout, reachability remains decidable. In particular, we show that reachability for VASS with monus semantics is as hard as that of classical VASS (i.e. Ackermann-hard), while the zero-reachability and coverability are easier (i.e. EXPSPACE-complete and NP-complete, respectively). We provide a comprehensive account of the complexity of the general reachability problem, reachability of zero configurations, and coverability under monus semantics. We study these problems in general VASS, two-dimensional VASS, and one-dimensional VASS, with unary and binary counter updates.

Context-Bounded Analysis of Concurrent Programs (Invited Talk)
with Pascal Baumann, Moses Ganardi, Rupak Majumdar, and Ramanathan S. Thinniyam
Proceedings of ICALP 2023
Abstract
Context-bounded analysis of concurrent programs is a technique to compute a sequence of under-approximations of all behaviors of the program. For a fixed bound k, a context bounded analysis considers only those runs in which a single process is interrupted at most k times. As k grows, we capture more and more behaviors of the program. Practically, context-bounding has been very effective as a bug-finding tool: many bugs can be found even with small bounds. Theoretically, context-bounded analysis is decidable for a large number of programming models for which verification problems are undecidable. In this paper, we survey some recent work in context-bounded analysis of multithreaded programs. In particular, we show a general decidability result. We study context-bounded reachability in a language-theoretic setup. We fix a class of languages (satisfying some mild conditions) from which each thread is chosen. We show context-bounded safety and termination verification problems are decidable iff emptiness is decidable for the underlying class of languages and context-bounded boundedness is decidable iff finiteness is decidable for the underlying class.

Checking Refinement of Asynchronous Programs against Context-Free Specifications
with Pascal Baumann, Moses Ganardi, Rupak Majumdar, and Ramanathan S. Thinniyam
Proceedings of ICALP 2023
Abstract
In the language-theoretic approach to refinement verification, we check that the language of traces of an implementation all belong to the language of a specification. We consider the refinement verification problem for asynchronous programs against specifications given by a Dyck language. We show that this problem is EXPSPACE-complete---the same complexity as that of language emptiness and for refinement verification against a regular specification. Our algorithm uses several technical ingredients. First, we show that checking if the coverability language of a succinctly described vector addition system with states (VASS) is contained in a Dyck language is EXPSPACE-complete. Second, in the more technical part of the proof, we define an ordering on words and show a downward closure construction that allows replacing the (context-free) language of each task in an asynchronous program by a regular language. Unlike downward closure operations usually considered in infinite-state verification, our ordering is not a well-quasi-ordering, and we have to construct the regular language ab initio. Once the tasks can be replaced, we show a reduction to an appropriate VASS and use our first ingredient. In addition to the inherent theoretical interest, refinement verification with Dyck specifications captures common practical resource usage patterns based on reference counting, for which few algorithmic techniques were known.

Unboundedness problems for machines with reversal-bounded counters
with Pascal Baumann, Flavio D'Alessandro, Oscar Ibarra, Moses Ganardi, Ian McQuillan, and Lia Schütze
Proceedings of FoSSaCS 2023
EATCS Best Paper Award at ETAPS 2023
Abstract
We consider a general class of decision problems concerning formal languages, called ``(one-dimensional) unboundedness predicates'', for automata that feature reversal-bounded counters (RBCA). We show that each problem in this class reduces -- non-deterministically in polynomial time -- to the same problem for just finite automata. We also show an analogous reduction for automata that have access to both a pushdown stack and reversal-bounded counters (PRBCA). This allows us to answer several open questions: For example, we show that it is coNP-complete to decide whether a given (P)RBCA language L is bounded, meaning whether there exist words $w_1,\ldots,w_n$ with $L\subseteq w_1^*w_2^*\cdots w_n^*$. For PRBCA, even decidability was open. Our methods also show that there is no language of a (P)RBCA of intermediate growth. This means, the number of words of each length grows either polynomially or exponentially. Part of our proof is likely of independent interest: We show that one can translate an RBCA into a machine with Z-counters in logarithmic space, while preserving the accepted language.

Regular Separability in Büchi VASS
with Pascal Baumann and Roland Meyer
Proceedings of STACS 2023
Abstract
We study the regular separability problem for Büchi VASS languages: Given two Büchi VASS with languages $L_1$ and $L_2$, check whether there is a regular language that fully contains $L_1$ while remaining disjoint from $L_2$. We show that the problem is decidable in general and PSPACE-complete in the 1-dimensional case, assuming succinct counter updates. The results rely on several arguments. We characterize the set of all regular languages disjoint from $L_2$. Based on this, we derive a (sound and complete) notion of inseparability witnesses, non-regular subsets of $L_1$. Finally, we show how to symbolically represent inseparability witnesses and how to check their existence.

Context-Bounded Verification of Context-Free Specifications
with Pascal Baumann, Moses Ganardi, Rupak Majumdar, and Ramanathan S. Thinniyam
Proceedings of POPL 2023
Abstract
A fundamental problem in refinement verification is to check that the language of behaviors of an implementation is included in the language of the specification. We consider the refinement verification problem where the implementation is a multithreaded shared memory system modeled as a multistack pushdown automaton and the specification is an input-deterministic multistack pushdown language. Our main result shows that the context-bounded refinement problem, where we ask that all behaviors generated in runs of bounded number of context switches belong to a specification given by a Dyck language, is decidable and coNP-complete. The more general case of input-deterministic languages follows, with the same complexity. Context-bounding is essential since emptiness for multipushdown automata is already undecidable, and so is the refinement verification problem for the subclass of regular specifications. Input-deterministic languages capture many non-regular specifications of practical interest and our result opens the way for algorithmic analysis of these properties. The context-bounded refinement problem is coNP-hard already with deterministic regular specifications; our result demonstrates that the problem is not harder despite the stronger class of specifications. Our proof introduces several general techniques for formal languages and counter programs and shows that the search for counterexamples can be reduced in non-deterministic polynomial time to the satisfiability problem for existential Presburger arithmetic. These techniques are essential to ensure the coNP upper bound: existing techniques for regular specifications are not powerful enough for decidability, while simple reductions lead to problems that are either undecidable or have high complexities. As a special case, our decidability result gives an algorithmic verification technique to reason about reference counting and re-entrant locking in multithreaded programs.

Membership problems in finite groups
with Markus Lohrey and Andreas Rosowski
Proceedings of MFCS 2022
Abstract
We show that the subset sum problem, the knapsack problem and the rational subset membership problem for permutation groups are NP-complete. Concerning the knapsack problem we obtain NP-completeness for every fixed n \geq 3, where n is the number of permutations in the knapsack equation. In other words: membership in products of three cyclic permutation groups is NP-complete. This sharpens a result of Luks, which states NP-completeness of the membership problem for products of three abelian permutation groups. We also consider the context-free membership problem in permutation groups and prove that it is PSPACE-complete but NP-complete for a restricted class of context-free grammars where acyclic derivation trees must have constant Horton-Strahler number. Our upper bounds hold for black box groups. The results for context-free membership problems in permutation groups yield new complexity bounds for various intersection non-emptiness problems for DFAs and a single context-free grammar.

Reachability in Bidirected Pushdown VASS
with Moses Ganardi, Rupak Majumdar, Andreas Pavlogiannis, and Lia Schütze
Proceedings of ICALP 2022
Abstract
A pushdown vector addition system with states (PVASS) extends the model of vector addition systems with a pushdown store. A PVASS is said to be bidirected if every transition (pushing/popping a symbol or modifying a counter) has an accompanying opposite transition that reverses the effect. Bidirectedness arises naturally in many models; it can also be seen as a overapproximation of reachability. We show that the reachability problem for bidirected PVASS is decidable in Ackermann time and primitive recursive for any fixed dimension. For the special case of one-dimensional bidirected PVASS, we show reachability is in PSPACE, and in fact in polynomial time if the stack is polynomially bounded. Our results are in contrast to the directed setting, where decidability of reachability is a long-standing open problem already for one dimensional PVASS, and there is a PSPACE-lower bound already for one-dimenstional PVASS with bounded stack. The reachability relation in the bidirected (stateless) case is a congruence over N^d. Our upper bounds exploit saturation techniques over congruences. In particular, we show novel elementary-time constructions of semilinear representations of congruences generated by finitely many vector pairs. For the special case of one-dimensional PVASS, we show a saturation procedure over bounded-size counters. We complement our upper bound with a TOWER-hardness result for arbitrary dimension and k-EXPSPACE hardness in dimension 2k+6 using a technique by Lazić and Totzke to implement iterative exponentiations.

The complexity of bidirected reachability in valence systems
with Moses Ganardi and Rupak Majumdar
Proceedings of LICS 2022
Abstract
Reachability problems in infinite-state systems are often subject to extremely high complexity. This motivates the investigation of efficient overapproximations, where we add transitions to obtain a system in which reachability can be decided more easily. We consider bidirected infinite-state systems, where for every transition there is a transition with opposite effect. We study bidirected reachability in the framework of valence systems, an abstract model featuring finitely many control states and an infinite-state storage that is specified by a finite graph. By picking suitable graphs, valence systems can uniformly model counters as in vector addition systems, pushdowns, integer counters, and combinations thereof. We provide a comprehensive complexity landscape for bidirected reachability and show that the complexity drops substantially (often to polynomial time) from that of general reachability, for almost every storage mechanism where reachability is known to be decidable.

Ramsey Quantifiers over Automatic Structures: Complexity and Applications to Verification
with Pascal Bergsträßer, Moses Ganardi, and Anthony W. Lin
Proceedings of LICS 2022
Abstract
Automatic structures are infinite structures that are finitely represented by synchronized finite-state automata. This paper concerns specifically automatic structures over finite words and trees (ranked/unranked). We investigate the ``directed version'' of Ramsey quantifiers, which express the existence of an infinite directed clique. This subsumes the standard ``undirected version'' of Ramsey quantifiers. Interesting connections between Ramsey quantifiers and two problems in verification are firstly observed: (1) reachability with Büchi and generalized Büchi conditions in regular model checking can be seen as Ramsey quantification over transitive automatic graphs (i.e. whose edge relations are transitive), (2) checking monadic decomposability (a.k.a. recognizability) of automatic relations can be viewed as Ramsey quantification over co-transitive automatic graphs (i.e. the complements of whose edge relations are transitive). We provide a comprehensive complexity landscape of Ramsey quantifiers in these three cases (general, transitive, co-transitive), all between NL and EXP. In turn, this yields a wealth of new results with precise complexity, e.g., verification of subtree/flat prefix rewriting, as well as monadic decomposability over tree-automatic relations. We also obtain substantially simpler proofs, e.g., for NL complexity for monadic decomposability over word-automatic relations (given by DFAs).

Existential definability over the subword ordering
with Pascal Baumann, Moses Ganardi, and Ramanathan S. Thinniyam
Proceedings of STACS 2022
Abstract
We study first-order logic (FO) over the structure consisting of finite words over some alphabet~$A$, together with the (non-contiguous) subword ordering. In terms of decidability of quantifier alternation fragments, this logic is well-understood: If every word is available as a constant, then even the $\Sigma_1$ (i.e.\ existential) fragment is undecidable, already for binary alphabets $A$. However, up to now, little is known about the expressiveness of the quantifier alternation fragments: For example, the undecidability proof for the existential fragment relies on Diophantine equations and only shows that recursively enumerable languages over a singleton alphabet (and some auxiliary predicates) are definable. We show that if $|A|\ge 3$, then a relation is definable in the existential fragment over $A$ with constants if and only if it is recursively enumerable. This implies characterizations for all fragments~$\Sigma_i$: If $|A|\ge 3$, then a relation is definable in $\Sigma_i$ if and only if it belongs to the $i$-th level of the arithmetical hierarchy. In addition, our result yields an analogous complete description of the $\Sigma_i$-fragments for $i\ge 2$ of the pure logic, where the words of $A^*$ are not available as constants.

Context-Bounded Verification of Thread Pools
with Pascal Baumann, Rupak Majumdar, and Ramanathan S. Thinniyam
Proceedings of POPL 2022
Abstract
Thread pooling is a common programming idiom in which a fixed set of worker threads are maintained to execute tasks concurrently. The workers repeatedly pick tasks and execute them to completion. Each task is sequential, with possibly recursive code, and tasks communicate over shared memory. Executing a task can lead to more new tasks being spawned. We consider the safety verification problem for thread-pooled programs. We parameterize the problem with two parameters: the size of the thread pool as well as the number of context switches for each task. The size of the thread pool determines the number of workers running concurrently. The number of context switches determines how many times a worker can be swapped out while executing a single task---like many verification problems for multithreaded recursive programs, the context bounding is important for decidability. We show that the safety verification problem for thread-pooled, context-bounded, Boolean programs is EXPSPACE-complete, even if the size of the thread pool and the context bound are given in binary. Our main result, the EXPSPACE upper bound, is derived using a sequence of new succinct encoding techniques of independent language-theoretic interest. In particular, we show a polynomial-time construction of downward closures of languages accepted by succinct pushdown automata as doubly succinct nondeterministic finite automata. While there are explicit doubly exponential lower bounds on the size of nondeterministic finite automata accepting the downward closure, our result shows these automata can be compressed. We show that thread pooling significantly reduces computational power: in contrast, if only the context bound is provided in binary, but there is no thread pooling, the safety verification problem becomes 3EXPSPACE-complete. Given the high complexity lower bounds of related problems involving binary parameters, the relatively low complexity of safety verification with thread-pooling comes as a surprise.

Recent Advances on Reachability Problems for Valence Systems (Invited Talk)
Proceedings of RP 2021
Abstract
Valence systems are an abstract model of computation that consists of a finite-state control and some storage mechanism. In contrast to traditional models, the storage mechanism is not fixed, but given as a parameter. This allows us to precisely state questions like: For which storage mechanisms is the reachability problem decidable? This survey reports on recent results that aim to understand the impact of the storage mechanism on decidability and complexity of several variants of the reachability problem. The considered problems are configuration reachability, model-checking first-order logic with reachability, and reachability under bounded context switching and scope-boundedness.

General Decidability Results for Asynchronous Shared-Memory Programs: Higher-Order and Beyond
with Rupak Majumdar and Ramanathan S. Thinniyam
Proceedings of TACAS 2021
EAPLS Best Paper Award at ETAPS 2021
Abstract
The model of asynchronous programming arises in many contexts, from low-level systems software to high-level web programming. We take a language-theoretic perspective and show general decidability and undecidabilit y results for asynchronous programs that capture all known results as well as show decidability of new and important classes. As a main consequence, we show decidability of safety, termination and boundedness verification for \emph{higher-order} asynchronous programs---such as OCaml programs using Lwt---and undecidability of liveness verification already for order-2 asynchronous programs. We show that, surprisingly, safety and termination verification of asynchronous programs with handlers from a language class are decidable \emph{if{}f} emptiness is decidable for the underlying language class. Moreover, we show that configuration reachability and liveness (fair termination) verification are equivalent, and decidability of these problems implies decidability of the well-known ``equal-letters'' problem on languages. Our results close the decidability frontier for asynchronous programs.

Scope-Bounded Reachability in Valence Systems
with Aneesh Shetty and Krishna S.
Proceedings of CONCUR 2021
Abstract
Multi-pushdown systems are a standard model for concurrent recursive programs, but they have an undecidable reachability problem. Therefore, there have been several proposals to underapproximate their sets of runs so that reachability in this underapproximation becomes decidable. One such underapproximation that covers a relatively high portion of runs is scope boundedness. In such a run, after each push to stack i, the corresponding pop operation must come within a bounded number of visits to stack i. In this work, we generalize this approach to a large class of infinite-state systems. For this, we consider the model of valence systems, which consist of a finite-state control and an infinite-state storage mechanism that is specified by a finite undirected graph. This framework captures pushdowns, vector addition systems, integer vector addition systems, and combinations thereof. For this framework, we propose a notion of scope boundedness that coincides with the classical notion when the storage mechanism happens to be a multi-pushdown. We show that with this notion, reachability can be decided in PSPACE for every storage mechanism in the framework. Moreover, we describe the full complexity landscape of this problem across all storage mechanisms, both in the case of (i) the scope bound being given as input and (ii) for fixed scope bounds. Finally, we provide an almost complete description of the complexity landscape if even a description of the storage mechanism is part of the input.

A characterization of wreath products where knapsack is decidable
with Pascal Bergsträßer and Moses Ganardi
Proceedings of STACS 2021
Abstract
The knapsack problem for groups was introduced by Miasnikov, Nikolaev, and Ushakov. It is defined for each finitely generated group $G$ and takes as input group elements $g_1,\ldots,g_n,g\in G$ and asks whether there are $x_1,\ldots,x_n\ge 0$ with $g_1^{x_1}\cdots g_n^{x_n}=g$. We study the knapsack problem for wreath products $G\wr H$ of groups $G$ and $H$. Our main result is a characterization of those wreath products $G\wr H$ for which the knapsack problem is decidable. The characterization is in terms of decidability properties of the indiviual factors $G$ and $H$. To this end, we introduce two decision problems, the \emph{intersection knapsack problem} and its restriction, the \emph{positive intersection knapsack problem}. Moreover, we apply our main result to $H_3(\Z)$, the discrete Heisenberg group, and to Baumslag-Solitar groups $\BS(1,q)$ for $q\ge 1$. First, we show that the knapsack problem is undecidable for $G\wr H_3(\Z)$ for any $G\ne 1$. This implies that for $G\ne 1$ and for infinite and virtually nilpotent groups $H$, the knapsack problem for $G\wr H$ is decidable if and only if $H$ is virtually abelian and solvability of systems of exponent equations is decidable for $G$. Second, we show that the knapsack problem is decidable for $G\wr\BS(1,q)$ if and only if solvability of systems of exponent equations is decidable for $G$.

Context-Bounded Verification of Liveness Properties for Multithreaded Shared-Memory Programs
with Pascal Baumann, Rupak Majumdar, and Ramanathan S. Thinniyam
Proceedings of POPL 2021
Distinguished Paper Award
Abstract
We study context-bounded verification of liveness properties of multi-threaded, shared-memory programs, where each thread can spawn additional threads. Our main result shows that context-bounded fair termination is decidable for the model; context-bounded implies that each spawned thread can be context switched a fixed constant number of times. Our proof is technical, since fair termination requires reasoning about the composition of unboundedly many threads each with unboundedly large stacks. In fact, techniques for related problems, which depend crucially on replacing the pushdown threads with finite-state threads, are not applicable. Instead, we introduce an extension of vector addition systems with states (VASS), called VASS with balloons (VASSB), as an intermediate model; it is an infinite-state model of independent interest. A VASSB allows tokens that are themselves markings (balloons). We show that context bounded fair termination reduces to fair termination for VASSB. We show the latter problem is decidable by showing a series of reductions: from fair termination to configuration reachability for VASSB and thence to the reachability problem for VASS. For a lower bound, fair termination is known to be non-elementary already in the special case where threads run to completion (no context switches). We also show that the simpler problem of context-bounded termination is 2EXPSPACE-complete, matching the complexity bound---and indeed the techniques---for safety verification. Additionally, we show the related problem of \emph{fair starvation}, which checks if some thread can be starved along a fair run, is also decidable in the context-bounded case. The decidability employs an intricate reduction from fair starvation to fair termination. Like fair termination, this problem is also non-elementary.

Knapsack and the power word problem in solvable Baumslag-Solitar groups
with Markus Lohrey
Proceedings of MFCS 2020

The complexity of bounded context switching with dynamic thread creation
with Pascal Baumann, Rupak Majumdar, and Ramanathan S. Thinniyam
Proceedings of ICALP 2020

Rational subsets of Baumslag-Solitar groups
with Michaël Cadilhac and Dmitry Chistikov
Proceedings of ICALP 2020

The complexity of knapsack problems in wreath products
with Michael Figelius, Moses Ganardi, and Markus Lohrey
Proceedings of ICALP 2020

Extensions of Omega-Regular Languages
with Mikołaj Bojańczyk, Edon Kelmendi, and Rafał Stefański
Proceedings of LICS 2020
Abstract
We consider extensions of monadic second order logic over $\omega$-words, which are obtained by adding one language that is not $\omega$-regular. We show that if the added language $L$ has a neutral letter, then the resulting logic is necessarily undecidable. A corollary is that the $\omega$-regular languages are the only decidable Boolean-closed full trio over $\omega$-words.

An Approach to Regular Separability in Vector Addition Systems
with Wojciech Czerwiński
Proceedings of LICS 2020
Abstract
We study the problem of regular separability of languages of vector addition systems with states (VASS). It asks whether for two given VASS languages $K$ and $L$, there exists a regular language $R$ that includes $K$ and is disjoint from $L$. While decidability of the problem in full generality remains an open question, there are several subclasses for which decidability has been shown: It is decidable for (i)~one-dimensional VASS, (ii)~VASS coverability languages, (iii)~languages of integer VASS, and (iv)~commutative VASS languages. We propose a general approach to deciding regular separability. We use it to decide regular separability of an arbitrary VASS language from any language in the classes~(i), (ii), and~(iii). This generalizes all previous results, including~(iv).

Regular Separability and Intersection Emptiness are Independent Problems
with Ramanathan S. Thinniyam
Proceedings of FSTTCS 2019

Coverability Is Undecidable in One-Dimensional Pushdown Vector Addition Systems with Resets
with Sylvain Schmitz
Proceedings of RP 2019
Abstract
We consider the model of pushdown vector addition systems with resets. These consist of vector addition systems that have access to a pushdown stack and have instructions to reset counters. For this model, we study the coverability problem. In the absence of resets, this problem is known to be decidable for one-dimensional pushdown vector addition systems, but decidability is open for general pushdown vector addition systems. Moreover, coverability is known to be decidable for reset vector addition systems without a pushdown stack. We show in this note that the problem is undecidable for one-dimensional pushdown vector addition systems with resets.

Presburger arithmetic with stars, rational subsets of graph groups, and nested zero tests
with Christoph Haase
Proceedings of LICS 2019
Abstract
We study the computational complexity of existential Presburger arithmetic with (possibly nested occurrences of) a Kleene-star operator. In addition to being a natural extension of Presburger arithmetic, our investigation is motivated by two other decision problems.
The first problem is the rational subset membership problem in graph groups. A graph group is an infinite group specified by a finite undirected graph. While a characterisation of graph groups with a decidable rational subset membership problem was given by Lohrey and Steinberg [J. Algebra, 320(2) (2008)], it has been an open problem (i) whether the decidable fragment has elementary complexity and (ii) what is the complexity for each fixed graph group. The second problem is the reachability problem for integer vector addition systems with states and nested zero tests.
We prove that the satisfiability problem for existential Presburger arithmetic with stars is NEXP-complete and that all three problems are polynomially inter-reducible. Moreover, we consider for each problem a variant with a fixed parameter: We fix the star-height in the logic, the group for the membership problem, and the number of distinct zero-tests in the integer vector addition systems. We establish NP-completeness of all problems with fixed parameters.
In particular, this enables us to obtain a complete description of the complexity landscape of the rational subset membership problem for fixed graph groups: If the graph is a clique, the problem is NL-complete. If the graph is a disjoint union of cliques, it is PTIME-complete. If it is a transitive forest (and not a union of cliques), the problem is NP-complete. Otherwise, the problem is undecidable.

Languages ordered by the subword order
with Dietrich Kuske
Proceedings of FoSSaCS 2019
Abstract
We consider a language together with the subword relation, the cover relation, and regular predicates. For such structures, we consider the extension of first-order logic by threshold- and modulo-counting quantifiers. Depending on the language, the used predicates, and the fragment of the logic, we determine four new combinations that yield decidable theories. These results extend earlier ones where only the language of all words without the cover relation and fragments of first-order logic were considered.

Bounded Context Switching for Valence Systems
with Roland Meyer and Sebastian Muskalla
Proceedings of CONCUR 2018
Abstract
We study valence systems, finite-control programs over infinite-state memories modeled in terms of graph monoids. Our contribution is a notion of bounded context switching (BCS). Valence systems generalize pushdowns, concurrent pushdowns, and Petri nets. In these settings, our definition conservatively generalizes existing notions. The main finding is that reachability within a bounded number of context switches is in $\NPTIME$, independent of the memory (the graph monoid). Our proof is genuinely algebraic, and therefore contributes a new way to think about BCS.

Unboundedness problems for languages of vector addition systems
with Wojciech Czerwiński and Piotr Hofman
Proceedings of ICALP 2018
Abstract
A vector addition system (VAS) with an initial and a final marking and transition labels induces a language. In part because the reachability problem in VAS remains far from being well-understood, it is difficult to devise decision procedures for such languages. This is especially true for checking properties that state the existence of infinitely many words of a particular shape. Informally, we call these \emph{unboundedness properties}. We present a simple set of axioms for predicates that can express unboundedness properties. Our main result is that such a predicate is decidable for VAS languages as soon as it is decidable for regular languages. Among other results, this allows us to show decidability of (i)~separability by bounded regular languages, (ii)~unboundedness of occurring factors from a language $K$ with mild conditions on $K$, and (iii)~universality of the set of factors.

Separability by piecewise testable languages and downward closures beyond subwords
Proceedings of LICS 2018
Abstract
We introduce a flexible class of well-quasi-orderings (WQOs) on words that generalizes the ordering of (not necessarily contiguous) subwords. Each such WQO induces a class of piecewise testable languages (PTLs) as Boolean combinations of upward closed sets. In this way, a range of regular language classes arises as PTLs. Moreover, each of the WQOs guarantees regularity of all downward closed sets.
We consider two problems. First, we study which (perhaps non-regular) language classes allow to decide whether two given languages are separable by a PTL with respect to a given WQO. Second, we want to effectively compute downward closures with respect to these WQOs.
Our first main result is that for each of the WQOs, under mild assumptions, both problems reduce to the simultaneous unboundedness problem (SUP) and are thus solvable for many powerful system models. In the second main result, we apply the framework to show decidability of separability of regular languages by $\mathcal{B}\Sigma_1[<, \mathsf{mod}]$, a fragment of first-order logic with modular predicates.

Knapsack problems for wreath products
with Moses Ganardi, Daniel König, and Markus Lohrey
Proceedings of STACS 2018
Abstract
In recent years, knapsack problems for (in general non-commutative) groups have attracted attention. In this paper, the knapsack problem for wreath products is studied. It turns out that decidability of knapsack is not preserved under wreath product. On the other hand, the class of knapsack-semilinear groups, where solutions sets of knapsack equations are effectively semilinear, is closed under wreath product. As a consequence, we obtain the decidability of knapsack for free solvable groups. Finally, it is shown that for every non-trivial abelian group $G$, knapsack (as well as the related subset sum problem) for the wreath product $G \wr \Z$ is $\NP$-complete.

Decidability, Complexity, and Expressiveness of First-Order Logic Over the Subword Ordering
with Simon Halfon and Philippe Schnoebelen
Proceedings of LICS 2017
Abstract
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 $\Sigma_1$ theory is undecidable (already over two letters).
We investigate the decidability border by considering fragments where all but a certain number of variables are alternation bounded, meaning that the variable must always be quantified over languages with a bounded number of letter alternations. We prove that when at most two variables are not alternation bounded, the $\Sigma_1$ fragment is decidable, and that it becomes undecidable when three variables are not alternation bounded. Regarding higher quantifier alternation depths, we prove that the $\Sigma_2$ fragment is undecidable already for one variable without alternation bound and that when all variables are alternation bounded, the entire first-order theory is decidable.

The Complexity of Knapsack in Graph Groups
with Markus Lohrey
Proceedings of STACS 2017
Abstract
Myasnikov et al. have introduced the knapsack problem for arbitrary finitely generated groups. In previous work, the authors proved that for each graph group, the knapsack problem can be solved in NP. Here, we determine the exact complexity of the problem for every graph group. While the problem is TC0-complete for complete graphs, it is LogCFL-complete for each (non-complete) transitive forest. For every remaining graph, the problem is NP-complete.

Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
with Daniel König and Markus Lohrey
Proceedings of AMS Special Session on Groups, Algorithms, and Cryptography (San Antonio, Texas, 2015)

The Complexity of Downward Closure Comparisons
Proceedings of ICALP 2016
Abstract
The downward closure of a language is the set of all (not necessarily contiguous) subwords of its members. It is well-known that the downward closure of every language is regular. Moreover, recent results show that downward closures are computable for quite powerful system models.
One advantage of abstracting a language by its downward closure is that then, equivalence and inclusion become decidable. In this work, we study the complexity of these two problems. More precisely, we consider the following decision problems: Given languages $K$ and $L$ from classes $\C$ and $\D$, respectively, does the downward closure of $K$ include (equal) that of $L$?
These problems are investigated for finite automata, one-counter automata, context-free grammars, and reversal-bounded counter automata. For each combination, we prove a completeness result either for fixed or for arbitrary alphabets. Moreover, for Petri net languages, we show that both problems are Ackermann-hard and for higher-order pushdown automata of order $k$, we prove hardness for complements of nondeterministic $k$-fold exponential time.

The complexity of regular abstractions of one-counter languages
with Mohamed Faouzi Atig, Dmitry Chistikov, Piotr Hofman, K Narayan Kumar, and Prakash Saivasan
Proceedings of LICS 2016
Abstract
We study the computational and descriptional complexity of the following transformation: Given a one-counter automaton (OCA) A, construct a nondeterministic finite automaton (NFA) B that recognizes an abstraction of the language of A: its (1) downward closure, (2) upward closure, or (3) Parikh image. For the Parikh image over a fixed alphabet and for the upward and downward closures, we find polynomial-time algorithms that compute such an NFA. For the Parikh image with the alphabet as part of the input, we find a quasi-polynomial time algorithm and prove a completeness result: we construct a sequence of OCA that admits a polynomial-time algorithm iff there is one for all OCA. For all three abstractions, it was previously unknown if appropriate NFA of sub-exponential size exist.

First-order logic with reachability for infinite-state systems
with Emanuele D'Osualdo and Roland Meyer
Proceedings of LICS 2016
Abstract
First-order logic with the reachability predicate (FOR) is an important means of specification in system analysis. Its decidability status is known for some individual types of infinite-state systems such as pushdown (decidable) and vector addition systems (undecidable). This work aims at a general understanding of which types of systems admit decidability. As a unifying model, we employ valence systems over graph monoids, which feature a finite-state control and are parameterized by a monoid to represent their storage mechanism. As special cases, this includes pushdown systems, various types of counter systems (such as vector addition systems) and combinations thereof. Our main result is a complete characterization of those graph monoids where FOR is decidable for the resulting transition systems.

Knapsack in Graph Groups, HNN-Extensions and Amalgamated Products
with Markus Lohrey
Proceedings of STACS 2016
Abstract
It is shown that the knapsack problem, which was introduced by Myasnikov et al. for arbitrary finitely generated groups, can be solved in NP for graph groups. This result even holds if the group elements are represented in a compressed form by SLPs, which generalizes the classical NP-completeness result of the integer knapsack problem. We also prove general transfer results: NP-membership of the knapsack problem is passed on to finite extensions, HNN-extensions over finite associated subgroups, and amalgamated products with finite identified subgroups.

The Emptiness Problem for Valence Automata or: Another Decidable Extension of Petri Nets
Proceedings of RP 2015
Abstract
This work studies which storage mechanisms in automata permit decidability of the reachability problem. The question is formalized using valence automata, an abstract model that generalizes automata with storage. For each of a variety of storage mechanisms, one can choose a (typically infinite) monoid $M$ such that valence automata over $M$ are equivalent to (one-way) automata with this type of storage.
In fact, many interesting storage mechanisms can be realized by monoids defined by finite graphs, called graph monoids. Hence, we study for which graph monoids the emptiness problem for valence automata is decidable. A particular model realized by graph monoids is that of Petri nets with a pushdown stack. For these, decidability is a long-standing open question and we do not answer it here.
However, if one excludes subgraphs corresponding to this model, a characterization can be achieved. This characterization yields a new extension of Petri nets with a decidable reachability problem. Moreover, we provide a description of those storage mechanisms for which decidability remains open. This leads to a natural model that generalizes both pushdown Petri nets and priority multicounter machines.

An Approach to Computing Downward Closures
Proceedings of ICALP 2015
Best Student Paper Award in Track B
Abstract
The downward closure of a word language is the set of all (not necessarily contiguous) subwords of its members. It is well-known that the downward closure of any language is regular. While the downward closure appears to be a powerful abstraction, algorithms for computing a finite automaton for the downward closure of a given language have been established only for few language classes.
This work presents a simple general method for computing downward closures. For language classes that are closed under rational transductions, it is shown that the computation of downward closures can be reduced to checking a certain unboundedness property.
This result is used to prove that downward closures are computable for (i) every language class with effectively semilinear Parikh images that are closed under rational transductions, (ii) matrix languages, and (iii) indexed languages (equivalently, languages accepted by higher-order pushdown automata of order~2).

Computing downward closures for stacked counter automata
Proceedings of STACS 2015
Abstract
The downward closure of a language $L$ of words is the set of all (not necessarily contiguous) subwords of members of $L$. It is well known that the downward closure of any language is regular. Although the downward closure seems to be a promising abstraction, there are only few language classes for which an automaton for the downward closure is known to be computable.
It is shown here that for stacked counter automata, the downward closure is computable. Stacked counter automata are finite automata with a storage mechanism obtained by \emph{adding blind counters} and \emph{building stacks}. Hence, they generalize pushdown and blind counter automata.
The class of languages accepted by these automata are precisely those in the hierarchy obtained from the context-free languages by alternating two closure operators: imposing semilinear constraints and taking the algebraic extension. The main tool for computing downward closures is the new concept of Parikh annotations. As a second application of Parikh annotations, it is shown that the hierarchy above is strict at every level.

The Monoid of Queue Actions
with Martin Huschenbett and Dietrich Kuske
Proceedings of MFCS 2014
Abstract
We investigate the monoid of transformations that are induced by sequences of writing to and reading from a queue storage. We describe this monoid by means of a confluent and terminating semi-Thue system and study some of its basic algebraic properties, e.g., conjugacy. Moreover, we show that while several properties concerning its rational subsets are undecidable, their uniform membership problem is NL-complete. Furthermore, we present an algebraic characterization of this monoid's recognizable subsets. Finally, we prove that it is not Thurston-automatic.

On Boolean closed full trios and rational Kripke frames
with Markus Lohrey
Proceedings of STACS 2014
Abstract
A Boolean closed full trio is a class of languages that is closed under the Boolean operations (union, intersection, and complementation) and rational transductions. It is well-known that the regular languages constitute such a Boolean closed full trio. It is shown here that every such language class that contains any non-regular language already includes the whole arithmetical hierarchy (and even the one relative to this language).
A consequence of this result is that aside from the regular languages, no full trio generated by one language is closed under complementation.
Our construction also shows that there is a fixed rational Kripke frame such that assigning an arbitrary non-regular language to some variable allows the definition of any language from the arithmetical hierarchy in the corresponding Kripke structure using multimodal logic.

Semilinearity and Context-Freeness of Languages Accepted by Valence Automata
with Phoebe Buckheister
Proceedings of MFCS 2013
Abstract
Valence automata are a generalization of various models of automata with storage. Here, each edge carries, in addition to an input word, an element of a monoid. A computation is considered valid if multiplying the monoid elements on the visited edges yields the identity element. By choosing suitable monoids, a variety of automata models can be obtained as special valence automata. This work is concerned with the accepting power of valence automata. Specifically, we ask for which monoids valence automata can accept only context-free languages or only languages with semilinear Parikh image, respectively. First, we present a characterization of those graph products (of monoids) for which valence automata accept only context-free languages. Second, we provide a necessary and sufficient condition for a graph product of copies of the bicyclic monoid and the integers to yield only languages with semilinear Parikh image when used as a storage mechanism in valence automata. Third, we show that all languages accepted by valence automata over torsion groups have a semilinear Parikh image.

Rational Subsets and Submonoids of Wreath Products
with Markus Lohrey and Benjamin Steinberg
Proceedings of ICALP 2013
Abstract
It is shown that membership in rational subsets of wreath products $H \wr V$ with $H$ a finite group and $V$ a virtually free group is decidable. On the other hand, it is shown that there exists a fixed finitely generated submonoid in the wreath product $\mathbb{Z}\wr\mathbb{Z}$ with an undecidable membership problem.

Silent Transitions in Automata with Storage
Proceedings of ICALP 2013
Abstract
We consider the computational power of silent transitions in one-way automata with storage. Specifically, we ask which storage mechanisms admit a transformation of a given automaton into one that accepts the same language and reads at least one input symbol in each step.
We study this question using the model of valence automata. Here, a finite automaton is equipped with a storage mechanism that is given by a monoid.
This work presents generalizations of known results on silent transitions. For two classes of monoids, it provides characterizations of those monoids that allow the removal of silent transitions. Both classes are defined by graph products of copies of the bicyclic monoid and the group of integers. The first class contains pushdown storages as well as the blind counters while the second class contains the blind and the partially blind counters.

A Sufficient Condition for Erasing Productions to Be Avoidable
Proceedings of DLT 2011
Abstract
In each grammar model, it is an important question whether erasing productions are necessary to generate all languages. Using the concept of grammars with control languages by Salomaa, which offers a uniform treatment of a variety of grammar models, we present a condition on the class of control languages that guarantees that erasing productions are avoidable in the resulting grammar model. On the one hand, this generalizes the previous result that in Petri net controlled grammars, erasing productions can be eliminated. On the other hand, it allows us to infer that the same is true for vector grammars.

On the Capabilities of Grammars, Automata, and Transducers Controlled by Monoids
Proceedings of ICALP 2011
Abstract
During recent decades, classical models in language theory have been extended by control mechanisms defined by monoids. We study which monoids cause the extensions of context-free grammars, finite automata, or finite state transducers to exceed the capacity of the original model. Furthermore, we investigate when, in the extended automata model, the nondeterministic variant differs from the deterministic one in capacity. We show that all these conditions are in fact equivalent and present an algebraic characterization. In particular, the open question of whether every language generated by a valence grammar over a finite monoid is context-free is provided with a positive answer.

On Erasing Productions in Random Context Grammars
Proceedings of ICALP 2010
Abstract
Three open questions in the theory of regulated rewriting are addressed. The first is whether every permitting random context grammar has a non-erasing equivalent. The second asks whether the same is true for matrix grammars without appearance checking. The third concerns whether permitting random context grammars have the same generative capacity as matrix grammars without appearance checking. The main result is a positive answer to the first question. For the other two, conjectures are presented. It is then deduced from the main result that at least one of the two holds.

Erasing in Petri Net Languages and Matrix Grammars
Proceedings of DLT 2009
Abstract
It is shown that applying linear erasing to a Petri net language yields a language generated by a non-erasing matrix grammar. The proof uses Petri net controlled grammars. These are context-free grammars, where the application of productions has to comply with a firing sequence in a Petri net. Petri net controlled grammars are equivalent to arbitrary matrix grammars (without appearance checking), but a certain restriction on them (linear Petri net controlled grammars) leads to the class of languages generated by non-erasing matrix grammars. It is also shown that in Petri net controlled grammars (with final markings and arbitrary labeling), erasing rules can be eliminated, which yields a reformulation of the problem of whether erasing rules in matrix grammars can be eliminated.

Labeled Step Sequences in Petri Nets
with Matthias Jantzen
Proceedings of PETRI NETS 2008
Abstract
We compare various modes of firing transitions in Petri nets and define classes of languages defined this way. We define languages through steps, i. e. sets of transitions, maximal steps, multi-steps, and maximal multi-steps of transitions in Petri nets, but in a different manner than those defined in [Burk 81a,Burk 83], by considering labeled transitions. We will show that we obtain a hierarchy of families of languages defined by multiple use of transition in firing transitions in a single multistep. Except for the maximal multi-steps all classes can be simulated by sequential firing of transitions.

Journal articles

Existential definability over the subword ordering
with Pascal Baumann, Moses Ganardi, and Ramanathan S. Thinniyam
Logical Methods in Computer Science 19, 2023
Abstract
We study first-order logic (FO) over the structure consisting of finite words over some alphabet~$A$, together with the (non-contiguous) subword ordering. In terms of decidability of quantifier alternation fragments, this logic is well-understood: If every word is available as a constant, then even the $\Sigma_1$ (i.e., existential) fragment is undecidable, already for binary alphabets $A$. However, up to now, little is known about the expressiveness of the quantifier alternation fragments: For example, the undecidability proof for the existential fragment relies on Diophantine equations and only shows that recursively enumerable languages over a singleton alphabet (and some auxiliary predicates) are definable. We show that if $|A|\ge 3$, then a relation is definable in the existential fragment over $A$ with constants if and only if it is recursively enumerable. This implies characterizations for all fragments~$\Sigma_i$: If $|A|\ge 3$, then a relation is definable in $\Sigma_i$ if and only if it belongs to the $i$-th level of the arithmetical hierarchy. In addition, our result yields an analogous complete description of the $\Sigma_i$-fragments for $i\ge 2$ of the \emph{pure logic}, where the words of $A^*$ are not available as constants.

Knapsack and the power word problem in Baumslag-Solitar Groups
with Moses Ganardi and Markus Lohrey
International Journal of Algebra and Computation 33, 2023
Abstract
We prove that the power word problem for certain metabelian subgroups of $GL(2,\mathbb{C})$ (including the solvable Baumslag-Solitar groups $BS(1,q) = \langle a,t \mid t a t^{-1} = a^q \rangle$) belongs to the circuit complexity class $TC^0$. In the power word problem, the input consists of group elements $g_1, \ldots, g_d$ and binary encoded integers $n_1, \ldots, n_d$ and it is asked whether $g_1^{n_1} \cdots g_d^{n_d} = 1$ holds. Moreover, we prove that the knapsack problem for $\BS(1,q)$ is $\NP$-complete. In the knapsack problem, the input consists of group elements $g_1, \ldots, g_d,h$ and it is asked whether the equation $g_1^{x_1} \cdots g_d^{x_d} = h$ has a solution in $\N^d$. For the more general case of a system of so-called exponent equations, where the exponent variables $x_i$ can occur multiple times, we show that solvability is undecidable for $BS(1,q)$.

Closure properties of knapsack semilinear groups
with Michael Figelius and Markus Lohrey
Journal of Algebra 589, 2022
Abstract
A knapsack equation in a group $G$ is an equation of the form $g_1^{x_1}\cdots g_k^{x_k}=g$, where $g_1,\ldots,g_k,g$ are elements of G and $x_1,\ldots,x_k$ are variables that take values in the natural numbers. We study the class of groups G for which all knapsack equations have effectively semilinear solution sets. We show that the following group constructions preserve effective semilinearity: graph products, amalgamated free products with finite amalgamated subgroups, HNN-extensions with finite associated subgroups, and finite extensions. Moreover, we study a complexity measure, called magnitude, of the resulting semilinear solution sets. More precisely, we are interested in the growth of the magnitude in terms of the length of the knapsack equation (measured in number of generators). We investigate how this growth changes under the above group operations.

The Emptiness Problem for Valence Automata over Graph Monoids
Information and Computation 277, 2021
Special Issue on RP 2015
Abstract
This work studies which storage mechanisms in automata permit decidability of the emptiness problem. The question is formalized using valence automata, an abstract model of automata in which the storage mechanism is given by a monoid. For each of a variety of storage mechanisms, one can choose a (typically infinite) monoid $M$ such that valence automata over $M$ are equivalent to (one-way) automata with this type of storage. In fact, many important storage mechanisms can be realized by monoids defined by finite graphs, called graph monoids. Examples include pushdown stacks, partially blind counters (which behave like Petri net places), blind counters (which may attain negative values), and combinations thereof.
Hence, we study for which graph monoids the emptiness problem for valence automata is decidable. A particular model realized by graph monoids is that of Petri nets with a pushdown stack. For these, decidability is a long-standing open question and we do not answer it here.
However, if one excludes subgraphs corresponding to this model, a characterization can be achieved. Moreover, we provide a description of those storage mechanisms for which decidability remains open. This leads to a model that naturally generalizes both pushdown Petri nets and the priority multicounter machines introduced by Reinhardt.
The cases that are proven decidable constitute a natural and apparently new extension of Petri nets with decidable reachability. It is finally shown that this model can be combined with another such extension by Atig and Ganty: We present a further decidability result that subsumes both of these Petri net extensions.

General Decidability Results for Asynchronous Shared-Memory Programs: Higher-Order and Beyond
with Rupak Majumdar and Ramanathan S. Thinniyam
Logical Methods in Computer Science 18, 2022
Special Issue on TACAS 2021
Abstract
The model of asynchronous programming arises in many contexts, from low-level systems software to high-level web programming. We take a language-theoretic perspective and show general decidability and undecidability results for asynchronous programs that capture all known results as well as show decidability of new and important classes. As a main consequence, we show decidability of safety, termination and boundedness verification for higher-order asynchronous programs -- such as OCaml programs using Lwt -- and undecidability of liveness verification already for order-2 asynchronous programs. We show that under mild assumptions, surprisingly, safety and termination verification of asynchronous programs with handlers from a language class are decidable iff emptiness is decidable for the underlying language class. Moreover, we show that configuration reachability and liveness (fair termination) verification are equivalent, and decidability of these problems implies decidability of the well-known "equal-letters" problem on languages. Our results close the decidability frontier for asynchronous programs.

Knapsack in Graph Groups
with Markus Lohrey
Theory of Computing Systems 62, 2018
Special Issue on STACS 2016
Abstract
It is shown that the knapsack problem, which was introduced by Myasnikov et al. for arbitrary finitely generated groups, can be solved in {\sf NP} for every graph group. This result even holds if the group elements are represented in a compressed form by so called straight-line programs, which generalizes the classical {\sf NP}-completeness result of the integer knapsack problem. If group elements are represented explicitly by words over the generators, then knapsack for a graph group belongs the class {\sf LogCFL} (a subclass of {\sf P}) if the graph group can be built up from the trivial group using the operations of free product and direct product with $\Z$. In all other cases, the knapsack problem is {\sf NP}-complete.

The Monoid of Queue Actions
with Martin Huschenbett and Dietrich Kuske
Semigroup Forum 95, 2017
Abstract
We investigate the monoid of transformations that are induced by sequences of writing to and reading from a queue storage. We describe this monoid by means of a confluent and terminating semi-Thue system and study some of its basic algebraic properties, e.g., conjugacy. Moreover, we show that while several properties concerning its rational subsets are undecidable, their uniform membership problem is NL-complete. Furthermore, we present an algebraic characterization of this monoid's recognizable subsets. Finally, we prove that it is not Thurston-automatic.

A Characterization for Decidable Separability by Piecewise Testable Languages
with Wojciech Czerwiński, Wim Martens, Lorijn van Rooijen, and Marc Zeitoun
Discrete Mathematics and Theoretical Computer Science 19(4), 2017
Special Issue on FCT 2015
Abstract
The separability problem for word languages of a class $\C$ by languages of a class $\S$ asks, for two given languages $I$ and $E$ from $\C$, whether there exists a language $S$ from $\S$ that includes $I$ and excludes $E$, that is, $I \subseteq S$ and $S\cap E = \emptyset$. In this work, we assume some mild closure properties for $\C$ and study for which such classes $\C$, separability by piecewise testable languages (PTL) is decidable. We characterize these classes in terms of decidability of (two variants of) an unboundedness problem. From this we deduce that separability by PTL is decidable for a number of language classes, such as the context-free languages and languages of labeled vector addition systems. Furthermore, it follows that separability by PTL is decidable if and only if one can compute for any language of the class its downward closure wrt.\ the \subword ordering (i.e., if the set of \subwords of any language of the class is effectively regular).
The obtained decidability results contrast some undecidability results. In fact, for all the (non-regular) language classes we present as examples with decidable separability, it is undecidable whether a given language is a PTL itself.
Our characterization involves a result of independent interest, which states that for \emph{any} kind of languages $I$ and $E$, non-separability is equivalent to the existence of common patterns in $I$ and $E$.

On Boolean closed full trios and rational Kripke frames
with Dietrich Kuske and Markus Lohrey
Theory of Computing Systems 60, 2017
Special Issue on STACS 2014
Abstract
We study what languages can be constructed from a non-regular language $L$ using Boolean operations and (synchronized) rational transductions. If all rational transductions are allowed, one can construct the whole arithemtical hierarchy relative to $L$. If only synchronized rational transductions are allowed, we present non-regular languages that allow to construct at least languages arbitrarily high in the arithmetical hierarchy and we present non-regular languages that allow to construct only decidable languages.
A consequence of the results is that aside from the regular languages, no full trio generated by a single language is closed under complementation.
Our construction also shows that there is a fixed rational Kripke frame such that assigning an arbitrary non-regular language to some variable allows the definition of any language from the arithmetical hierarchy in the corresponding Kripke structure using multimodal logic.

Monoids as Storage Mechanisms
Bulletin of the EATCS 120, 2016

Permutations of context-free, ET0L and indexed languages
with Tara Brough, Laura Ciobanu, and Murray Elder
Discrete Mathematics and Theoretical Computer Science 17(3), 2016
Abstract
For a language $L$, we consider its cyclic closure, and more generally the language $C^k(L)$, which consists of all words obtained by partitioning words from $L$ into $k$ factors and permuting them. We prove that the classes of ET0L and EDT0L languages are closed under the operators $C^k$. This both sharpens and generalises Brandstädt's result that if $L$ is context-free then $C^k(L)$ is context-sensitive and not context-free in general for $k\geq 3$. We also show that the cyclic closure of an indexed language is indexed.

Rational subsets and submonoids of wreath products
with Markus Lohrey and Benjamin Steinberg
Information and Computation 243, 2015
Special Issue on ICALP 2013
Abstract
It is shown that membership in rational subsets of wreath products $H \wr V$ with $H$ a finite group and $V$ a virtually free group is decidable. On the other hand, it is shown that there exists a fixed finitely generated submonoid in the wreath product $\mathbb{Z}\wr\mathbb{Z}$ with an undecidable membership problem.

Toward Understanding the Generative Capacity of Erasing Rules in Matrix Grammars
International Journal of Foundations of Computer Science 22(2), 2011
Special Issue on DLT 2009
Abstract
This article presents approaches to the open problem of whether erasing rules can be eliminated in matrix grammars. The class of languages generated by non-erasing matrix grammars is characterized by the newly introduced linear Petri net grammars. Petri net grammars are known to be equivalent to arbitrary matrix grammars (without appearance checking). In linear Petri net grammars, the marking has to be linear in size with respect to the length of the sentential form. The characterization by linear Petri net grammars is then used to show that applying linear erasing to a Petri net language yields a language generated by a non-erasing matrix grammar. It is also shown that in Petri net grammars (with final markings and arbitrary labeling), erasing rules can be eliminated, which yields two reformulations of the problem of whether erasing rules in matrix grammars can be eliminated.

Properties of Multiset Language Classes Defined by Multiset Pushdown Automata
with Manfred Kudlek and Patrick Totzke
Fundamenta Informaticae 93(1-3), 2009
Special Issue on CS&P 2008
Abstract
The previously introduced multiset language classes defined by multiset pushdown automata are being explored with respect to their closure properties and alternative characterizations.

Multiset Pushdown Automata
with Manfred Kudlek and Patrick Totzke
Fundamenta Informaticae 93(1-3), 2009
Special Issue on CS&P 2008
Abstract
Multiset finite Automata, a model equivalent to regular commutative grammars, are extended with a multiset store and the accepting power of this extended model of computation is investigated. This type of multiset automata come in two flavours, varying only in the ability of testing the storage for emptiness. This paper establishes normal forms and relates the derived language classes to each other as well as to known multiset language classes.

Petri Net Controlled Finite Automata
with Berndt Farwer, Matthias Jantzen, Manfred Kudlek, and Heiko Rölke
Fundamenta Informaticae 85(1-4), 2008
Special Issue on CS&P 2007
Abstract
We present a generalization of finite automata using Petri nets as control, called Concurrent Finite Automata for short. Several modes of acceptance, defined by final markings of the Petri net, are introduced, and their equivalence is shown. The class of languages obtained by l-free concurrent finite automata contains both the class of regular sets and the class of Petri net languages defined by final marking, and is contained in the class of context-sensitive languages.

Language Classes Defined by Concurrent Finite Automata
with Matthias Jantzen and Manfred Kudlek
Fundamenta Informaticae 85(1-4), 2008
Special Issue on CS&P 2007
Abstract
This paper presents results regarding the various relations among the language classes defined by Concurrent Finite Automata, relations to other language classes, as well as decidability and closure properties.

Workshop contributions

Multiset Storage Automata
with Manfred Kudlek and Patrick Totzke
Proceedings of CS&P 2008
Abstract
Two kinds of multiset automata with a storage attached, varying only in their ability of testing the storage for emptiness, are introduced, as well as normal forms. Their accepting power and relation to other multiset languages classes is investigated.

Properties of Multiset Language Classes Defined by Multiset Storage Automata
with Manfred Kudlek and Patrick Totzke
Proceedings of CS&P 2008
Abstract
The previously introduced multiset language classes defined by multiset storage automata are being explored with respect to their closure properties and alternative characterizations.

Concurrent finite automata and related language classes (an overview)
with Manfred Kudlek
Proceedings of AFLAS 2008

On Concurrent Finite Automata
with Berndt Farwer, Matthias Jantzen, Manfred Kudlek, and Heiko Rölke
Proceedings of CS&P 2007

On Languages Accepted by Concurrent Finite Automata
with Matthias Jantzen and Manfred Kudlek
Proceedings of CS&P 2007

Finite Automata Controlled by Petri Nets
with Matthias Jantzen and Manfred Kudlek
Proceedings of AWPN 2007

Theses

On Erasing Productions in Grammars with Regulated Rewriting
Diplomarbeit (Master's thesis), Universität Hamburg, 2010

Monoids as Storage Mechanisms
PhD thesis, Technische Universität Kaiserslautern, 2016
EATCS Distinguished Dissertation Award
Abstract
Automata theory has given rise to a variety of automata models that consist of a finite-state control and an infinite-state storage mechanism. The aim of this work is to provide insights into how the structure of the storage mechanism influences the expressiveness and the analyzability of the resulting model. To this end, it presents generalizations of results about individual storage mechanisms to larger classes. These generalizations characterize those storage mechanisms for which the given result remains true and for which it fails.
In order to speak of classes of storage mechanisms, we need an overarching framework that accommodates each of the concrete storage mechanisms we wish to address. Such a framework is provided by the model of valence automata, in which the storage mechanism is represented by a monoid. Since the monoid serves as a parameter to specifying the storage mechanism, our aim translates into the question: For which monoids does the given (automata-theoretic) result hold?
As a first result, we present an algebraic characterization of those monoids over which valence automata accept only regular languages. In addition, it turns out that for each monoid, this is the case if and only if valence grammars, an analogous grammar model, can generate only context-free languages.
Furthermore, we are concerned with closure properties: We study which monoids result in a Boolean closed language class. For every language class that is closed under rational transductions (in particular, those induced by valence automata), we show: If the class is Boolean closed and contains any non-regular language, then it already includes the whole arithmetical hierarchy.
This work also introduces the class of graph monoids, which are defined by finite graphs. By choosing appropriate graphs, one can realize a number of prominent storage mechanisms, but also combinations and variants thereof. Examples are pushdowns, counters, and Turing tapes. We can therefore relate the structure of the graphs to computational properties of the resulting storage mechanisms.
In the case of graph monoids, we study (i) the decidability of the emptiness problem, (ii) which storage mechanisms guarantee semilinear Parikh images, (iii) when silent transitions (i.e. those that read no input) can be avoided, and (iv) which storage mechanisms permit the computation of downward closures.

Service [ back to top ]
I am on the program committee of CiE 2019, DLT 2019, and STACS 2020.

I have reviewed submissions for Journal of the ACM, Algorithmica, ACM TECS, IJFCS, IJAC, DMTCS, JCSS, TCS, Acta Informatica, Inform. Comput., Kybernetika, LMCS, ACSD 2013, DLT 2013, ICALP 2013, ACSD 2014, AFL 2014, FSTTCS 2014, DCFS 2015, CSL 2015, FSTTCS 2015, POPL 2016, LATA 2016, TACAS 2016, ICALP 2016, MFCS 2016, STACS 2017, FoSSaCS 2017, CIE 2017, ICALP 2017, CIAA 2017, GandALF 2017, MFCS 2017, FSTTCS 2017, STACS 2018, CIE 2018, DLT 2018, ICALP 2018, MFCS 2018, CONCUR 2018, FSTTCS 2018, SOFSEM 2018, LATA 2019, LICS 2019, ICALP 2019, FSTTCS 2019, ISSAC 2020, RAMiCS 2021, STACS 2023, and STACS 2024.

Teaching [ back to top ]
Supervised theses
  1. Martin Köhler (Bachelor thesis, 2014)
  2. Phoebe Buckheister (Bachelor thesis, 2013)
Lectures
Organization of exercise courses
Tutoring
Talks [ back to top ]
Invited talks

Given at Jewels of Automata Theory 2024 in Bordeaux, France

Given at ANR Delta Project Meeting in Marseille, France

Recent Advances on Reachability Problems in Valence Systems
Given at RP 2021 in Liverpool, UK

Subword Based Abstractions of Formal Languages
Given at Theorietag "Automaten und formale Sprachen" 2016 in Tannenfelde, Germany
Abstract
A successful idea in the area of verification is to consider finite-state abstractions of infinite-state systems. A prominent example is the fact that many language classes satisfy a Parikh's theorem, i.e. for each language, there exists a finite automaton that accepts the same language up to the order of letters. Hence, provided that the abstraction preserves pertinent properties, this allows us to work with finite-state systems, which are much easier to handle.
While Parikh-style abstractions have been studied very intensely over the last decades, recent years have seen an increasing interest in abstractions based on the subword ordering. Examples include the set of (non necessarily contiguous) subwords of members of a language (the downward closure), or their superwords (the upward closure). Whereas it is well-known that these closures are regular for any language, it is often not obvious how to compute them. Another type of subword based abstractions are piecewise testable separators. Here, a separators acts as an abstraction of a pair of languages.
This talk will present approaches to computing closures, deciding separability by piecewise testable languages, and a (perhaps surprising) connection between these problems. If time permits, complexity issues will be discussed as well.

Knapsack in Graph Groups, HNN-Extensions and Amalgamated Products
(joint work with Markus Lohrey)
Given at Equations and formal languages in algebra in Les Diablerets, Switzerland
Abstract
It is shown that the knapsack problem, which was introduced by Myasnikov et al. for arbitrary finitely generated groups, can be solved in NP for graph groups. This result even holds if the group elements are represented in a compressed form by SLPs, which generalizes the classical NP-completeness result of the integer knapsack problem. We also prove general transfer results: NP-membership of the knapsack problem is passed on to finite extensions, HNN-extensions over finite associated subgroups, and amalgamated products with finite identified subgroups.

Recent Results on Erasing in Regulated Rewriting
Given at Theorietag "Automaten und formale Sprachen" 2011 in Allrode, Germany
Abstract
For each grammar model with regulated rewriting, it is an important question whether erasing productions add to its expressivity. In some cases, however, this has been a longstanding open problem. In recent years, several results have been obtained that clarified the generative capacity of erasing productions in some grammar models with classical types of regulated rewriting. The aim of this talk is to give an overview of these results.

Other talks

The complexity of bidirected reachability in valence systems
(joint work with Moses Ganardi and Rupak Majumdar)
Given at LICS 2022 in Haifa, Israel
Abstract
Reachability problems in infinite-state systems are often subject to extremely high complexity. This motivates the investigation of efficient overapproximations, where we add transitions to obtain a system in which reachability can be decided more easily. We consider bidirected infinite-state systems, where for every transition there is a transition with opposite effect. We study bidirected reachability in the framework of valence systems, an abstract model featuring finitely many control states and an infinite-state storage that is specified by a finite graph. By picking suitable graphs, valence systems can uniformly model counters as in vector addition systems, pushdowns, integer counters, and combinations thereof. We provide a comprehensive complexity landscape for bidirected reachability and show that the complexity drops substantially (often to polynomial time) from that of general reachability, for almost every storage mechanism where reachability is known to be decidable.

Given at Dagstuhl Seminar on Unambiguity in Automata Theory in Schloss Dagstuhl, Germany

Context-bounded verification of liveness properties for multithreaded shared-memory programs
Given at Seminar "Méthodes Formelles" at LaBRI in Bordeaux, France

Rational Subsets of Baumslag-Solitar Groups
Given at Seminar on Semigroups, Automata and Languages at Centro de Matemática, Universidade do Porto in Porto, Portugal

Rational Subsets of Baumslag-Solitar Groups
Given at Göttingen-Kassel Theory (Online) Seminar

Given at Dagstuhl Seminar on Modern Aspects of Complexity Theory in Automata Theory in Schloss Dagstuhl, Germany

Extensions of Omega-Regular Languages
Given at Highlights 2020

Rational Subsets of Baumslag-Solitar Groups
Given at Seminar "Automates et applications" at IRIF in Paris, France

Extensions of Omega-Regular Languages
Given at Seminar "Automates et applications" at IRIF in Paris, France

Rational subsets of Baumslag-Solitar groups
(joint work with Michaël Cadilhac and Dmitry Chistikov)
Given at ICALP 2020

Coverability Is Undecidable in One-Dimensional Pushdown Vector Addition Systems with Resets
(joint work with Sylvain Schmitz)
Given at RP 2019 in Brussels, Belgium
Abstract
We consider the model of pushdown vector addition systems with resets. These consist of vector addition systems that have access to a pushdown stack and have instructions to reset counters. For this model, we study the coverability problem. In the absence of resets, this problem is known to be decidable for one-dimensional pushdown vector addition systems, but decidability is open for general pushdown vector addition systems. Moreover, coverability is known to be decidable for reset vector addition systems without a pushdown stack. We show in this note that the problem is undecidable for one-dimensional pushdown vector addition systems with resets.

Presburger arithmetic with stars, rational subsets of graph groups, and nested zero tests
Given at Highlights 2019 in Warsaw, Poland

Regular subsets of wreath products
Given at Dagstuhl Seminar on Algorithmic Problems in Group Theory in Schloss Dagstuhl, Germany

Given at CAALM 2021 in Chennai, India

Separability by piecewise testable languages and downward closures beyond subwords
Given at LICS 2018 in Oxford, United Kingdom
Abstract
We introduce a flexible class of well-quasi-orderings (WQOs) on words that generalizes the ordering of (not necessarily contiguous) subwords. Each such WQO induces a class of piecewise testable languages (PTLs) as Boolean combinations of upward closed sets. In this way, a range of regular language classes arises as PTLs. Moreover, each of the WQOs guarantees regularity of all downward closed sets.
We consider two problems. First, we study which (perhaps non-regular) language classes allow to decide whether two given languages are separable by a PTL with respect to a given WQO. Second, we want to effectively compute downward closures with respect to these WQOs.
Our first main result is that for each of the WQOs, under mild assumptions, both problems reduce to the simultaneous unboundedness problem (SUP) and are thus solvable for many powerful system models. In the second main result, we apply the framework to show decidability of separability of regular languages by $\mathcal{B}\Sigma_1[<, \mathsf{mod}]$, a fragment of first-order logic with modular predicates.

Storage mechanisms and finite-state abstractions for software verification
Given at MPI-SWS Colloquium in Kaiserslautern, Germany

Storage mechanisms and finite-state abstractions for software verification
Given at Kolloquium Technische Universität Kaiserslautern in Germany

Parameterized WQOs, downward closures, and separability problems
Given at Workshop on Separability Problems in Warsaw, Poland
Abstract
We discuss a flexible class of well-quasi-orderings on words that generalizes the ordering of (not necessarily contiguous) subwords. Each of these orderings is specified by a finite automaton or a counter automaton and, like the subword ordering, guarantees regularity of all downward (or upward) closures. We then consider two problems. First, we study for which language classes one can effectively compute downward closures with respect to these orderings. Second, we are interested in which language classes permit a decision procedure to decide whether two given languages are separable by a PTL with respect to such an ordering. Here, a PTL is a finite Boolean combination of upward closed sets. The main result is that, under mild assumptions on closure properties, these two problems are solvable for the same language classes. Moreover, solvability is equivalent to that of a particular unboundedness problem that has recently been shown to be decidable for many powerful language classes.

First-order logic over the subword ordering
(joint work with Simon Halfon and Philippe Schnoebelen)
Given at Verification Seminar at Oxford University, United Kingdom
Abstract
This talk reports on results concerning first-order logic over the subword ordering on finite words. It has been known since 2006 that the whole first-order logic over this structure is undecidable, whereas the Sigma_1 fragment is NP-complete. One might therefore expect that introducing each word as a constant would leave the Sigma_1 fragment decidable. However, it was shown recently that in the presence of these constants, the \Sigma_1 theory becomes undecidable (already over two letters). Regarding the decidability border, we will consider fragments where all but a certain number of variables are alternation bounded, meaning that the variable must always be quantified over languages with a bounded number of letter alternations. Here, the second result is that when at most two variables are not alternation bounded, the \Sigma_1 fragment is decidable, and that it becomes undecidable when three variables are not alternation bounded. Concerning higher quantifier alternation depths, the \Sigma_2 fragment is undecidable already for one variable without alternation bound and that when all variables are alternation bounded, the entire first-order theory is decidable. If time permits, complexity aspects will be treated as well. This is joint work with Simon Halfon and Philippe Schnoebelen (to be presented at LICS 2017).

Monoids as Storage Mechanisms
Given at Kasseler Informatik-Kolloquium, Universität Kassel in Germany
Abstract
The investigation of models extending finite automata by some storage mechanism is a central theme in theoretical computer science. Choosing an appropriate storage mechanism can yield a model that is expressive enough to capture a given behavioral aspect while admitting desired means of analysis. It is therefore a central concern to understand which storage mechanisms have which properties regarding expressiveness and (algorithmic) analysis. This talk presents a line of research that aims for general insights in this direction. In other words: How does the structure of the storage mechanism influence expressiveness and analysis of the resulting model? In order to study this question, one needs a model in which the storage mechanism appears as a parameter. Such a model is available in valence automata, where the storage mechanism is given by a (typically infinite) monoid. Choosing a suitable monoid then yields models such as Turing machines, pushdown automata, vector addition systems, or combinations thereof. This talk surveys a selection of results that characterize storage mechanisms with certain desirable properties, such as decidability of reachability, semilinearity of Parikh images, and decidability of logics.

The Complexity of Knapsack in Graph Groups
(joint work with Markus Lohrey)
Given at STACS 2017 in Hannover, Germany
Abstract
Myasnikov et al. have introduced the knapsack problem for arbitrary finitely generated groups. In previous work, the authors proved that for each graph group, the knapsack problem can be solved in NP. Here, we determine the exact complexity of the problem for every graph group. While the problem is TC0-complete for complete graphs, it is LogCFL-complete for each (non-complete) transitive forest. For every remaining graph, the problem is NP-complete.

First-order logic with reachability for infinite-state systems
(joint work with Emanuele D'Osualdo and Roland Meyer)
Given at Seminar "Modélisation et vérification" at IRIF in Paris, France
Abstract
First-order logic with the reachability predicate (FOR) is an important means of specification in system analysis. Its decidability status is known for some individual types of infinite-state systems such as pushdown (decidable) and vector addition systems (undecidable).
This work aims at a general understanding of which types of systems admit decidability. As a unifying model, we employ valence systems over graph monoids, which feature a finite-state control and are parameterized by a monoid to represent their storage mechanism. As special cases, this includes pushdown systems, various types of counter systems (such as vector addition systems) and combinations thereof. Our main result is a characterization of those graph monoids where FOR is decidable for the resulting transition systems.

Subword Based Abstractions of Formal Languages
Given at Seminar "Méthodes Formelles" at LaBRI in Bordeaux, France
Abstract
A successful idea in the area of verification is to consider finite-state abstractions of infinite-state systems. A prominent example is the fact that many language classes satisfy a Parikh's theorem, i.e. for each language, there exists a finite automaton that accepts the same language up to the order of letters. Hence, provided that the abstraction preserves pertinent properties, this allows us to work with finite-state systems, which are much easier to handle.
While Parikh-style abstractions have been studied very intensely over the last decades, recent years have seen an increasing interest in abstractions based on the subword ordering. Examples include the set of (non necessarily contiguous) subwords of members of a language (the downward closure), or their superwords (the upward closure). Whereas it is well-known that these closures are regular for any language, it is often not obvious how to compute them. Another type of subword based abstractions are piecewise testable separators. Here, a separators acts as an abstraction of a pair of languages.
This talk will present approaches to computing closures, deciding separability by piecewise testable languages, and a (perhaps surprising) connection between these problems. If time permits, complexity issues will be discussed as well.

Subword Based Abstractions of Formal Languages
Given at Seminar "Automates et applications" at IRIF in Paris, France
Abstract
A successful idea in the area of verification is to consider finite-state abstractions of infinite-state systems. A prominent example is the fact that many language classes satisfy a Parikh's theorem, i.e. for each language, there exists a finite automaton that accepts the same language up to the order of letters. Hence, provided that the abstraction preserves pertinent properties, this allows us to work with finite-state systems, which are much easier to handle.
While Parikh-style abstractions have been studied very intensely over the last decades, recent years have seen an increasing interest in abstractions based on the subword ordering. Examples include the set of (non necessarily contiguous) subwords of members of a language (the downward closure), or their superwords (the upward closure). Whereas it is well-known that these closures are regular for any language, it is often not obvious how to compute them. Another type of subword based abstractions are piecewise testable separators. Here, a separators acts as an abstraction of a pair of languages.
This talk will present approaches to computing closures, deciding separability by piecewise testable languages, and a (perhaps surprising) connection between these problems. If time permits, complexity issues will be discussed as well.

First-order logic with reachability for valence automata over graph monoids
(joint work with Emanuele D'Osualdo and Roland Meyer)
Given at Jahrestagung "Logik in der Informatik" 2016 in Tannenfelde, Germany
Abstract
First-order logic with the reachability predicate (FOR) is an important means of specification in system analysis. Its decidability status is known for some individual types of infinite-state systems such as pushdown (decidable) and vector addition systems (undecidable).
This work aims at a general understanding of which types of systems admit decidability. As a unifying model, we employ valence systems over graph monoids, which feature a finite-state control and are parameterized by a monoid to represent their storage mechanism. As special cases, this includes pushdown systems, various types of counter systems (such as vector addition systems) and combinations thereof. Our main result is a characterization of those graph monoids where FOR is decidable for the resulting transition systems.

Monoids as Storage Mechanisms
Given at Theory Seminar at the National University of Singapore
Abstract
The investigation of models extending finite automata by some storage mechanism is a central theme in theoretical computer science. Choosing an appropriate storage mechanism can yield a model that is expressive enough to capture a given behavioral aspect while admitting desired means of analysis.
It is therefore a central concern to understand which storage mechanisms have which properties regarding expressiveness and (algorithmic) analysis. This talk presents a line of research that aims for general insights in this direction. In other words: How does the structure of the storage mechanism influence expressiveness and analysis of the resulting model?
In order to study this question, one needs a model in which the storage mechanism appears as a parameter. Such a model is available in valence automata, where the storage mechanism is given by a (typically infinite) monoid. Choosing a suitable monoid then yields models such as Turing machines, pushdown automata, vector addition systems, or combinations thereof.
This talk surveys a selection of results that characterize storage mechanisms with certain desirable properties, such as decidability of reachability, semilinearity of Parikh images, and decidability of logics.

Monoids as Storage Mechanisms
Given at Communicating, Distributed and Parameterized Systems in Singapore
Abstract
The investigation of models extending finite automata by some storage mechanism is a central theme in theoretical computer science. Choosing an appropriate storage mechanism can yield a model that is expressive enough to capture a given behavioral aspect while admitting desired means of analysis.
It is therefore a central concern to understand which storage mechanisms have which properties regarding expressiveness and (algorithmic) analysis. This talk presents a line of research that aims for general insights in this direction. In other words: How does the structure of the storage mechanism influence expressiveness and analysis of the resulting model?
In order to study this question, one needs a model in which the storage mechanism appears as a parameter. Such a model is available in valence automata, where the storage mechanism is given by a (typically infinite) monoid. Choosing a suitable monoid then yields models such as Turing machines, pushdown automata, vector addition systems, or combinations thereof.
This talk surveys a selection of results that characterize storage mechanisms with certain desirable properties, such as decidability of reachability, semilinearity of Parikh images, and decidability of logics.

The Complexity of Downward Closure Comparisons
Given at ICALP 2016 in Rome, Italy
Abstract
The downward closure of a language is the set of all (not necessarily contiguous) subwords of its members. It is well-known that the downward closure of every language is regular. Moreover, recent results show that downward closures are computable for quite powerful system models.
One advantage of abstracting a language by its downward closure is that then, equivalence and inclusion become decidable. In this work, we study the complexity of these two problems. More precisely, we consider the following decision problems: Given languages $K$ and $L$ from classes $\C$ and $\D$, respectively, does the downward closure of $K$ include (equal) that of $L$?
These problems are investigated for finite automata, one-counter automata, context-free grammars, and reversal-bounded counter automata. For each combination, we prove a completeness result either for fixed or for arbitrary alphabets. Moreover, for Petri net languages, we show that both problems are Ackermann-hard and for higher-order pushdown automata of order $k$, we prove hardness for complements of nondeterministic $k$-fold exponential time.

Boolean closed full trios and rational Kripke frames
(joint work with Dietrich Kuske and Markus Lohrey)
Given at Seminar of the INFINI group at LSV in May 2016 in Cachan, France
Abstract
It is a well-known phenomenon that languages classes induced by infinite-state systems usually lack decidability and closure properties that make regular languages pleasant to analyze. Most notably, nondeterministic infinite-state systems typically fail to be closed under Boolean operations. In visibly pushdown automata, one has closure under Boolean operations, but at the expense of restricting the employed input alphabets, meaning they are not closed under rational transductions.
This raises the question of whether there is some type of infinite-state system that enjoys closure under Boolean operations and rational transductions (and permits decidability of, say, the emptiness problem). This talk demonstrates that this is not the case. It is shown that every language class that contains any non-regular language and is closed under Boolean operations and rational transductions already contains the whole arithmetic hierarchy (which significantly extends the recursively enumerable languages).

The complexity of downward closure comparisons
Given at NII Shonan Meeting on Higher-Order Model Checking in Shonan, Japan
Abstract
The downward closure of a language is the set of all (not necessarily contiguous) subwords of its members. It is well-known that the downward closure of every language is regular. One advantage of abstracting a language by its downward closure is that then, equivalence and inclusion become decidable.
It has recently been shown by Hague, Kochems, and Ong that downward closures are computable for higher-order pushdown automata. However, the current method yields no upper bound on the complexity of such a computation. This talk will present recent results on complexity issues surrounding downward closures. Aside from general algorithms and possible approaches to obtain upper bounds in the case of HOPA, we will discuss a lower bound result for the abovementioned equivalence and inclusion problem for HOPA.

Knapsack in Graph Groups, HNN-Extensions and Amalgamated Products
(joint work with Markus Lohrey)
Given at STACS 2016 in Orléans, France
Abstract
It is shown that the knapsack problem, which was introduced by Myasnikov et al. for arbitrary finitely generated groups, can be solved in NP for graph groups. This result even holds if the group elements are represented in a compressed form by SLPs, which generalizes the classical NP-completeness result of the integer knapsack problem. We also prove general transfer results: NP-membership of the knapsack problem is passed on to finite extensions, HNN-extensions over finite associated subgroups, and amalgamated products with finite identified subgroups.

Monoids as Storage Mechanisms
Given at Seminar of the INFINI group at LSV in December 2015 in Cachan, France
Abstract
The investigation of models extending finite automata by some storage mechanism is a central theme in theoretical computer science. Choosing an appropriate storage mechanism can yield a model that is expressive enough to capture a given behavioral aspect while admitting desired means of analysis.
It is therefore a central concern to understand which storage mechanisms have which properties regarding expressiveness and (algorithmic) analysis. This talk presents a line of research that aims for general insights in this direction. In other words: How does the structure of the storage mechanism influences expressiveness and analysis of the resulting model?
In order to study this question, one needs a model in which the storage mechanism appears as a parameter. Such a model is available in valence automata, where the storage mechanism is given by a (typically infinite) monoid. Choosing a suitable monoid then yields models such as Turing machines, pushdown automata, vector addition systems, or combinations thereof.
This talk surveys a selection of results that characterize storage mechanisms with certain desirable properties, such as deciability of reachability, semilinearity of Parikh images, and avoidability of epsilon-transitions.

An Approach to Computing Downward Cosures
Given at Theorietag "Automaten und formale Sprachen" 2015 in Speyer, Germany
Abstract
The downward closure of a word language is the set of all (not necessarily contiguous) subwords of its members. It is known that the downward closure of every language is regular. However, algorithms for computing a finite automaton for the downward closure of a given language are known only for few language classes. This work presents a simple general approach to this problem. It is used to prove that downward closures are computable for (i)~every language class with effectively semilinear Parikh images that is closed under rational transductions, (ii)~matrix languages, and (iii)~indexed languages (equivalently, languages accepted by higher-order pushdown automata of order~2).

The Emptiness Problem for Valence Automata or: Another Decidable Extension of Petri Nets
Given at RP 2015 in Warsaw, Poland
Abstract
This work studies which storage mechanisms in automata permit decidability of the reachability problem. The question is formalized using valence automata, an abstract model that generalizes automata with storage. For each of a variety of storage mechanisms, one can choose a (typically infinite) monoid $M$ such that valence automata over $M$ are equivalent to (one-way) automata with this type of storage.
In fact, many interesting storage mechanisms can be realized by monoids defined by finite graphs, called graph monoids. Hence, we study for which graph monoids the emptiness problem for valence automata is decidable. A particular model realized by graph monoids is that of Petri nets with a pushdown stack. For these, decidability is a long-standing open question and we do not answer it here.
However, if one excludes subgraphs corresponding to this model, a characterization can be achieved. This characterization yields a new extension of Petri nets with a decidable reachability problem. Moreover, we provide a description of those storage mechanisms for which decidability remains open. This leads to a natural model that generalizes both pushdown Petri nets and priority multicounter machines.

An Approach to Computing Downward Closures
Given at ICALP 2015 in Kyoto, Japan
Abstract
The downward closure of a word language is the set of all (not necessarily contiguous) subwords of its members. It is well-known that the downward closure of any language is regular. While the downward closure appears to be a powerful abstraction, algorithms for computing a finite automaton for the downward closure of a given language have been established only for few language classes.
This work presents a simple general method for computing downward closures. For language classes that are closed under rational transductions, it is shown that the computation of downward closures can be reduced to checking a certain unboundedness property.
This result is used to prove that downward closures are computable for (i) every language class with effectively semilinear Parikh images that are closed under rational transductions, (ii) matrix languages, and (iii) indexed languages (equivalently, languages accepted by higher-order pushdown automata of order~2).

Downward Closures of Indexed Languages
Given at HOPA 2015 in Kyoto, Japan

Computing downward closures for stacked counter automata
Given at STACS 2015 in Munich, Germany
Abstract
The downward closure of a language $L$ of words is the set of all (not necessarily contiguous) subwords of members of $L$. It is well known that the downward closure of any language is regular. Although the downward closure seems to be a promising abstraction, there are only few language classes for which an automaton for the downward closure is known to be computable.
It is shown here that for stacked counter automata, the downward closure is computable. Stacked counter automata are finite automata with a storage mechanism obtained by \emph{adding blind counters} and \emph{building stacks}. Hence, they generalize pushdown and blind counter automata.
The class of languages accepted by these automata are precisely those in the hierarchy obtained from the context-free languages by alternating two closure operators: imposing semilinear constraints and taking the algebraic extension. The main tool for computing downward closures is the new concept of Parikh annotations. As a second application of Parikh annotations, it is shown that the hierarchy above is strict at every level.

Effectively regular downward closures
Given at LSV Seminar at ENS Cachan in Cachan, France
Abstract
The downward closure of a language is the set of all (not necessarily contiguous) subwords of its members. It is a well-known consequence of Higman's Lemma that the downward closure of every language is regular.
Aside from encoding interesting counting properties, the downward closure constitutes a promising abstraction: If L is the set of action sequences of a system, then the downward closure of L is precisely what is observed through a lossy channel, i.e. when actions can go unnoticed arbitrarily. Hence, if the downward closure is available as a regular language, the equivalence and even inclusion of system behaviors can be decided with respect to such observations.
However, there are only few classes of languages for which it is known how to compute the downward closure of a given language as a finite automaton. This talk presents new approaches to this problem.

Expressiveness and analysis of valence automata over graph monoids
Given at FORMAT Workshop 07/2014 in Kaiserslautern, Germany

Of stacks (of stacks (...) with blind counters) with blind counters
Given at AISS 2014 in Vienna, Austria
Abstract
Recent work on automata with abstract storage revealed a class of storage mechanisms that proves quite expressive and amenable to various kinds of algorithmic analysis. The storage mechanisms in this class are obtained by \emph{building stacks} and \emph{adding blind counters}.
The former is to construct a new mechanism that stores a stack whose entries are configurations of an old mechanism. One can then manipulate the topmost entry, pop it if empty, or start a new one on top. Adding a blind counter to an old mechanism yields a new mechanism in which the old one and a blind counter can be used simultaneously. We call the resulting model \emph{stacked counter automaton}.
This talk presents results on expressivity, Parikh images, membership problems, and the computability of downward closures.

On Boolean closed full trios and rational Kripke frames
(joint work with Markus Lohrey)
Given at STACS 2014 in Lyon, France
Abstract
A Boolean closed full trio is a class of languages that is closed under the Boolean operations (union, intersection, and complementation) and rational transductions. It is well-known that the regular languages constitute such a Boolean closed full trio. It is shown here that every such language class that contains any non-regular language already includes the whole arithmetical hierarchy (and even the one relative to this language).
A consequence of this result is that aside from the regular languages, no full trio generated by one language is closed under complementation.
Our construction also shows that there is a fixed rational Kripke frame such that assigning an arbitrary non-regular language to some variable allows the definition of any language from the arithmetical hierarchy in the corresponding Kripke structure using multimodal logic.

On Boolean closed full trios and rational Kripke frames
(joint work with Markus Lohrey)
Given at Seminar "Automata and Logic" at Technische Universität Ilmenau in Ilmenau, Germany
Abstract
A Boolean closed full trio is a class of languages that is closed under Boolean operations (union, intersection, and complement) and rational transductions. It is well-known that the regular languages constitute such a Boolean closed full trio. It is shown here that every such language class that contains any non-regular language already includes the whole arithmetical hierarchy (and even the one relative to this language).
Our construction also shows that there is a fixed rational Kripke frame such that assigning an arbitrary non-regular language to some variable allows the interpretation of any language from the arithmetical hierarchy in the corresponding Kripke structure.
Another consequence of our result is that no full trio generated by one language is closed under complementation, unless it coincides with the regular languages.

On Boolean closed full trios and rational Kripke frames
(joint work with Markus Lohrey)
Given at Theorietag "Automaten und formale Sprachen" 2013 in Ilmenau, Germany
Abstract
A Boolean closed full trio is a class of languages that is closed under Boolean operations (union, intersection, and complement) and rational transductions. It is well-known that the regular languages constitute such a Boolean closed full trio. We present a result stating that every such language class that contains any non-regular language already contains the whole arithmetical hierarchy.
Our construction also shows that there is a fixed rational Kripke frame such that assigning an arbitrary non-regular language to some variable allows the interpretation of any language from the arithmetical hierarchy in the corresponding Kripke structure.

Recent advances on valence automata as a generalization of automata with storage
(joint work with Phoebe Buckheister)
Given at Theorietag "Automaten und formale Sprachen" 2013 in Ilmenau, Germany
Abstract
A valence automaton over a monoid $M$ is a finite automaton in which each edge carries an input word and an element of $M$. A word is then accepted if there is a run that spells the word such that the product of the monoid elements is the identity.
By choosing suitable monoids $M$, one can obtain various kinds of automata with storage as special valence automata. Examples include pushdown automata, blind multicounter automata, and partially blind multicounter automata. Therefore, valence automata offer a framework to generalize results on such automata with storage.
This talk will present recent advances in this direction. The addressed questions include: For which monoids do we have a Parikh's Theorem (as for pushdown automata)? For which monoids can we avoid silent transitions?

Semilinearity and Context-Freeness of Languages Accepted by Valence Automata
(joint work with Phoebe Buckheister)
Given at MFCS 2013 in Klosterneuburg, Austria
Abstract
Valence automata are a generalization of various models of automata with storage. Here, each edge carries, in addition to an input word, an element of a monoid. A computation is considered valid if multiplying the monoid elements on the visited edges yields the identity element. By choosing suitable monoids, a variety of automata models can be obtained as special valence automata. This work is concerned with the accepting power of valence automata. Specifically, we ask for which monoids valence automata can accept only context-free languages or only languages with semilinear Parikh image, respectively. First, we present a characterization of those graph products (of monoids) for which valence automata accept only context-free languages. Second, we provide a necessary and sufficient condition for a graph product of copies of the bicyclic monoid and the integers to yield only languages with semilinear Parikh image when used as a storage mechanism in valence automata. Third, we show that all languages accepted by valence automata over torsion groups have a semilinear Parikh image.

Rational Subsets and Submonoids of Wreath Products
(joint work with Markus Lohrey and Benjamin Steinberg)
Given at ICALP 2013 in Riga, Latvia
Abstract
It is shown that membership in rational subsets of wreath products $H \wr V$ with $H$ a finite group and $V$ a virtually free group is decidable. On the other hand, it is shown that there exists a fixed finitely generated submonoid in the wreath product $\mathbb{Z}\wr\mathbb{Z}$ with an undecidable membership problem.

Silent Transitions in Automata with Storage
Given at ICALP 2013 in Riga, Latvia
Abstract
We consider the computational power of silent transitions in one-way automata with storage. Specifically, we ask which storage mechanisms admit a transformation of a given automaton into one that accepts the same language and reads at least one input symbol in each step.
We study this question using the model of valence automata. Here, a finite automaton is equipped with a storage mechanism that is given by a monoid.
This work presents generalizations of known results on silent transitions. For two classes of monoids, it provides characterizations of those monoids that allow the removal of silent transitions. Both classes are defined by graph products of copies of the bicyclic monoid and the group of integers. The first class contains pushdown storages as well as the blind counters while the second class contains the blind and the partially blind counters.

Valence automata as a generalization of automata with storage
Given at ALFA'13 in Riga, Latvia
Abstract
A valence automaton over a monoid M is a finite automaton in which each edge carries an input word and an element of M. A word is then accepted if there is a run that spells the word such that the product of the monoid elements is the identity. By choosing appropriate monoids M, one can obtain various kinds of automata with storage as special valence automata. Examples include pushdown automata, blind multicounter automata, and partially blind multicounter automata. Therefore, valence automata offer a framework to generalize results on such automata with storage. This talk will present recent advances in this direction. The addressed questions include: For which monoids can we accept non-regular languages? For which monoids can we determinize automata? For which monoids do we have a Parikh's Theorem (as for pushdown automata)?

Valence automata as a generalization of automata with storage
Given at D-CON 2013 in Lübeck, Germany
Abstract
A valence automaton over a monoid $M$ is a finite automaton in which each edge carries an input word and an element of $M$. A word is then accepted if there is a run that spells the word such that the product of the monoid elements is the identity. By choosing appropriate monoids $M$, one can obtain various kinds of automata with storage as special valence automata. Examples include pushdown automata, blind multicounter automata, and partially blind multicounter automata. Therefore, valence automata offer a framework to generalize results on such automata with storage. This talk will present recent results on valence automata. The addressed questions include: For which monoids can we accept non-regular languages? For which monoids can we determinize automata? For which monoids can we avoid silent edges (i.e., those which read no input symbol)?

Valence automata as a generalization of automata with storage
Given at Algebra and Cryptography Seminar at CUNY Graduate Center in New York City, USA
Abstract
A valence automaton over a monoid M is a finite automaton in which each edge carries an input word and an element of M. A word is then accepted if there is a run that spells the word such that the product of the monoid elements is the identity.
By choosing appropriate monoids M, one can obtain various kinds of automata with storage as special valence automata. Examples include pushdown automata, blind multicounter automata, and partially blind multicounter automata. Therefore, valence automata offer a framework to generalize results on such automata with storage.
This talk will present recent results on valence automata. The addressed questions include: For which monoids can we accept non-regular languages? For which monoids can we determinize automata? For which monoids can we avoid silent edges (i.e., those which read no input symbol)?

Silent Transitions in Valence Automata
Given at Seminar "Algebraic and Logical Foundations of Computer Science" at Universität Leipzig in Germany
Abstract
We consider the problem of eliminating silent transitions from one-way automata with storage. It is known that in pushdown automata and in blind multicounter automata (where the counter values can become negative and are only zero-tested in the end), silent transitions can be avoided. On the other hand, in the case of partially blind multicounter automata (where the counter values are always non-negative and are only zero-tested in the end), silent transitions are necessary to accept all languages. In order to study the expressive power of silent transitions in greater generality, we use the model of valence automata. Here, a finite automaton is equipped with a storage mechanism that is given by a monoid. Since many models of automata with storage (including all of the above) arise as special valence automata, our question is: for which monoids can silent transitions be avoided? This work presents generalizations of the results above. For two classes of monoids, it provides characerizations of those monoids that allow the removal of silent transitions. Both classes are defined by graph products of copies of the bicyclic monoid and the group of integers.

Monoid Control for Grammars, Automata, and Transducers
Given at Theorietag "Automaten und formale Sprachen" 2011 in Allrode, Germany
Abstract
During recent decades, classical models in language theory have been extended by control mechanisms defined by monoids. We study which monoids cause the extensions of context-free grammars, finite automata, or finite state transducers to exceed the capacity of the original model. Furthermore, we investigate when, in the extended automata model, the nondeterministic variant differs from the deterministic one in capacity. We show that all these conditions are in fact equivalent and present an algebraic characterization. In particular, the open question of whether every language generated by a valence grammar over a finite monoid is context-free is provided with a positive answer.

A Sufficient Condition for Erasing Productions to Be Avoidable
Given at DLT 2011 in Milano, Italy
Abstract
In each grammar model, it is an important question whether erasing productions are necessary to generate all languages. Using the concept of grammars with control languages by Salomaa, which offers a uniform treatment of a variety of grammar models, we present a condition on the class of control languages that guarantees that erasing productions are avoidable in the resulting grammar model. On the one hand, this generalizes the previous result that in Petri net controlled grammars, erasing productions can be eliminated. On the other hand, it allows us to infer that the same is true for vector grammars.

On the Capabilities of Grammars, Automata, and Transducers Controlled by Monoids
Given at ICALP 2011 in Zürich, Switzerland
Abstract
During recent decades, classical models in language theory have been extended by control mechanisms defined by monoids. We study which monoids cause the extensions of context-free grammars, finite automata, or finite state transducers to exceed the capacity of the original model. Furthermore, we investigate when, in the extended automata model, the nondeterministic variant differs from the deterministic one in capacity. We show that all these conditions are in fact equivalent and present an algebraic characterization. In particular, the open question of whether every language generated by a valence grammar over a finite monoid is context-free is provided with a positive answer.

On Erasing Productions in Random Context Grammars
Given at ICALP 2010 in Bordeaux, France
Abstract
Three open questions in the theory of regulated rewriting are addressed. The first is whether every permitting random context grammar has a non-erasing equivalent. The second asks whether the same is true for matrix grammars without appearance checking. The third concerns whether permitting random context grammars have the same generative capacity as matrix grammars without appearance checking. The main result is a positive answer to the first question. For the other two, conjectures are presented. It is then deduced from the main result that at least one of the two holds.

Erasing in Petri Net Languages and Matrix Grammars
Given at DLT 2009 in Stuttgart, Germany
Abstract
It is shown that applying linear erasing to a Petri net language yields a language generated by a non-erasing matrix grammar. The proof uses Petri net controlled grammars. These are context-free grammars, where the application of productions has to comply with a firing sequence in a Petri net. Petri net controlled grammars are equivalent to arbitrary matrix grammars (without appearance checking), but a certain restriction on them (linear Petri net controlled grammars) leads to the class of languages generated by non-erasing matrix grammars. It is also shown that in Petri net controlled grammars (with final markings and arbitrary labeling), erasing rules can be eliminated, which yields a reformulation of the problem of whether erasing rules in matrix grammars can be eliminated.

Labeled Step Sequences in Petri Nets
(joint work with Matthias Jantzen)
Given at PETRI NETS 2008 in Xi'an, China
Abstract
We compare various modes of firing transitions in Petri nets and define classes of languages defined this way. We define languages through steps, i. e. sets of transitions, maximal steps, multi-steps, and maximal multi-steps of transitions in Petri nets, but in a different manner than those defined in [Burk 81a,Burk 83], by considering labeled transitions. We will show that we obtain a hierarchy of families of languages defined by multiple use of transition in firing transitions in a single multistep. Except for the maximal multi-steps all classes can be simulated by sequential firing of transitions.

Concurrent Finite Automata
(joint work with Matthias Jantzen and Manfred Kudlek)
Given at Theorietag "Automaten und formale Sprachen" 2007 in Leipzig, Germany
Abstract
We present a generalization of finite automata using Petri nets as control. Acceptance is defined by final markings of the Petri net. The class of languages obtained by $\lambda$-free concurrent finite automata contains both the class of regular sets and the class of Petri net languages defined by final marking.