Skip to main content

History-Determinism vs. Fair-Simulation

Udi Boker ( Reichman University )

An automaton is history-deterministic if its nondeterminism can be resolved on the fly, only using the prefix of the word read so far. An automaton A is guidable with respect to a class C of automata if it can fairly simulate every automaton B in C, whose language is contained in that of A. In other words, guidable automata are those for which inclusion and simulation coincide.