Reachability Problems
16th International Conference, RP 2022, Kaiserslautern, Germany, October 17–21, 2022, Proceedings
Page
%P
-
Chapter and Conference Paper
Unboundedness Problems for Machines with Reversal-Bounded Counters
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 ...
-
Book and Conference Proceedings
-
Chapter and Conference Paper
General Decidability Results for Asynchronous Shared-Memory Programs: Higher-Order and Beyond
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 undecida...
-
Chapter and Conference Paper
Recent Advances on Reachability Problems for Valence Systems (Invited Talk)
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 pa...
-
Chapter and Conference Paper
Coverability Is Undecidable in One-Dimensional Pushdown Vector Addition Systems with Resets
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 ...
-
Chapter and Conference Paper
Languages Ordered by the Subword Order
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 quan...
-
Article
Knapsack in Graph Groups
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 every graph group. This result even holds if the group elements are...
-
Article
The monoid of queue actions
We model the behavior of a fifo-queue as a monoid of transformations that are induced by sequences of writing and reading. We describe this monoid by means of a confluent and terminating semi-Thue system and s...
-
Article
On Boolean Closed Full Trios and Rational Kripke Frames
We study what languages can be constructed from a non-regular language L using Boolean operations and synchronous or non-synchronous rational transductions. If all rational transductions are allowed, one can cons...
-
Chapter and Conference Paper
The Emptiness Problem for Valence Automata or: Another Decidable Extension of Petri Nets
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 stora...
-
Chapter and Conference Paper
An Approach to Computing Downward Closures
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...
-
Chapter and Conference Paper
The Monoid of Queue Actions
We model the behavior of a fifo-queue as a monoid of transformations that are induced by sequences of writing and reading. We describe this monoid by means of a confluent and terminating semi-Thue system and s...
-
Chapter and Conference Paper
Semilinearity and Context-Freeness of Languages Accepted by Valence Automata
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...
-
Chapter and Conference Paper
Rational Subsets and Submonoids of Wreath Products
It is shown that membership in rational subsets of wreath products H ≀ 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 generate...
-
Chapter and Conference Paper
Silent Transitions in Automata with Storage
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 s...
-
Chapter and Conference Paper
A Sufficient Condition for Erasing Productions to Be Avoidable
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 t...
-
Chapter and Conference Paper
On the Capabilities of Grammars, Automata, and Transducers Controlled by Monoids
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...
-
Chapter and Conference Paper
On Erasing Productions in Random Context Grammars
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 ...
-
Chapter and Conference Paper
Erasing in Petri Net Languages and Matrix Grammars
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, wher...
-
Chapter and Conference Paper
Labeled Step Sequences in Petri Nets
We compare various modes of firing transitions in Petri nets and investigate classes of languages specified by them. We define languages through steps, (i. e., sets of transitions), maximal steps, multi-steps,...
