STRUCTURE OF EVENTS AND AUTOMATA,
Abstract
The relations between certain structural aspects of automata and their accepted events are investigated. A general repetitive machine is an automaton having a path from every final state to the start state. The general repetitive machines contain as a proper subclass the strongly connected machines. General repetitive events are defined in terms of certain 'factorization' properties of the associated regular expressions, and a one-to-one onto correspondence is shown between general repetitive machines and general repetitive events. Definite and ultimate definite general repetitive machines are investigated, and a number of properties exhibited. All ultimate-definite automata are synchronizable; that is, there is an input sequence which causes the machine to move to a predetermined state regardless of the state of the machine before applying the sequence. Ultimate-definite general repetitive machines are shown to be strongly connected and hence synchronizable to the start state. The structure question is also pursued from the viewpoint of a machine's cascade decomposition (Zeiger's method). An input to a component machine of a Zeiger cascade either permutes the states or resets to one state. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 31, 1968
- Accession Number
- AD0677291
Entities
People
- B. G. Reynolds
- W. L. Kilmer
Organizations
- Michigan State University