Automaton mappings of words that propagate distortions in Hamming and Levenshte\u\i n metrics no more than $K$ times

A. V. Babash

Diskretnaya Matematika, Tome 14 (2002) no. 3, pp. 78-94

Résumé

Let $I$ and $O$ be finite alphabets. For a finite alphabet $\Omega$, let $\Omega^*$ denote the set of all words of finite lengths over the alphabet $\Omega$. In this paper we give a complete description of all automaton mappings of the set $I^*$ into $O^*$ which multiply symbol replacement errors in words by a factor not exceeding $K$. We give a complete description of injective automaton mappings of the set $I^*$ into $O^*$ which multiply symbol skip errors by a factor no greater than $K$. A similar result is obtained for the deletion and insertion metric.