Counting Lyndon factors (Q2401409): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Changed an Item
ReferenceBot (talk | contribs)
Changed an Item
 
Property / cites work
 
Property / cites work: Sturmian and Episturmian Words / rank
 
Normal rank
Property / cites work
 
Property / cites work: Sturmian words, Lyndon words and trees / rank
 
Normal rank
Property / cites work
 
Property / cites work: Descriptions of the Characteristic Sequence of an Irrational / rank
 
Normal rank
Property / cites work
 
Property / cites work: Free differential calculus. IV: The quotient groups of the lower central series / rank
 
Normal rank
Property / cites work
 
Property / cites work: Sturmian words: structure, combinatorics, and their arithmetics / rank
 
Normal rank
Property / cites work
 
Property / cites work: Some combinatorial properties of Sturmian words / rank
 
Normal rank
Property / cites work
 
Property / cites work: Factorizing words over an ordered alphabet / rank
 
Normal rank
Property / cites work
 
Property / cites work: Determination of [nθ] by its Sequence of<sup>*</sup>Differences / rank
 
Normal rank
Property / cites work
 
Property / cites work: On Sturmian and episturmian words, and related topics / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4341774 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4529547 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On Burnside's Problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Lyndon words and Fibonacci numbers / rank
 
Normal rank

Latest revision as of 08:40, 14 July 2024

scientific article
Language Label Description Also known as
English
Counting Lyndon factors
scientific article

    Statements

    Counting Lyndon factors (English)
    0 references
    0 references
    0 references
    0 references
    8 September 2017
    0 references
    Two words \(u\), \(v\) are conjugates if there are words \(x\), \(y\) such that \(u=xy\) and \(v=yx.\) A word is primitive if it cannot be expressed as \(x^{n}\) for a word \(x\) and \(n\geq2\). A Lyndon word is a non-empty primitive word that is the lexicographically least word in its conjugacy class. The paper provides formulas for the following values for an alphabet of size \(\sigma\): \(D\left( \sigma,n\right) \) -- the maximum number of distinct Lyndon factors in a word of length \(n\); \(ET\left( \sigma,n\right) \) -- the expected total number of Lyndon factors (counted according to their multiplicity) in a word of length \(n\); \(ED\left( \sigma,n\right) \) -- the expected number of distinct Lyndon factors in a word of length \(n\). Then the authors provide a generalization of a result of Saari on the number of Lyndon factors of a Fibonacci Lyndon word (a Lyndon factor of the infinite Fibonacci word -- being a particular Sturmian word) by determining the number of Lyndon factors of any Christoffel word (a Lyndon factor of any Sturmian word). They present, as well, a counterexample to a conjecture of Saari that the word in the set of all Lyndon words of the same length different from 6 which contains the least number of Lyndon factors is a Christoffel word.
    0 references
    0 references
    Lyndon word
    0 references
    Christoffel word
    0 references
    Lyndon factor
    0 references

    Identifiers