On the size of the neighborhoods of a word
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908518203785216 |
|---|---|
| author | Chauve, Cedric Zhang, Louxin |
| author_facet | Chauve, Cedric Zhang, Louxin |
| contents | 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 such as the condensed neighborhood or the super-condensed neighborhood has applications in the design of approximate pattern matching algorithms. It follows that bounds on the maximum size of the neighborhood of words of a given length can be used in the complexity analysis of such approximate pattern matching algorithms. In this note, we present exact formulas for the size of the condensed and super condensed neighborhoods of a unary word, a novel upper bound for the maximum size of the condensed neighborhood of an arbitrary word of a given length, and we prove a conjectured upper bound again for the maximum size of the condensed neighborhood of an arbitrary word of a given length. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_13796 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the size of the neighborhoods of a word Chauve, Cedric Zhang, Louxin Combinatorics Discrete Mathematics 05A05, 05A15, 05A16 G.2.1 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 such as the condensed neighborhood or the super-condensed neighborhood has applications in the design of approximate pattern matching algorithms. It follows that bounds on the maximum size of the neighborhood of words of a given length can be used in the complexity analysis of such approximate pattern matching algorithms. In this note, we present exact formulas for the size of the condensed and super condensed neighborhoods of a unary word, a novel upper bound for the maximum size of the condensed neighborhood of an arbitrary word of a given length, and we prove a conjectured upper bound again for the maximum size of the condensed neighborhood of an arbitrary word of a given length. |
| title | On the size of the neighborhoods of a word |
| topic | Combinatorics Discrete Mathematics 05A05, 05A15, 05A16 G.2.1 |
| url | https://arxiv.org/abs/2505.13796 |