Lyndon word
String that is strictly smaller in lexicographic order than all of its rotations
Facts
6 properties- Instance of
- mathematical concept
- Subclass of
- Hall word
- Defining formula
- w=w_0w_2\dotsm w_{k-1}<\min\{w_1w_2\dotsm w_{k-1}w_0,w_2\dotsm w_{k-1}w_0w_1,\dotsc,w_{k-1}w_0\dotsm w_{k-2}\} \in \Sigma^k
- Discoverer or inventor
- Anatoly Shirshov
- Named after
- Roger Lyndon
- Time of discovery or invention
- 1953
🏷️ Also known as
en standard lexicographic sequence
en Lyndon word
en regular word
de Lyndonwort
fr mot de Lyndon
fr Mots de Lyndon
ja リンドンワード
pl słowa Lyndona
pl słowa pierwsze
pl słowo Lyndona
pl słowo pierwsze
pt palavra de Lyndon
ru Слово Линдона
sv Lyndonord
🔖 Identifiers · 3
- Freebase ID
- /m/0b6sdd
- MathWorld ID
- LyndonWord
- Microsoft Academic ID (discontinued)
- 6178322
🔗 Connections
Created notable works 1
Maintained by WikiProject 1
Named after 1
Press Enter · cited answer in seconds
0 sources
Summary
Lyndon word is a mathematical concept[1].
Key Facts
- Discoverer or inventor: Anatoly Shirshov[2]
- Named after: Roger Lyndon[3]
- Subclass of: Hall word[4]
- Time of discovery or invention: 1953[5]
- Lyndon word's defining formula is recorded as w=w_0w_2\dotsm w_{k-1}<\min{w_1w_2\dotsm w_{k-1}w_0,w_2\dotsm w_{k-1}w_0w_1,\dotsc,w_{k-1}w_0\dotsm w_{k-2}} \in \Sigma^k<sup id="cite-C16" class="cite-ref" title="Lyndon word — defining formula (P2534): w=w_0w_2\dotsm w_{k-1}<\min{w_1w_2\dotsm w_{k-1}w_0,w_2\dotsm w_{k-1}w_0w_1,\dotsc,w_{k-1}w_0\dotsm w_{k-2}} \in \Sigma^k">[?].
- Maintained by WikiProject: WikiProject Mathematics[6]