52 citations · 206 across the 25 of their papers we have counts for
5 papers · 1 filter
Efficient reduction of nondeterministic automata with application to language inclusion testing
Lorenzo Clemente, Richard Mayr
We present efficient algorithms to reduce the size of nondeterministic Büchi word automata (NBA) and nondeterministic finite word automata (NFA), while retaining their languages. A…
Reduction of Nondeterministic Tree Automata
Ricardo Almeida, Lukáš Holík, Richard Mayr
We present an efficient algorithm to reduce the size of nondeterministic tree automata, while retaining their language. It is based on new transition pruning techniques, and quotie…
Simulation Over One-counter Nets is PSPACE-Complete
Piotr Hofman, Slawomir Lasota, Richard Mayr +1
One-counter nets (OCN) are Petri nets with exactly one unbounded place. They are equivalent to a subclass of one-counter automata with just a weak test for zero. Unlike many other…
Decidability of Weak Simulation on One-counter Nets
Piotr Hofman, Richard Mayr, Patrick Totzke
One-counter nets (OCN) are Petri nets with exactly one unbounded place. They are equivalent to a subclass of one-counter automata with only a weak test for zero. We show that weak…
Advanced Automata Minimization
Lorenzo Clemente, Richard Mayr
We present an efficient algorithm to reduce the size of nondeterministic Buchi word automata, while retaining their language. Additionally, we describe methods to solve PSPACE-comp…