A characterization of balanced episturmian sequences

MaRDI QIDQ2372877zbMATH OpenFDO

Authors Geneviève Paquin, L. Vuillon

Publication date 16 July 2007

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0611576, https://eudml.org/doc/128028, http://www.emis.de/journals/EJC/Volume_14/Abstracts/v14i1r33.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Sturmian sequences

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: It is well known that Sturmian sequences are the aperiodic sequences that are balanced over a 2-letter alphabet. They are also characterized by their complexity: they have exactly $(n+1)$ factors of length $n$. One possible generalization of Sturmian sequences is the set of infinite sequences over a $k$-letter alphabet, $kgeq3$, which are closed under reversal and have at most one right special factor for each length. This is the set of episturmian sequences. These are not necessarily balanced over a $k$-letter alphabet, nor are they necessarily aperiodic. In this paper, we characterize balanced episturmian sequences, periodic or not, and prove Fraenkel's conjecture for the class of episturmian sequences. This conjecture was first introduced in number theory and has remained unsolved for more than 30 years. It states that for a fixed $k>2$, there is only one way to cover $$ by $k$ Beatty sequences. The problem can be translated to combinatorics on words: for a $k$-letter alphabet, there exists only one balanced sequence up to letter permutation that has different letter frequencies.

Review text

Summary: It is well-known that Sturmian sequences are the non ultimately periodic sequences that are balanced over a 2-letter alphabet. They are also characterized by their complexity: they have exactly \((n+1)\) distinct factors of length \(n\). A natural generalization of Sturmian sequences is the set of infinite episturmian sequences. These sequences are not necessarily balanced over a \(k\)-letter alphabet, nor are they necessarily aperiodic. In this paper, we characterize balanced episturmian sequences, periodic or not, and prove Fraenkel's conjecture for the special case of episturmian sequences. It appears that balanced episturmian sequences are all ultimately periodic and they can be classified in 3 families.

Recommendations

• On generalized balancing sequences
• On a Class of 2-Balanced Sequences
• On balanced sequences and their critical exponent
• On characterization of some sequences
• On balanced sequences and their asymptotic critical exponent
• Asymptotic repetitive threshold of balanced sequences
• A new sufficient condition for log-balancedness of sequences
• On minimal critical exponent of balanced sequences
• The log-balancedness for a class of sequences.
• scientific article; zbMATH DE number 4134339

Cited in

(15)

• Palindromic richness
• Quasiperiodic and Lyndon episturmian words
• On the structure of bispecial Sturmian words
• Sturmian and Episturmian Words
• On the Ehrenfeucht-Mycielski balance conjecture
• Directive words of episturmian words: equivalences and normalization
• Balanced Words Having Simple Burrows-Wheeler Transform
• scientific article; zbMATH DE number 1528686 (Why is no real title available?)
• Construction of Sturmian sequences
• Second Order Balance Property on Christoffel Words
• Episturmian words: a survey
• Extremal properties of (epi)Sturmian sequences and distribution modulo 1
• Balancing and clustering of words in the Burrows-Wheeler transform
• A geometric point of view on the synchronization of three Christoffel words
• On a generalization of Christoffel words: epichristoffel words

This page was built for publication: A characterization of balanced episturmian sequences

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