Nondeterminism probably makes your favourite deterministic automata model more expressive, or at least more succinct. This usually comes at the cost of algorithmic complexity. Classes of automata in between deterministic and nondeterministic ones offer different trade-offs with respect to expressivity, succinctness and algorithmic properties.

History deterministic automata (sometimes known as good-for-games automata) are nondeterministic automata in which nondeterministic choices can be resolved on the fly, without knowledge of the future of a word. They combine some of the succinctness and expressivity of nondeterministic automata with some of the useful algorithmic properties of deterministic automata. In particular, games with winning conditions given by history-deterministic automata tend to be simpler to solve than games with nondeterministic winning conditions.

In this talk, I will give an overview of history-deterministic automata and their relation to various synthesis problems, survey recent developments in the area for different classes of automata and point to some of the hard questions that remain unanswered and some areas that remain unexplored.