40 citations · 57 across the 12 of their papers we have counts for
4 papers · 1 filter
History Determinism vs. Good for Gameness in Quantitative Automata
Udi Boker, Karoliina Lehtinen
Automata models between determinism and nondeterminism/alternations can retain some of the algorithmic properties of deterministic automata while enjoying some of the expressivenes…
Token Games and History-Deterministic Quantitative-Automata
Udi Boker, Karoliina Lehtinen
A nondeterministic automaton is history-deterministic if its nondeterminism can be resolved by only considering the prefix of the word read so far. Due to their good compositional…
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…
A Recursive Approach to Solving Parity Games in Quasipolynomial Time
Karoliina Lehtinen, Paweł Parys, Sven Schewe +1
Zielonka's classic recursive algorithm for solving parity games is perhaps the simplest among the many existing parity game algorithms. However, its complexity is exponential, whil…