Georg Zetzsche
Mail address
LSV, CNRS & ENS de Cachan
61, avenue du Président Wilson
94235 CACHAN Cedex
France
Office
RH-B-002
Email
zetzsche(at)lsv(dot)fr

Since November 2015, I am a Postdoc at the LSV Cachan, funded by a fellowship of the DAAD (German Academic Exchange Service). 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 mostly concerned with questions of expressiveness and decidability for infinite-state systems. Topics I have worked on include (in no particular order):

This year, I'm attending the following events:

Publications [ back to top ]
Recent

The Emptiness Problem for Valence Automata over Graph Monoids
Submitted to journal, 2016
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.
The cases that are proven decidable together make up 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.

The Monoid of Queue Actions
with Martin Huschenbett and Dietrich Kuske
Submitted to journal, 2016
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
Submitted to journal, 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$.

Permutations of context-free, ET0L and indexed languages
with Tara Brough, Laura Ciobanu, and Murray Elder
Accepted for Discrete Mathematics & Theoretical Computer Science, 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.

On Boolean closed full trios and rational Kripke frames
with Dietrich Kuske and Markus Lohrey
Accepted for Theory of Computing Systems, 2016
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.

Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
with Daniel König and Markus Lohrey
Accepted for Contemporary Mathematics, 2016

The complexity of downward closure comparisons
Accepted for 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.

Complexity of regular abstractions of one-counter languages
with Mohamed Faouzi Atig, Dmitry Chistikov, Piotr Hofman, K Narayan Kumar, and Prakash Saivasan
Accepted for 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
Accepted for 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.

Conference contributions

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.

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

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

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.

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.

Reviewing [ back to top ]

I have reviewed submissions for Algorithmica, ACM TECS, IJFCS, IJAC, DMTCS, 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, and MFCS 2016.

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

Valence automata as a generalization of automata with storage
Given at ALFA'13, 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)?

Recent Results on Erasing in Regulated Rewriting
Given at Theorietag 2011, 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

Monoids as Storage Mechanisms
Given at Seminar of the INFINI group at LSV in December 2015, 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.

The Emptiness Problem for Valence Automata or: Another Decidable Extension of Petri Nets
Given at RP 2015, 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 Cosures
Given at Theorietag 2015, 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).

An Approach to Computing Downward Closures
Given at ICALP 2015, 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, Kyoto, Japan

Computing downward closures for stacked counter automata
Given at STACS 2015, 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 October 2014, 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, Kaiserslautern, Germany

Of stacks (of stacks (...) with blind counters) with blind counters
Given at AISS 2014, 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, 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 Theorietag 2013, 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 2013, 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, 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, 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, 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 D-CON 2013, 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)?

Monoid Control for Grammars, Automata, and Transducers
Given at Theorietag 2011, 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, 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, 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, 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, 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, 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 2007, 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.