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

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

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},
     publisher = {mathdoc},
     volume = {15},
     number = {2},
     year = {2009},
     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
PB  - mathdoc
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
%I mathdoc
%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/