Input-Error-Limiting Automata

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.