Accession Number : AD0677291

Title :   STRUCTURE OF EVENTS AND AUTOMATA,

Corporate Author : MICHIGAN STATE UNIV EAST LANSING DIV OF ENGINEERING RESEARCH

Personal Author(s) : Reynolds,B. G. ; Kilmer,W. L.

Report Date : 31 AUG 1968

Pagination or Media Count : 68

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)

Descriptors :   (*DIGITAL COMPUTERS, AUTOMATA), THEORY, SYNCHRONIZATION(ELECTRONICS), SEQUENCES(MATHEMATICS), THEOREMS, SET THEORY, COMBINATORIAL ANALYSIS, COMPUTER LOGIC

Subject Categories : Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE