THEORY OF ADAPTIVE MECHANISMS. PART IV. DETERMINISTIC REALIZATION AND SIMULATION OF NONDETERMINISTIC AUTOMATA.
Abstract
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1970
- Accession Number
- AD0711050
Entities
People
- F. R. Moore
Organizations
- Syracuse University