Article ID Journal Published Year Pages File Type
10330785 Information and Computation 2011 8 Pages PDF
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
Optimal simulation of self-verifying automata by deterministic automata
Authors
, ,