Deterministic Büchi automata recognize omega-regular languages — infinite sequences that satisfy a repetition condition. For any such language, there exists a deterministic automaton that accepts exactly the words in the language. The question is how many states it needs.
Nondeterministic automata can be exponentially smaller than deterministic ones, but they sacrifice the step-by-step decidability that makes deterministic automata useful for verification and synthesis. History-deterministic automata sit between: they resolve nondeterministic choices based on the input read so far, without seeing the future. They combine the operational advantages of determinism with some of the compactness of nondeterminism.
Casares, Prakash, and Thejaswini settle a decade-old question: history-deterministic Büchi automata can be strictly smaller than any equivalent deterministic Büchi automaton. Their construction uses 65 states to recognize a language that requires more states in any deterministic version. The proof combines theoretical analysis with computational verification — an exhaustive check that no smaller deterministic automaton recognizes the same language.
The through-claim is about the cost of commitment. A deterministic automaton commits to a single transition at each step, paying for this commitment in states — it needs more states to encode the information that a nondeterministic automaton carries in its set of possible states. History-determinism recovers some of this cost by deferring commitment: the transition depends on the full history, not just the current state. The automaton still makes a single choice at each step, but the choice is informed by everything it has seen. This additional information — the history — lets it navigate with fewer states. Memory reduces the need for structure.