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

A. V. Babash


Abstract: 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.

UDC: 519.7

Received: 18.09.2001

DOI: 10.4213/dm256

 English version: Discrete Mathematics and Applications, 2002, 12:4, 375–392

Bibliographic databases:

• 
•