Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 9 min ago
PreprintCC BY 4.0HAL

String attractors and bi-infinite words

  • Pierre Béaur
  • France Gheeraert
  • Benjamin Hellouin de Menibus
Open at sourcePDFCite

Abstract

String attractors are a combinatorial tool coming from the field of data compression. It is a set of positions within a word which captures an occurrence of every factor. While one-sided infinite words admitting a finite string attractor are eventually periodic, the situation is different for two-sided infinite words. In this article, we characterise the bi-infinite words admitting a finite string attractor as the eventually periodic words, the characteristic Sturmian words and their morphic images. For words that do not admit finite string attractors, we study the structure and properties of their infinite string attractors.

Related

  1. Smallest String Attractors and Minimal Coverage Certificates of Thue--Morse Words
    Simone Faro, Francesco Pio Marino, Arianna Pavone
    arXivPreprintCC BY 4.0Full text1 citedCombinatorics & discrete mathematicsarXiv
  2. Algebraic Magnetism: X-products of attractors via 𝔽1-geometry
    Arnaud Mayeux
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  3. Behavior of the SRB Entropy Functional in Families of Hyperbolic Attractors and Expanding Maps
    Miaohua Jiang
    arXivPreprintCC BY-NC-ND 4.0Full textDynamical systemsarXiv
  4. On the language of palindromic reduced words in a Coxeter group
    Asilata Bapat
    arXivPreprintCC BY-SA 4.0Full textAlgebra & number theoryarXiv
  5. Nonminimizing Attractors of Stochastic Subgradient Methods on Semialgebraic Functions
    Jiajin Li
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{beaur2026string,
  title = {{String attractors and bi-infinite words}},
  author = {Pierre Béaur and France Gheeraert and Benjamin Hellouin de Menibus},
  howpublished = {HAL},
  year = {2026},
  month = nov,
  eprint = {2403.13449},
  archivePrefix = {arXiv},
  url = {https://hal.science/hal-05641031v2},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - String attractors and bi-infinite words
AU  - Pierre Béaur
AU  - France Gheeraert
AU  - Benjamin Hellouin de Menibus
PY  - 2026
DA  - 2026/11/02
PB  - HAL
UR  - https://hal.science/hal-05641031v2
AB  - String attractors are a combinatorial tool coming from the field of data compression. It is a set of positions within a word which captures an occurrence of every factor. While one-sided infinite words admitting a finite string attractor are eventually periodic, the situation is different for two-sided infinite words. In this article, we characterise the bi-infinite words admitting a finite string attractor as the eventually periodic words, the characteristic Sturmian words and their morphic images. For words that do not admit finite string attractors, we study the structure and properties of their infinite string attractors.
ER  -