String attractors and infinite words

DOI10.1007/978-3-031-20624-5_26arXiv2206.00376OpenAlexW4312527278MaRDI QIDQ6109022

Marinella Sciortino, Antonio Restivo, Giuseppe Romana

Publication date: 26 July 2023

Published in: LATIN 2022: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2206.00376

zbMATH Keywords

Sturmian wordmorphismfactor complexityrecurrent wordstring attractorrepetitiveness measure

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx)

Related Items (2)

String Attractors of Fixed Points of k-Bonacci-Like Morphisms ⋮ String attractors of episturmian sequences

Cites Work

• Unnamed Item
• Languages under substitutions and balanced words
• Circular Sturmian words and Hopcroft's algorithm
• Burrows-Wheeler transform and Sturmian words
• Toeplitz words, generalized periodicity and periodically iterated morphisms
• On extremal cases of Hopcroft's algorithm
• Towards a definitive measure of repetitiveness
• Logarithmic equal-letter runs for BWT of purely morphic words
• A combinatorial view on string attractors
• Substitution dynamical systems: characterization of linear repetitivity and applications
• Complexité des facteurs des mots infinis engendrés par morphismes itérés
• The Lempel–Ziv Complexity of Fixed Points of Morphisms
• Hopcroft’s Algorithm and Cyclic Automata
• On the Complexity of Finite Sequences
• Fast Pattern Matching in Strings
• Automatic Sequences
• Dimension Groups and Dynamical Systems
• Optimal-Time Dictionary-Compressed Indexes
• At the roots of dictionary compression: string attractors
• Suffix Automata and Standard Sturmian Words

This page was built for publication: String attractors and infinite words