Optimal simulation of self-verifying automata by deterministic automata

摘要

Self-verifying automata are a special variant of finite automata with a symmetric kind of nondeterminism. We study the conversion of self-verifying automata to deterministic automata from a descriptional complexity point of view. The main result is the exact cost, in terms of the number of states, of such a simulation.