Effective Computation of Generalized Abelian Complexity for Pisot Type Substitutive Sequences
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913802373562368 |
|---|---|
| author | Couvreur, Jean-Michel Delacourt, Martin Ollinger, Nicolas Popoli, Pierre Shallit, Jeffrey Stipulanti, Manon |
| author_facet | Couvreur, Jean-Michel Delacourt, Martin Ollinger, Nicolas Popoli, Pierre Shallit, Jeffrey Stipulanti, Manon |
| contents | Generalized abelian equivalence compares words by their factors up to a certain bounded length. The associated complexity function counts the equivalence classes for factors of a given size of an infinite sequence. How practical is this notion? When can these equivalence relations and complexity functions be computed efficiently? We study the fixed points of substitution of Pisot type. Each of their $k$-abelian complexities is bounded and the Parikh vectors of their length-$n$ prefixes form synchronized sequences in the associated Dumont--Thomas numeration system. Therefore, the $k$-abelian complexity of Pisot substitution fixed points is automatic in the same numeration system. Two effective generic construction approaches are investigated using the \texttt{Walnut} theorem prover and are applied to several examples. We obtain new properties of the Tribonacci sequence, such as a uniform bound for its factor balancedness together with a two-dimensional linear representation of its generalized abelian complexity functions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_13584 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Effective Computation of Generalized Abelian Complexity for Pisot Type Substitutive Sequences Couvreur, Jean-Michel Delacourt, Martin Ollinger, Nicolas Popoli, Pierre Shallit, Jeffrey Stipulanti, Manon Formal Languages and Automata Theory Discrete Mathematics Combinatorics 11B85, 68R15, 68Q45 Generalized abelian equivalence compares words by their factors up to a certain bounded length. The associated complexity function counts the equivalence classes for factors of a given size of an infinite sequence. How practical is this notion? When can these equivalence relations and complexity functions be computed efficiently? We study the fixed points of substitution of Pisot type. Each of their $k$-abelian complexities is bounded and the Parikh vectors of their length-$n$ prefixes form synchronized sequences in the associated Dumont--Thomas numeration system. Therefore, the $k$-abelian complexity of Pisot substitution fixed points is automatic in the same numeration system. Two effective generic construction approaches are investigated using the \texttt{Walnut} theorem prover and are applied to several examples. We obtain new properties of the Tribonacci sequence, such as a uniform bound for its factor balancedness together with a two-dimensional linear representation of its generalized abelian complexity functions. |
| title | Effective Computation of Generalized Abelian Complexity for Pisot Type Substitutive Sequences |
| topic | Formal Languages and Automata Theory Discrete Mathematics Combinatorics 11B85, 68R15, 68Q45 |
| url | https://arxiv.org/abs/2504.13584 |