リンドンの言葉

数学のうち組合せ論とコンピュータサイエンスの分野において、リンドン語は、辞書式順序でそのすべての回転よりも厳密に小さい空でない文字列です。リンドン語は、1954年に研究し、標準辞書式シーケンスと呼んだ数学者ロジャー・リンドンにちなんで名付けられました。^[1]アナトリー・シルショフは1953年にリンドン語を通常の単語と呼んで導入しました。^{[2]リンドン語は}ホール語 の特殊なケースであり、リンドン語のほぼすべての特性がホール語と共有されています。

同等の定義は複数存在します。

長さ の -ary Lyndon word は、サイズのアルファベット上の- 文字列であり、そのすべての回転の多重集合における辞書式順序の唯一の最小要素です。唯一最小の回転であるということは、Lyndon word がその非自明な回転のいずれとも異なり、したがって非周期的であることを意味します。^[3]${\displaystyle k}$${\displaystyle n>0}$${\displaystyle n}$${\displaystyle k}$

あるいは、単語が Lyndon 単語となるのは、その単語が空でなく、辞書式にその単語の適切な接尾辞のいずれよりも厳密に小さい場合、つまり、 およびが空でないすべての空でない単語の場合です。 ${\displaystyle w}$${\displaystyle w<v}$${\displaystyle v}$${\displaystyle w=uv}$${\displaystyle u}$

もう1つの特徴付けは次の通りである。リンドン語は空でないという性質を持ち、2つの空でない部分文字列に分割されるときはいつでも、左側の部分文字列は常に右側の部分文字列よりも辞書式に小さくなる。つまり、がリンドン語で、が2つの部分文字列への因数分解で、およびが空でないと理解される場合、となる。この定義は、長さの文字列がリンドン語である場合、かつとなるリンドン語およびが存在する場合に限ります。^[4]この性質を持つおよびの選択肢は複数ある場合がありますが、が可能な限り長くなる標準因数分解と呼ばれる特定の選択肢があります。 ^[5]${\displaystyle w}$${\displaystyle w=uv}$${\displaystyle u}$${\displaystyle v}$${\displaystyle u<v}$${\displaystyle w}$${\displaystyle \geq 2}$${\displaystyle u}$${\displaystyle v}$${\displaystyle u<v}$${\displaystyle w=uv}$${\displaystyle u}$${\displaystyle v}$${\displaystyle v}$

2つの記号からなる2進アルファベット{0,1}上のリンドン語は、長さによってソートされ、各長さクラス内で辞書式に並べられ、無限のシーケンスを形成します。

0、1、01、001、011、0001、0011、0111、00001、00011、00101、00111、01011、01111、...

このシーケンスに属さない最初の文字列「00」は周期的であるため省略されます (部分文字列「0」の 2 回の繰り返しで構成されます)。省略された 2 番目の文字列「10」は非周期的ですが、小さい文字列「01」に周期的に置換できるため、置換クラスでは最小ではありません。

空文字列は長さ0のリンドンワードの定義も満たす。長さ0から始まる各長さの2進リンドンワードの数は、整数列を形成する。

1、2、1、2、3、6、9、18、30、56、99、186、335、...（OEISのシーケンスA001037）

リンドン語は非周期的なネックレス類代表に対応しており、モローのネックレスカウント関数でカウントできる。^{[3] [6]}

Duval (1988) は、指定されたアルファベット サイズで最大長さの Lyndon 単語を辞書式順序でリストする効率的なアルゴリズムを提供しています。 がシーケンス内の単語の 1 つである場合、次の単語は次の手順で見つけることができます。 ${\displaystyle n}$${\displaystyle s}$${\displaystyle w}$${\displaystyle w}$

1. これを繰り返し、ちょうど の長さの新しい単語に切り捨てます。${\displaystyle w}$${\displaystyle x}$${\displaystyle n}$
2. の最後の記号がアルファベットのソート順の最後の記号である限り、それを削除して、より短い単語を生成します。${\displaystyle x}$
3. 最後に残った記号を、アルファベットのソート順でその後続の記号に置き換えます。${\displaystyle x}$

たとえば、長さが 7 までのバイナリ Lyndon ワードを生成し、 まで生成した場合、手順は次のようになります。 ${\displaystyle w=00111}$

1. 繰り返して切り捨てると${\displaystyle x=00111\;00{\cancel {111}}}$
2. 最後の記号は 0 なので、最後の記号ではありません。
3. 最後のシンボルを増分して を取得します。${\displaystyle x=00111\;01}$

この手順で単語の次の単語を生成するのに最悪かかる時間は です。しかし、生成される単語が長さ の配列に格納され、からの の構築が の新しいコピーを作成するのではなくの末尾に記号を追加することによって実行される場合、 の後続単語を生成するのにかかる平均時間は(各単語が等しくあり得ると仮定して) 一定です。したがって、最大で長さ のすべての Lyndon 単語のシーケンスは、シーケンスの長さに比例する時間で生成できます。^[7]このシーケンス内の単語の一定割合がちょうど の長さであるため、同じ手順を使用して、これらの基準に一致しない生成された単語を除外することで、 ちょうど の長さの単語や で割り切れる長さの単語を効率的に生成できます。${\displaystyle w}$${\displaystyle O(n)}$${\displaystyle n}$${\displaystyle x}$${\displaystyle w}$${\displaystyle w}$${\displaystyle w}$${\displaystyle w}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$

チェン・フォックス・リンドン定理によれば、すべての文字列は、リンドン語のシーケンスを連結することによって一意に形成され、シーケンス内の単語は辞書式に非増加になります。^[8]このシーケンスの最後のリンドン語は、指定された文字列の辞書式最小の接尾辞です。^[9]リンドン語の非増加シーケンスへの因数分解（いわゆるリンドン因数分解）は、線形時間で構築できます。^{[9]リンドン因数分解は、}データ圧縮のためのバロウズ・ウィーラー変換の全単射バリアントの一部として使用できます。^{[10]また、}デジタル幾何学のアルゴリズムにも使用できます。^[11]

