New string attractor-based complexities for infinite words

DOI10.1016/J.JCTA.2024.105936MaRDI QIDQ6612124zbMATH OpenFDO

Authors Julien Cassaigne, France Gheeraert, Antonio Restivo, Giuseppe Romana, M. Sciortino, Manon Stipulanti

Publication date 30 September 2024

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCTA.2024.105936

zbMATH Keywords

\(k\)-Bonacci wordfactor complexityrecurrence functionrepetitiveness measurestring attractorSturmian word

Mathematics Subject Classification ID

Theory of data (68Pxx) Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx)

Cites work

• A combinatorial view on string attractors
• At the roots of dictionary compression: string attractors
• Automatic Sequences
• Burrows-Wheeler transform and Sturmian words
• Circular Sturmian words and Hopcroft's algorithm
• Comparison of LZ77-type parsings
• Complexity and special factors
• Complexité des facteurs des mots infinis engendrés par morphismes itérés
• Decidability of periodicity for infinite words
• Decidable problems in substitution shifts
• Dimension groups and dynamical systems. Substitutions, Bratteli diagrams and Cantor systems
• Episturmian words and some constructions of de Luca and Rauzy
• Factor complexity
• Fast Pattern Matching in Strings
• Hopcroft’s Algorithm and Cyclic Automata
• scientific article; zbMATH DE number 1688349 (Why is no real title available?)
• scientific article; zbMATH DE number 3991618 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• Languages under substitutions and balanced words
• Linearly recurrent subshifts have a finite number of non-periodic subshift factors
• Logarithmic equal-letter runs for BWT of purely morphic words
• On extending de Bruijn sequences
• On Repetitiveness Measures of Thue-Morse Words
• On the Complexity of Finite Sequences
• Palindromic complexity of infinite words associated with simple Parry numbers
• Prefix palindromic length of the Sierpinski word
• Some combinatorial properties of Sturmian words
• String attractors and infinite words
• String Attractors for Factors of the Thue-Morse Word
• String attractors of episturmian sequences
• String Attractors of Fixed Points of k-Bonacci-Like Morphisms
• Substitutional dynamical systems, Bratteli diagrams and dimension groups
• Suffix Automata and Standard Sturmian Words
• Symbolic dynamics.
• The Lempel–Ziv Complexity of Fixed Points of Morphisms
• Toward a Definitive Compressibility Measure for Repetitive Sequences
• Words with unbounded periodicity complexity

Cited in

(4)

• String attractors of some simple-parry automatic sequences
• Opacity complexity of automatic sequences: the general case
• The reflection complexity of sequences over finite alphabets
• Morphisms and BWT-run sensitivity

This page was built for publication: New string attractor-based complexities for infinite words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6612124)