Lyndon Word

A word l 𝑙 l is a Lyndon Word if any of the following equivalent conditions are met:

  1. l 𝑙 l is lexicographically smaller than all of its non-identity rotations.
  2. ∀ u , v : A + , l = u ⁢ v → l < v ⁢ u : for-all 𝑢 𝑣 superscript 𝐴 𝑙 𝑢 𝑣 → 𝑙 𝑣 𝑢 \forall~u,v:A^{+},\,l=uv\to l<vu
  3. ∀ u , v : A + , l = u ⁢ v → l < v : for-all 𝑢 𝑣 superscript 𝐴 𝑙 𝑢 𝑣 → 𝑙 𝑣 \forall\,u,v:A^{+},\,l=uv\to l<v (IE: l 𝑙 l is strictly smaller than any proper suffix)
  4. ∀ k : [ length ⁢ ( l ) ] , prefix ⁢ ( l , k ) < suffix ⁢ ( l , k ) : for-all 𝑘 delimited-[] length 𝑙 prefix 𝑙 𝑘 suffix 𝑙 𝑘 \forall\,k:\left[\;\mathrm{length}(l)\;\right],\,\mathrm{prefix}(l,k)<\mathrm{% suffix}(l,k)
  5. l = [ a ] ∨ ( l = u ⁢ v ∧ L ⁢ ( u ) ∧ L ⁢ ( v ) ∧ u < v ) 𝑙 delimited-[] 𝑎 𝑙 𝑢 𝑣 𝐿 𝑢 𝐿 𝑣 𝑢 𝑣 l=[a]\lor(l=uv\land L(u)\land L(v)\land u<v)

Notes

It seems like all of these definitions are overly strict, and could cause annoying problems. Note that Duval's algorithm needs us to have a decidable strict order.