Checking and producing word attractors
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_ | 1866918138757513216 |
|---|---|
| author | Béal, Marie-Pierre Crochemore, Maxime Romana, Giuseppe |
| author_facet | Béal, Marie-Pierre Crochemore, Maxime Romana, Giuseppe |
| contents | The article focuses on word (or string) attractors, which are sets of positions related to the text compression efficiency of the underlying word. The article presents two combinatorial algorithms based on Suffix automata or Directed Acyclic Word Graphs. The first algorithm decides in linear time whether a set of positions on the word is an attractor of the word. The second algorithm generates an attractor for a given word in a greedy manner. Although this problem is NP-hard, the algorithm is efficient and produces very small attractors for several well-known families of words. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_08503 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Checking and producing word attractors Béal, Marie-Pierre Crochemore, Maxime Romana, Giuseppe Data Structures and Algorithms Formal Languages and Automata Theory 68W32 The article focuses on word (or string) attractors, which are sets of positions related to the text compression efficiency of the underlying word. The article presents two combinatorial algorithms based on Suffix automata or Directed Acyclic Word Graphs. The first algorithm decides in linear time whether a set of positions on the word is an attractor of the word. The second algorithm generates an attractor for a given word in a greedy manner. Although this problem is NP-hard, the algorithm is efficient and produces very small attractors for several well-known families of words. |
| title | Checking and producing word attractors |
| topic | Data Structures and Algorithms Formal Languages and Automata Theory 68W32 |
| url | https://arxiv.org/abs/2509.08503 |