32 citations · 149 across the 42 of their papers we have counts for
9 papers · 1 filter
History-deterministic Parikh Automata
Enzo Erlich, Mario Grobler, Shibashis Guha +3
Parikh automata extend finite automata by counters that can be tested for membership in a semilinear set, but only at the end of a run. Thereby, they preserve many of the desirable…
Parikh Automata over Infinite Words
Shibashis Guha, Ismaël Jecker, Karoliina Lehtinen +1
Parikh automata extend finite automata by counters that can be tested for membership in a semilinear set, but only at the end of a run, thereby preserving many of the desirable alg…
Efficient Monitoring of Timed Properties
Thomas Møller Grosen, Sean Kauffman, Kim Guldstrand Larsen +1
In this paper we study monitoring of real-time systems with respect to properties given by a pair of Timed Büchi Automata, one for the property and one for its complement. This inc…
Weak Muller Conditions Make Delay Games Hard
Sarah Winter, Martin Zimmermann
We show that solving delay games with winning conditions given by deterministic and nondeterministic weak Muller automata is 2EXPTIME-complete respectively 3EXPTIME-complete. Furth…
A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct
Shibashis Guha, Ismaël Jecker, Karoliina Lehtinen +1
We study the expressiveness and succinctness of history-deterministic pushdown automata (HD-PDA) over finite words, that is, pushdown automata whose nondeterminism can be resolved…
Approximating the Minimal Lookahead Needed to Win Infinite Games
Martin Zimmermann
We present an exponential-time algorithm approximating the minimal lookahead necessary to win an -regular delay game.