### Synchronizations and General Repetitive Machines, with Applications to Ultimate Definite AutomataSynchronizations and General Repetitive Machines, with Applications to Ultimate Definite Automata

Access Restriction
Subscribed

 Author Reynolds, R. G. ♦ Cutlip, W. F. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1969 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract Let $\textit{s}$ and $\textit{t}$ be states of a finite (deterministic) automaton $\textit{A}.$ $\textit{t}$ can be reached from $\textit{s}$ if there is a tape $\textit{x}$ such that, if $\textit{A}$ is in state $\textit{s}$ and receives $\textit{x},$ $\textit{A}$ goes to state $\textit{t}.We$ consider (1) automata in which the initial state can be reached from any final state, and (2) automata which can be brought to a known state from any unknown state by applying a predetermined tape $\textit{x}.Necessary$ and sufficient conditions for an ultimate definite automaton to have the former property are obtained. Every ultimate definite automaton $\textit{A}$ is shown to have the latter property; and a characterization is obtained for all tapes which bring $\textit{A}$ to a known state. Finally, those ultimate definite automata having the former property are shown to be precisely those which can be brought to the start state from any state by some tape $\textit{x}.$ ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1969-04-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 16 Issue Number 2 Page Count 9 Starting Page 226 Ending Page 234

#### Open content in new tab

Source: ACM Digital Library