Characteristic Sturmian words are extremal for the critical factorization theorem

DOI10.1016/J.TCS.2012.03.012zbMATH Open1263.68122OpenAlexW2083294913MaRDI QIDQ714825FDOQ714825

Authors: Filippo Mignosi, Antonio Restivo 

Publication date: 11 October 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.03.012

Recommendations

• Special factors, periodicity, and an application to Sturmian words
• Sturmian words and words with a critical exponent
• Density of Critical Factorizations
• Some combinatorial properties of Sturmian words
• Critical factorisation in square-free words

zbMATH Keywords

combinatorics on wordsperiodicitySturmian wordscritical factorization theorem

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cites Work

• Two-way string-matching
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sturmian and Episturmian Words
• Title not available (Why is that?)
• Fast Pattern Matching in Strings
• Simple real-time constant-space string matching
• Title not available (Why is that?)
• Uniqueness Theorems for Periodic Functions
• The smallest automaton recognizing the subwords of a text
• Some combinatorial properties of Sturmian words
• Rotations of Periodic Strings and Short Superstrings
• Sequences with minimal block growth
• Saving comparisons in the Crochemore-Perrin string-matching algorithm
• Sturmian graphs and integer representations over numeration systems
• On Sturmian graphs
• Burrows-Wheeler transform and Sturmian words
• Circular Sturmian words and Hopcroft's algorithm
• Title not available (Why is that?)
• Suffix Automata and Standard Sturmian Words
• Periodes et repetitions des mots du monoide libre
• Density of Critical Factorizations
• Recurrence and periodicity in infinite words from local periods
• Hopcroft's automaton minimization algorithm and Sturmian words

Cited In (7)

• An extension of Christoffel duality to a subset of Sturm numbers and their characteristic words
• How to prove that a sequence is not automatic
• Sequences of words defined by two-way transducers
• Abelian repetitions in Sturmian words
• Critical factorisation in square-free words
• Standard Sturmian words and automata minimization algorithms
• A new complexity function for words based on periodicity

This page was built for publication: Characteristic Sturmian words are extremal for the critical factorization theorem

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