
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 onetoone 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 ultimatedefinite 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. Ultimatedefinite 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