4 papers
History-Deterministic Büchi Automata are Succinct
Antonio Casares, Keya Prakash, K. S. Thejaswini
We describe a history-deterministic Büchi automaton that has strictly less states than every language-equivalent deterministic Büchi automaton. This solves a problem that had bee…
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…
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…
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…