RU
On the complexity of converting pairs of words with respect to drop-in operations of a special type
Published: 2023, vol. 27, issue 3, pp. 122–136
Abstract
This article is devoted to finding the distance between pairs of words in a general finite alphabet under the action of the operation of replacing one letter into two (adjacent) and calculating the corresponding shortest chain of substitutions (if it exists). Initially, the problem was posed in a more general formulation for a pair of regular languages, but later the formulation of the problem was clarified. At the same time, two possibilities are considered - with the permission to replace letters that were previously absent in the original word or with the prohibition of such operations. This direction is relevant and can be used, for example, in the theory of noise-resistant coding. In particular, it is worth mentioning the Levenstein metric, which inspires similar research on a new type of letter substitution operations.
Keywords: text recognition, Levenshtein distance, metric, optimal algorithm.
BibTeX
@article{IS-Dergach-Amirova2023,
author = {Dergach, Peter Sergeevich and Amirova, Sabina Rovshan},
title = {{On the complexity of converting pairs of words with respect to drop-in operations of a special type}},
journal = {Intelligent Systems. Theory and Applications},
year = {2023},
volume = {27},
number = {3},
pages = {122--136},
}
AMSBIB
\Bibitem{IS-Dergach-Amirova2023}
\by P.\,S.~Dergach, S.\,R.~Amirova
\paper On the complexity of converting pairs of words with respect to drop-in operations of a special type
\jour Intelligent Systems. Theory and Applications
\yr 2023
\vol 27
\issue 3
\pages 122--136
\lang In Russian