このような因数分解は、葉にアルファベットのラベルが付けられ、右方向の各枝がシーケンスの最後の Lyndon 語で指定された有限二分木として (一意に) 記述できます。^{[12]このような木は、}標準括弧 と呼ばれることもあり、自由群の要素の因数分解、または自由リー代数の基底要素として考えることができます。これらの木はホール木の特殊なケースであり(Lyndon 語はホール語の特殊なケースである)、同様に、ホール語は、群の交換子収集プロセスと呼ばれる標準的な順序と、リー代数の基底を提供します。^{[13]実際、これらは、}普遍包絡代数の構成に必要な、ポアンカレ-バーコフ-ウィットの定理 に現れる交換子の明示的な構成を提供します。

リンドンの単語はすべて順列、つまり接尾辞の標準順列として理解できます。

Duval (1983) は、線形時間と定数空間で実行される標準因数分解を見つけるためのアルゴリズムを開発しました。このアルゴリズムは、文字列を反復処理して、できるだけ長い Lyndon ワードを見つけようとします。このワードが見つかると、結果リストに追加し、文字列の残りの部分の検索に進みます。結果の文字列リストは、指定された文字列の標準因数分解です。アルゴリズムのより正式な説明は次のとおりです。

長さNの文字列Sが与えられた場合、次の手順に進みます。

1. すでに収集されたシンボルに追加するシンボル候補のインデックスをmとします。最初は、 m = 1 (文字列内のシンボルのインデックスは 0 から始まります)。
2. k を他のシンボルと比較するシンボルのインデックスとします。最初は、 k = 0 です。
3. kとmがNより小さい間、S [ k ] (文字列Sのk番目のシンボル) とS [ m ] を比較します。結果は 3 つ考えられます。
   1. S [ k ] はS [ m ]に等しい:現在収集されているシンボルにS [ m ] を追加します。kとm を増分します。
   2. S [ k ] はS [ m ]より小さい:現在収集されているシンボルにS [ m ] を追加すると、Lyndon ワードが得られます。ただし、これはより大きな Lyndon ワードの一部である可能性があるため、結果リストにはまだ追加できません。したがって、 m を増分してk を0 に設定し、次のシンボルが文字列の最初のシンボルと比較されるようにします。
   3. S [ k ] はS [ m ]より大きい:現在収集されているシンボルにS [ m ] を追加しても、それは Lyndon ワードでも、その始まりでもありません。したがって、最初のm − k 個の収集されたシンボルを結果リストに追加し、文字列から削除し、mを 1 に、kを0 に設定して、それぞれ文字列の 2 番目と最初のシンボルを指すようにします。
4. m > Nの場合、本質的にはマイナス無限大に遭遇するのと同じなので、最初に収集されたm − k 個のシンボルを文字列から削除した後、結果リストに追加し、 mを 1 に、k を0 に設定して、前の手順に戻ります。
5. 結果リストにSを追加します。

長さが与えられた数n を割り切るすべての Lyndon 語を辞書式順序で連結すると、その結果はde Bruijn シーケンス、つまり、長さn の各シーケンスが連続する部分シーケンスの 1 つとして 1 回だけ出現する、循環的なシンボル シーケンスになります。たとえば、長さが 4 を割り切る 2 進 Lyndon 語の連結は、

0 0001 0011 01 0111 1

この構成は、リンドン語の効率的な生成と相まって、線形時間と対数空間で特定のデ・ブリュイン列を構築するための効率的な方法を提供します。^[14]

リンドン語は、与えられた次数の同次部分の基底を構成する際に、自由リー代数の記述に応用される。これがリンドンがこれらの語を導入した当初の動機であった。 ^{[4]リンドン語は}ホール集合の特殊なケースとして理解することができる。^[4]

素数pに対して、体上の次数dの既約な単項多項式の数は、 p個の記号のアルファベット中の長さdのリンドン語の数と同じであり、それらは明示的に対応づけることができる。^[15]${\displaystyle \mathbb {F} _{p}}$

ラドフォードの定理によれば、標数 0 の体上のシャッフル代数は、リンドン語上の多項式代数として見ることができる。より正確には、Aをアルファベット、kを標数 0 の体（または、より一般的には、可換 ℚ-代数）、R を自由非可換k代数k ⟨ x _a | a ∈ A ⟩とする。 A上の語は、 Rの「非可換単項式」（つまり、x _aの積）と同一視できる。つまり、語 ( a ₁ , a ₂ ,..., a _n ) を単項式x _{a 1} x _{a 2} ... x _{a n}と同一視する。したがって、 A上の語は、Rのkベクトル空間基底を形成する。次に、R上でシャッフル積が定義される。これはk-双線型で結合的かつ可換な積であり、шで表され、単語上で再帰的に次のように定義できる。

1 ш v = v ‍ 任意の単語vについて;

u ø 1 = u ‍ 任意の単語uに対して。

ua ш vb = ( u ш vb ) a + ( ua ш v ) b ‍ 任意のa、b ∈ Aおよび任意の単語uとvについて。

アルファベットA上のシャッフル代数は、乗法としてшを付与された加法群Rとして定義される。ラドフォードの定理^[16]は、リンドン語がこのシャッフル代数の代数的に独立した要素であり、それを生成することを述べている。したがって、シャッフル代数はk上の多項式環と同型であり、不定部分はリンドン語に対応する。^[16]

• 辞書式に最小の文字列回転
• 形態素
• シュトゥルム語
• ネックレス（組み合わせ論）