6 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 been…
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…
History-Determinism vs Fair Simulation
Udi Boker, Thomas A. Henzinger, Karoliina Lehtinen +1
An automaton is history-deterministic if its nondeterminism can be resolved on the fly, only using the prefix of the word read so far. This mild form of nondeterminism has attracte…
Lookahead Games and Efficient Determinisation of History-Deterministic Büchi Automata
Rohan Acharya, Marcin Jurdziński, Keya Prakash
Our main technical contribution is a polynomial-time determinisation procedure for history-deterministic Büchi automata, which settles an open question of Kuperberg and Skrzypczak,…