On the identification of a finite automaton by its input and output sequences in case of distortions

Sergey Melnikov, Konstantin Samouylov, Andrey Zyazin
A method is proposed for checking whether a pair of observed distorted sequences can correspond to the true input and output sequences of a reference automaton, provided that the initial state of the automaton is unknown, and the proportion of deletions, insertions, and replacements of symbols is small.