Input-Error-Limiting Automata
- 1 July 1964
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 11 (3) , 338-351
- https://doi.org/10.1145/321229.321236
Abstract
Some properties of automata are investigated, which are capable of limiting the effect of input errors on their behavior. First necessary and sufficient conditions arc derived for an automaton to be capable of always being resynchronized within a bo~mded xmmber of input letters after an error has occurred, and then the results are specialized to finit e-state completely specified automata. Automata are investigated, which are capable of being resynchronized with probability one and it is shown that a finite-state completely specified automaton possesses this property if and only if there exists a finite sequence which is a universal synchronizer for the automaton. Some connections with similar problems for vari~bleAength codes are indicated.Keywords
This publication has 2 references indexed in Scilit:
- Operations on finite automataPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1961
- Variable-Length Binary EncodingsBell System Technical Journal, 1959