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/

[1] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982. | MR

[2] Wagner R. A., “Correcting regular and counter-recognizable languages”, Proc. 8th Hawaii Intern. Conf. Syst. Sci., Honolulu, Hawaii, 1975, 16–18 | MR | Zbl

[3] Martynov S. S., “O slozhnosti nekotorykh zadach redaktirovaniya slov”, Diskretnaya matematika, 1:4 (1989), 104–112 | MR | Zbl

[4] Martynov S. S., “Slozhnost zadachi o dline naibolshei podposledovatelnosti dvoichnogo slova, udovletvoryayuschei zadannomu ogranicheniyu”, Obozr. prikl. i prom. matem., 18:2 (2011), 302

[5] Martynov S. S., “O metode postroeniya svodimostei zadachi VYPOLNIMOST k zadacham redaktirovaniya slov”, Obozr. prikl. i prom. matem., 11:2 (2004), 372–373

[6] Martynov S. S., “Slozhnost zadach o podstrochnom perevode”, Obozr. prikl. i prom. matem., 19:3 (2012), 455–456

[7] Stiffler Dzh. Dzh., Teoriya sinkhronnoi svyazi, Per. s angl. B. S. Tsybakova, ed. E. M. Gabidullin, Svyaz, M., 1975

[8] Glukhov M. M., Shishkov A. B., Matematicheskaya logika. Diskretnye funktsii. Teoriya algoritmov, Uchebnoe posobie, Lan, SPb., 2012, 416 pp.

[9] D. Sankoff, J. B. Kruskal (eds.), Time warps, string edits and macromolecules: the theory and practice of sequence comparison, London, 1983 | MR

[10] Gasfild Den., Stroki, derevya i posledovatelnosti v algoritmakh. Informatika i vychislitelnaya biologiya, Per. s angl. I. V. Romanovskogo, Nevskii dialekt, BKhV-Peterburg, SPb., 2003, 654 pp.

[11] Popov V. V., Genomika s molekulyarno-geneticheskimi osnovami, Knizhnyi dom “Librokom”, M., 2009, 304 pp.