ERRORS IN FINITE AUTOMATA.
SYSTEMS ENGINEERING LAB UNIV OF MICHIGAN ANN ARBOR
Pagination or Media Count:
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
- Electrical and Electronic Equipment
- Statistics and Probability