Accession Number:

AD0677291

Title:

STRUCTURE OF EVENTS AND AUTOMATA,

Descriptive Note:

Corporate Author:

MICHIGAN STATE UNIV EAST LANSING DIV OF ENGINEERING RESEARCH

Personal Author(s):

Report Date:

1968-08-31

Pagination or Media Count:

68.0

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 machines cascade decomposition Zeigers method. An input to a component machine of a Zeiger cascade either permutes the states or resets to one state. Author

Subject Categories:

  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE