2 citations · 2 across the 4 of their papers we have counts for
Showing 2025Show all
3 papers · 1 filter
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…
cs.FL2025
Resolving Nondeterminism with Randomness
Thomas A. Henzinger, Keya Prakash, K. S. Thejaswini
In automata theory, while determinisation provides a standard route to solving many common problems in automata theory, some weak forms of nondeterminism can be dealt with in some…
cs.FL2025
History-Deterministic Parity Automata: Games, Complexity, and the 2-Token Theorem
Keya Prakash
History-deterministic automata are a restricted class of nondeterministic automata where the nondeterminism while reading an input can be resolved successfully based on the prefix…