On the size of the neighborhoods of a word

Cedric Chauve, Louxin Zhang

The d-neighborhood of a word W in the Levenshtein distance is the set of all words at distance at most d from W. Generating the neighborhood of a word W, or related sets of words s…