|
Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2009, Volume 15, Number 2, Pages 194–202
(Mi timm235)
|
|
|
|
Regularity of a dynamic neighborhood of a regular language
G. A. Povarov Ural State University
Abstract:
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.
Received: 25.02.2009
Citation:
G. A. Povarov, “Regularity of a dynamic neighborhood of a regular language”, Trudy Inst. Mat. i Mekh. UrO RAN, 15, no. 2, 2009, 194–202; Proc. Steklov Inst. Math. (Suppl.), 267, suppl. 1 (2009), S201–S209
Linking options:
https://www.mathnet.ru/eng/timm235 https://www.mathnet.ru/eng/timm/v15/i2/p194
|
Statistics & downloads: |
Abstract page: | 264 | Full-text PDF : | 76 | References: | 55 | First page: | 3 |
|