Automaton mappings of words which multiply errors by a factor no greater than K in the Hamming and Levenshtein metrics
Aleksandr Vladimirovich Babash · Discrete Mathematics and Applications · 2002
Abstract Let I and O be finite alphabets. For a finite alphabet Ω, let Ω* denote the set of all words of finite lengths over the alphabet Ω. 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 1* 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.