Results 1 to 10 of about 948,909 (194)
Quasiperiodic and Lyndon episturmian words [PDF]
Theoretical Computer Science, 2008 33 pages; minor ...
Gwenael Richomme, Amy Glen
exaly +6 more sources
Lyndon factorization of the Thue-Morse word and its relatives [PDF]
Discrete Mathematics & Theoretical Computer Science, 1997 We compute the Lyndon factorization of the Thue-Morse word. We also compute the Lyndon factorization of two related sequences involving morphisms that give rise to new presentations of these sequences.
Augustin Ido, Guy Melançon
doaj +5 more sources
Theoretical Computer Science, 2020 Let $\A$ be a finite non-empty set and $\preceq $ a total order on $\A^\nats$ verifying the following lexicographic like condition: For each $n\in \nats$ and $u, v\in \A^n,$ if $u^ω\prec v^ω$ then $ux\prec vy$ for all $x, y \in \A^\nats.$ A word $x\in \A^\nats$ is called $ω$-Lyndon if $x\prec y$ for each proper suffix $y$ of $x.$ A finite word $w\in \A^
Luca Q Zamboni
exaly +6 more sources
Inverse Lyndon words and inverse Lyndon factorizations of words [PDF]
Advances in Applied Mathematics, 2018 Motivated by applications to string processing, we introduce variants of the Lyndon factorization called inverse Lyndon factorizations. Their factors, named inverse Lyndon words, are in a class that strictly contains anti-Lyndon words, that is Lyndon words with respect to the inverse lexicographic order. The Lyndon factorization of a nonempty word w is
BONIZZONI, PAOLA +3 more
openaire +6 more sources
Lyndon factorization of generalized words of Thue [PDF]
Discrete Mathematics & Theoretical Computer Science, 2002 The i-th symbol of the well-known infinite word of Thue on the alphabet { 0,1} can be characterized as the parity of the number of occurrences of the digit 1 in the binary notation of i.
Anton Černý
doaj +5 more sources
2D Lyndon Words and Applications [PDF]
Algorithmica, 2015 A Lyndon word is a primitive string which is lexicographically smallest among cyclic permutations of its characters. Lyndon words are used for constructing bases in free Lie algebras, constructing de Bruijn sequences, finding the lexicographically smallest or largest substring in a string, and succinct suffix-prefix matching of highly periodic strings.
Dina Sokol
exaly +4 more sources
Transfinite Lyndon Words [PDF]
Logical Methods in Computer Science, 2015 In this paper, we extend the notion of Lyndon word to transfinite words. We prove two main results. We first show that, given a transfinite word, there exists a unique factorization in Lyndon words that are densely non-increasing, a relaxation of the condition used in the case of finite words.
Luc Boasson, Olivier Carton
openaire +8 more sources
Lyndon words and Fibonacci numbers
Journal of Combinatorial Theory - Series A, 2014 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.
Kalle Saari
exaly +4 more sources
Linear construction of a left Lyndon tree [PDF]
Information and Computation, 2022 We extend the left-to-right Lyndon factorisation of a word to the left Lyndon tree construction of a Lyndon word. It yields an algorithm to sort the prefixes of a Lyndon word according to the infinite ordering defined by Dolce et al. (2019).
Golnaz Badkobeh, Maxime Crochemore
exaly +2 more sources
Theoretical Computer Science, 2020 Abstract Let A be a finite non-empty set and ⪯ a total order on A N verifying the following lexicographic like condition: For each n ∈ N and u , v ∈ A n , if u ω ≺ v ω then u x ≺ v y for all x , y ∈ A N . A word x ∈ A N is called ω-Lyndon if x
Luca Q Zamboni
exaly +5 more sources