Accession Number : AD0711050

Title :   THEORY OF ADAPTIVE MECHANISMS. PART IV. DETERMINISTIC REALIZATION AND SIMULATION OF NONDETERMINISTIC AUTOMATA.

Descriptive Note : Final technical rept. 8 Aug 66-31 Oct 69,

Corporate Author : SYRACUSE UNIV RESEARCH INST N Y

Personal Author(s) : Moore,F. R.

Report Date : JUL 1970

Pagination or Media Count : 83

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)

Descriptors :   (*ARTIFICIAL INTELLIGENCE, AUTOMATA), (*LEARNING MACHINES, THEORY), ADAPTIVE SYSTEMS, CONTROL SEQUENCES, OPTIMIZATION, PROBLEM SOLVING, SIMULATION, STOCHASTIC PROCESSES, REPORTS

Subject Categories : Computer Programming and Software
      Bionics

Distribution Statement : APPROVED FOR PUBLIC RELEASE