3 papers
cs.FL2025
Explorability in Pushdown Automata
Ayaan Bedi, Karoliina Lehtinen
We study explorability, a measure of nondeterminism in pushdown automata, which generalises history-determinism. An automaton is k-explorable if, while reading the input, it suffic…
cs.FL2025
Using games and universal trees to characterise the nondeterministic index of tree languages
Olivier Idir, Karoliina Lehtinen
The parity index problem of tree automata asks, given a regular tree language and a set of priorities , is -feasible, that is, recognised by a nondeterministic parity…
cs.FL2025
The 2-Token Theorem: Recognising History-Deterministic Parity Automata Efficiently
Karoliina Lehtinen, Keya Prakash
History-determinism is a restricted notion of nondeterminism in automata, where the nondeterminism can be successfully resolved based solely on the prefix read so far. History-dete…