Geodesic
Regularity of a dynamic neighborhood of a regular language
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 15 (2009) no. 2, pp. 194-202
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

The operation of taking a dynamic neighborhood of a language is studied. It is proved that this operation preserves the regularity of the language. The increase in the complexity of the language under the passage to its dynamic neighborhood is estimated.
Keywords: regular language, finite transducer, Hamming distance, neighborhood of a language, nondeterministic complexity. 
@article{TIMM_2009_15_2_a17,
     author = {G. A. Povarov},
     title = {Regularity of a~dynamic neighborhood of a~regular language},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {194--202},
     year = {2009},
     volume = {15},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2009_15_2_a17/}
}
TY  - JOUR
AU  - G. A. Povarov
TI  - Regularity of a dynamic neighborhood of a regular language
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2009
SP  - 194
EP  - 202
VL  - 15
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMM_2009_15_2_a17/
LA  - ru
ID  - TIMM_2009_15_2_a17
ER  - 
%0 Journal Article
%A G. A. Povarov
%T Regularity of a dynamic neighborhood of a regular language
%J Trudy Instituta matematiki i mehaniki
%D 2009
%P 194-202
%V 15
%N 2
%U http://geodesic.mathdoc.fr/item/TIMM_2009_15_2_a17/
%G ru
%F TIMM_2009_15_2_a17
G. A. Povarov. Regularity of a dynamic neighborhood of a regular language. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 15 (2009) no. 2, pp. 194-202. http://geodesic.mathdoc.fr/item/TIMM_2009_15_2_a17/

[1] Kudryavtsev V. B., Aleshin S. V., Podkolzin A. S., Vvedenie v teoriyu avtomatov, Nauka, M., 1985, 320 pp. | MR

[2] Levenshtein V. I., “Dvoichnye kody s ispravleniem vypadenii, vstavok i zameschenii simvolov”, Dokl. AN SSSR, 163:4 (1965), 846–848, M.

[3] Chashkin A. V., Lektsii po diskretnoi matematike, MGU, M., 2007, 261 pp.

[4] R. Baeza-Yates, B. Ribeiro (eds.), Modern information retrieval, Addison-Wesley, Boston, 1999, 513 pp.

[5] Calude C., Salomaa K., Yu S., Metric lexical analysis, Lecture Notes in Computer Science, 2214, Springer, Berlin, 2001, 48–59 | MR | Zbl

[6] Epifanio C., Gabriele A., Mignosi F., Restivo A., Sciortino M., “Languages with mismatches”, Theoret. Comp. Science, 385:1–3 (2007), 152–166 | DOI | MR | Zbl

[7] Hopcroft J. E., Motwani R., Ullman J. D., Introduction to automata theory, languages, and computation, Addison-Wesley, Boston, 2001, 521 pp. | MR | Zbl

[8] Kukich K., “Techniques for automatically correcting words in text”, ACM Computing Surveys, 24:4 (1992), 377–439 | DOI

[9] Myers E., “Algorithmic Advances for Searching Biosequence Databases”, Computational methods in genome research, ed. S. Suhai, Plenum Press, New York, 1994, 121–125

[10] Navarro G., “A Guided tour to approximate string matching”, ACM Computing Surveys, 33 (2001), 31–88 | DOI

[11] Sakarovitch J., Éléments de théorie des automates, Vuibert, Paris, 2003, 816 pp.

[12] Ukkonen E., “Finding approximate patterns in strings”, J. Alg., 6 (1985), 132–137 | DOI | MR | Zbl

[13] Waterman M., Introduction to computational biology, Chapman and Hall, London, 1995, 431 pp. | Zbl

[14] Wu S., Manber U., “Fast text searching allowing errors”, Communicaions of the ACM, 35:10 (1992), 83–91 | DOI

[15] Yu S., “Regular languages”, Handbook of formal languages, Vol. 1, eds. G. Rozenberg, A. Salomaa, Springer, New York, 1997, 41–110 | MR | Zbl