Geodesic
NP-completeness of special string editing problems
Matematičeskie voprosy kriptografii, Tome 4 (2013), pp. 77-93

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

We establish the NP-completeness of the string editing problems with respect to a language defined by restrictions on a subwords of its words. The editing operations consists in a replacement of the substrings belonging to a specified block code, by the words of another block code. 
@article{MVK_2013_4_a5,
     author = {S. S. Martynov},
     title = {NP-completeness of special string editing problems},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {77--93},
     publisher = {mathdoc},
     volume = {4},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2013_4_a5/}
}
TY  - JOUR
AU  - S. S. Martynov
TI  - NP-completeness of special string editing problems
JO  - Matematičeskie voprosy kriptografii
PY  - 2013
SP  - 77
EP  - 93
VL  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MVK_2013_4_a5/
LA  - ru
ID  - MVK_2013_4_a5
ER  - 
%0 Journal Article
%A S. S. Martynov
%T NP-completeness of special string editing problems
%J Matematičeskie voprosy kriptografii
%D 2013
%P 77-93
%V 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MVK_2013_4_a5/
%G ru
%F MVK_2013_4_a5
S. S. Martynov. NP-completeness of special string editing problems. Matematičeskie voprosy kriptografii, Tome 4 (2013), pp. 77-93. http://geodesic.mathdoc.fr/item/MVK_2013_4_a5/