Questions tagged [lyndon-words]
The lyndon-words tag has no usage guidance.
7 questions
2
votes
1
answer
153
views
The shuffle algebra over the rationals is isomorphic to the polynomial algebra in the Lyndon words
On this wikipedia page is stated that over the rational numbers, the shuffle algebra (over a set $X$) is isomorphic to the polynomial algebra in the Lyndon words (on $X$). I was wondering if you can ...
- 85
2
votes
0
answers
47
views
How can we interpret Groebner basis in a special case?
Let consider a free Lie algebra generated by $X$ with a set of relations $S$ such that the degree of leading monomial of relations in $S$ are greater than or equal to $2$. Let assume that we compute ...
- 367
2
votes
0
answers
577
views
Lyndon basis of free Lie algebras
Let $A = \{a,b,c,d\}$ be a set of totally ordered alphabets, a Lyndon word over $A$ is a word $w$ in $A^*$ such that if $w=uv$ is a factorization of $w$ into non-empty subwords, then $u<v$ in ...
- 1,269
1
vote
1
answer
109
views
Cliques in overlap graphs for words
Let $\Sigma$ be a finite alphabet, and consider the free monoid $\Sigma^*$. Given $w, w' \in \Sigma^*$ we say that $w$ overlaps $w'$ if there exist non-empty words $u, v, u'$ such that $w = uv$ and $w'...
- 435
3
votes
1
answer
505
views
Lyndon words and Hall basis
I am looking for an algorithm to produce Hall basis from Lyndon words. First I will recall the definition of the Hall set following Serre's presentation.
Let $X$ be a finite set and let $M(X)$ be ...
- 697
32
votes
3
answers
2k
views
"Nyldon words": understanding a class of words factorizing the free monoid increasingly
BACKGROUND.
Let me first introduce some classical definitions, which appear, e.g., in §5 of Lothaire's Combinatorics on Words, in §5.1 of Reutenauer's Free Lie algebras, and in §6.1 of Victor Reiner'...
- 33.8k
11
votes
2
answers
696
views
Bracket of lyndon words?
Here is a simple question regarding the standard Lyndon basis for the free Lie Algebra. Suppose I take two lyndon words $m$ and $n$ and their standard bracketings $B(m)$ and $B(n)$ as elements in the ...
- 727