Register Automata with Extrema Constraints, and an Application to Two-Variable Logic
Szymon Toruńczyk, Thomas Zeume · 2020
We introduce a model of register automata over infinite trees with extrema constraints. Such an automaton can store elements of a linearly ordered domain in its registers, and can compare those values to the suprema and infima of register values in subtrees. We show that the emptiness problem for these automata is decidable.