# Questions tagged [lyndon-words]

The lyndon-words tag has no usage guidance.

5
questions

**2**

votes

**0**answers

127 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**

vote

**1**answer

85 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'...

**3**

votes

**1**answer

235 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 ...

**31**

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'...

**11**

votes

**2**answers

540 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 ...