
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 pisimulation, homorphic realization, expansion limited realization and isomorphic realization does not and simulation allows computational slowup which homomorphic realization does not. In mutual pisimulation 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