State Complexity of Neighbourhoods and Approximate Pattern Matching
Loading...
Authors
Ng, Timothy
Rappaport, David
Salomaa, Kai
Date
2018-02
Type
journal article
Language
en
Keyword
Regular Languages , State Complexity , Lower Bounds
Alternative Title
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.
Description
Citation
Timothy Ng, David Rappaport, and Kai Salomaa, Int. J. Found. Comput. Sci. 29, 315 (2018).
Publisher
World Scientific