Tolerant Automata and Variable Length Coding.
Abstract
Tolerant automata are finite state machines which, in due time, can recover their correct state after a change or transformation in the input sequence. A given finite state machine can tolerate, or be synchronized with respect to, a specific set of transformations depending on the machine. The synchronization is achieved by introduction of certain sequences in the input called universal synchronizers. Effective procedures exist for determining the set of tolerable transformations in the input sequence and the set of universal synchronizers, for any given finite state machine. Conversely, it is often possible to find all the finite state machines which can tolerate a given set of transformations. The question whether this can be done is, in general, undecidable. For individual cases it is usually possible to solve the problem. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1972
- Accession Number
- AD0749551
Entities
People
- Iraj Dara Mansoori
Organizations
- University of Southern California