ON THE FEEDBACK COMPLEXITY OF AUTOMATA.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1969
- Accession Number
- AD0681082
Entities
People
- Bernard Phillip Zeigler
Organizations
- University of Michigan