## State Complexity of Neighbourhoods and Approximate Pattern Matching

Loading...

##### Date

2018-02

##### Authors

Ng, Timothy

Rappaport, David

Salomaa, Kai

##### Keyword

Regular Languages , State Complexity , Lower Bounds

##### Abstract

The neighbourhood of a language L with respect to an additive
distance consists of all strings that have distance at
most the given radius from some string of L.
We show that the worst case
deterministic state complexity of a radius r neighbourhood
of a language recognized by an n state nondeterministic
finite automaton A is (r+2)n - 1.
In the case where A is deterministic
we get the same lower bound for the
state complexity of the neighbourhood if we use an
additive quasi-distance. The lower bound constructions
use an alphabet of size linear in n.
We show that the worst case state complexity of the set
of strings that contain a substring within distance $r$ from
a string recognized by A is (r+2){n-2} + 1.