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.

UDC: 519.713

Received: 25.02.2009

 English version: Proceedings of the Steklov Institute of Mathematics (Supplement Issues), 2009, 267, suppl. 1, S201–S209

Bibliographic databases:

• 
•