ERRORS IN FINITE AUTOMATA.
Abstract
The correctability properties of errors is studied in a finite automaton driven by a random source. An error is defined to be a pair of states and is corrected by a tape if the tape takes both coordinates of the pair into the same state. Errors are classified as one of four types: correctable, finite, definite, and non-correctable. A correctable error is an error for which there is a correcting tape. The error is finite if the probability of the set of correcting tapes approaches one as the length of the tapes gets longer. A definite error is an error for which all tapes, of length greater than some fixed length, are correcting tapes. A non-correctable error is one for which there does not exist a correcting tape. The set of finite errors induces a partition, called the finite error partition, on the set of states. The notation of the semigroup of the automaton is introduced. Necessary and sufficient conditions are given for the automaton to have errors which are correctable but not finite and for the automaton to have only definite or non-correctable errors. The error properties are given for finite automata which have a large number of states but can be decomposed into a series, parallel connection of smaller automata. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1965
- Accession Number
- AD0627374
Entities
People
- Philip S. Dauber