Geodesic
Complexity of some problems in editing words
Diskretnaya Matematika, Tome 1 (1989) no. 4, pp. 104-112 
S. S. Martynov. Complexity of some problems in editing words. Diskretnaya Matematika, Tome 1 (1989) no. 4, pp. 104-112. http://geodesic.mathdoc.fr/item/DM_1989_1_4_a10/
@article{DM_1989_1_4_a10,
     author = {S. S. Martynov},
     title = {Complexity of some problems in editing words},
     journal = {Diskretnaya Matematika},
     pages = {104--112},
     year = {1989},
     volume = {1},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_1989_1_4_a10/}
}
TY  - JOUR
AU  - S. S. Martynov
TI  - Complexity of some problems in editing words
JO  - Diskretnaya Matematika
PY  - 1989
SP  - 104
EP  - 112
VL  - 1
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DM_1989_1_4_a10/
LA  - ru
ID  - DM_1989_1_4_a10
ER  - 
%0 Journal Article
%A S. S. Martynov
%T Complexity of some problems in editing words
%J Diskretnaya Matematika
%D 1989
%P 104-112
%V 1
%N 4
%U http://geodesic.mathdoc.fr/item/DM_1989_1_4_a10/
%G ru
%F DM_1989_1_4_a10

Voir la notice de l'article provenant de la source Math-Net.Ru

By the editing of a word $S$ with respect to a language $L$ is meant a procedure for choosing a minimal sequence of operations from a given set of operations $\varPhi$ that translates $S$ into some word of $L$. Under the assumption that the set $\varPhi$ consists of operations of removal of letters, insertion of letters, replacement of one letter by another and transposition of a pair of letters, we establish $NP$-completeness of a problem of editing with respect to language $L$ with constraints on the set of subwords that occur in words of the language.