Lyndon words and Fibonacci numbers
From MaRDI portal
Publication:392802
DOI10.1016/J.JCTA.2013.09.002zbMATH Open1282.68188arXiv1207.4233OpenAlexW1976554601WikidataQ114162735 ScholiaQ114162735MaRDI QIDQ392802FDOQ392802
Publication date: 15 January 2014
Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)
Abstract: It is a fundamental property of non-letter Lyndon words that they can be expressed as a concatenation of two shorter Lyndon words. This leads to a naive lower bound log_{2}(n)} + 1 for the number of distinct Lyndon factors that a Lyndon word of length n must have, but this bound is not optimal. In this paper we show that a much more accurate lower bound is log_{phi}(n) + 1, where phi denotes the golden ratio (1 + sqrt{5})/2. We show that this bound is optimal in that it is attained by the Fibonacci Lyndon words. We then introduce a mapping L_x that counts the number of Lyndon factors of length at most n in an infinite word x. We show that a recurrent infinite word x is aperiodic if and only if L_x >= L_f, where f is the Fibonacci infinite word, with equality if and only if f is in the shift orbit closure of f.
Full work available at URL: https://arxiv.org/abs/1207.4233
Cites Work
- Necklaces of beads in k colors and k-ary de Bruijn sequences
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Sturmian words, Lyndon words and trees
- Factorizing words over an ordered alphabet
- Automatic Sequences
- Periodicity and the golden ratio
- Free differential calculus. IV: The quotient groups of the lower central series
- Least Periods of Factors of Infinite Words
- Uniqueness Theorems for Periodic Functions
- Title not available (Why is that?)
- Squares, cubes, and time-space efficient string searching
- A combinatorial property of the Fibonacci words
- Free Lie algebras and free monoids. Bases of free Lie algebras and factorizations of free monoids
- Fine and Wilf's theorem for three periods and a generalization of Sturmian words
- Infinite Lyndon words
- Monomial algebras defined by Lyndon words.
- Fine and Wilf words for any periods. II
- On extremal properties of the Fibonacci word
- Primitive Words and Lyndon Words in Automatic and Linearly Recurrent Sequences
- UNAVOIDABLE SETS OF CONSTANT LENGTH
- Some properties of the singular words of the Fibonacci word
- Periodicity and unbordered segments of words
- Weinbaum factorizations of primitive words
- Palindromic prefixes and episturmian words
Cited In (11)
- Abelian periods of factors of Sturmian words
- ENUMERATING NECKLACES WITH TRANSITIONS
- Decision algorithms for Fibonacci-automatic Words, I: Basic results
- Some properties of the Fibonacci sequence on an infinite alphabet
- Monomial algebras defined by Lyndon words.
- On generating binary words palindromically
- Studies on finite Sturmian words
- Counting Lyndon factors
- Abelian bordered factors and periodicity
- The sequence of return words of the Fibonacci sequence
- More properties of the Fibonacci word on an infinite alphabet
This page was built for publication: Lyndon words and Fibonacci numbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q392802)
