Accession Number : AD0681082

Title :   ON THE FEEDBACK COMPLEXITY OF AUTOMATA.

Descriptive Note : Technical rept.,

Corporate Author : MICHIGAN UNIV ANN ARBOR LOGIC OF COMPUTERS GROUP

Personal Author(s) : Zeigler,Bernard Phillip

Report Date : JAN 1969

Pagination or Media Count : 162

Abstract : Given a behavior, as embodied in a finite state transition function what is the minimum level of feedback complexity required by a logical net which can simulate this behavior. For any given level of complexity is there a transition function which cannot be simulated by any logical net characterized by this complexity level. To answer these questions we: (1) Consider five main classes of behavior realization: simulation, mutual pi-simulation, homorphic realization, expansion limited realization and isomorphic realization does not and simulation allows computational slow-up which homomorphic realization does not. In mutual pi-simulation the semigroup must be preserved while expansion limited realization corresponds to the use of covers for state splitting; (2) Construct representing digraphs for logical nets and characterize the reduced digraph of a simulation; (3) Select as measures of complexity of a logical net: (a) the size of the largest strong component of its representing digraph and (b) the largest of feedback indegrees of the points in the representing digraph. Here the feedback indegree of a point is the number of input lines it receives from points in the same strong component. (Author)

Descriptors :   (*ARTIFICIAL INTELLIGENCE, AUTOMATA), (*LEARNING MACHINES, FEASIBILITY STUDIES), GROUPS(MATHEMATICS), SET THEORY, GRAPHICS, COMPUTER LOGIC, FEEDBACK, SIMULATION, THESES

Subject Categories : Bionics

Distribution Statement : APPROVED FOR PUBLIC RELEASE