THEORY OF ADAPTIVE MECHANISMS. PART IV. DETERMINISTIC REALIZATION AND SIMULATION OF NONDETERMINISTIC AUTOMATA.
Final technical rept. 8 Aug 66-31 Oct 69,
SYRACUSE UNIV RESEARCH INST N Y
Pagination or Media Count:
The report investigates the deterministic realization of nondeterministic finite automata through the subset construction. It had been speculated by Rabin that the exponential increase in the number of states in this construction could be improved. Contrary to this a class of nondeterministic automata is constructed by the author for which the subset construction yields a reduced, connected deterministic automata with exactly 2 to the n power states. Author
- Computer Programming and Software