言葉の組合せ論

単語の組合せ論は、単語と形式言語の研究に焦点を当てた組合せ論から派生した、数学のかなり新しい分野です。この主題は、文字や記号、およびそれらが形成する シーケンスを調べます。単語の組合せ論は、代数やコンピューターサイエンスを含む数学の研究のさまざまな領域に影響を及ぼします。この分野には幅広い貢献がありました。最初の研究のいくつかは、 1900年代初頭のAxel Thueによる平方のない単語に関するものでした。彼と同僚は単語内のパターンを観察し、それを説明しようとしました。時が経つにつれて、単語の組合せ論はアルゴリズムとコーディングの研究に役立つようになりました。それは抽象代数の発展と未解決の問題への回答につながりました。

組合せ論は離散数学の一分野です。離散数学は可算構造の研究です。これらのオブジェクトには明確な始まりと終わりがあります。可算オブジェクトの研究は、微積分や無限構造を研究する解析学などの分野とは逆です。組合せ論は、さまざまな表現を使用してこれらのオブジェクトを数える方法を研究します。単語の組合せ論は、単語と形式言語の研究に焦点を当てたこの分野の最近の発展です。形式言語とは、人々が情報を伝達するために使用する記号の集合と記号の組み合わせです。^[1]

まず、単語の研究に関連する用語をいくつか説明する必要があります。まず第一に、単語は基本的に有限集合内の記号または文字のシーケンスです。^[1] これらの集合の 1 つは、一般にアルファベットとして知られています。たとえば、「encyclopedia」という単語は、英語のアルファベットの記号のシーケンスであり、26 文字の有限集合です。単語はシーケンスとして記述できるため、他の基本的な数学的記述を適用できます。アルファベットは集合 なので、当然のことながら、空集合はサブセットです。つまり、長さが 0 の一意の単語が存在します。単語の長さは、シーケンスを構成する記号の数によって定義され、 で表されます。^[1] 再び「encyclopedia」の例を見てみましょう。encyclopedia には 12 文字があるためです。大きな数の因数分解の考え方は単語に適用でき、単語の因数は連続する記号のブロックです。^[1]したがって、「cyclop」は「encyclopedia」の因数です。 ${\displaystyle w}$${\displaystyle |w|}$${\displaystyle |w|=12}$

シーケンス自体を調べることに加えて、単語の組合せ論で考慮すべきもう 1 つの領域は、シーケンスを視覚的に表現する方法です。数学では、データをエンコードするためにさまざまな構造が使用されます。組合せ論で使用される一般的な構造は、ツリー構造です。ツリー構造は、頂点が 1 本の線 (パスまたはエッジと呼ばれる) で接続されているグラフです。ツリーにはサイクルが含まれない場合があり、完全である場合とそうでない場合があります。単語は記号で構成されているため、単語をエンコードし、ツリーを使用してデータをエンコードすることができます。 ^[1] これにより、オブジェクトの視覚的な表現が得られます。

単語の組合せ論の起源をまとめた最初の本は、M.ロテールという名で呼ばれる数学者のグループによって書かれた。彼らの最初の本は、単語の組合せ論がより広く普及した1983年に出版された。^[1]

単語の組合せ論の発展に大きく貢献したのは、繰り返しを研究したアクセル・トゥー（1863-1922）である。トゥーの主な貢献は、無限の平方のない単語の存在の証明である。平方のない単語には、隣接する繰り返し因数がない。^[1] 明確に言えば、「dining」は「in」が連続して繰り返されているため平方のない単語ではないが、「servers」は平方のない単語であり、2つの「er」因数が隣接していない。トゥーは、置換を使用して、無限の平方のない単語の存在に関する彼の予想を証明した。置換とは、記号を単語に置き換える方法である。彼はこの手法を使用して、彼のもう1つの貢献であるトゥー・モース列、またはトゥー・モース語を説明した。^[1]

トゥーはスクエアフリー単語に関する論文を2本執筆しており、2本目はトゥー・モース単語に関するものであった。 名前にマーストン・モースが含まれているのは、トゥーと同じ結果を発見したが、2人は独立して研究したためである。トゥーは、重複のない単語の存在も証明した。重複のない単語とは、2つの記号 と について、パターンが単語内に存在しない単語である。2本目の論文では、無限の重複のない単語とスクエアフリー単語の関係を証明し続けている。トゥーは、2つの異なる文字を使用して作成された重複のない単語を取り上げ、置換を使用して3文字のスクエアフリー単語に変換する方法を示している。^[1]${\displaystyle x}$${\displaystyle y}$${\displaystyle xyxyx}$

前述のように、単語は記号の並びを調べることで研究されます。パターンが見つかり、それを数学的に記述することができます。パターンは回避可能なパターンか、回避不可能なパターンのどちらかです。回避不可能なパターン、つまり規則性の研究に大きく貢献したのは、1930 年のフランク ラムゼイです。彼の重要な定理は、整数、に対して、完全グラフが 2 色でどのように色付けされても、各色の単色部分グラフが常に存在するような最小の正の整数が存在するというものです。^[1]${\displaystyle k}$${\displaystyle m\geq 2}$${\displaystyle R(k,m)}$

避けられないパターンの研究に貢献した他の人物には、ファン・デル・ワールデンがいる。彼の定理は、正の整数をクラスに分割すると、未知の長さの等差数列を含むクラスが存在するというものである。等差数列とは、隣接する数の間の差が一定である数列である。^[1]${\displaystyle k}$${\displaystyle c}$${\displaystyle c}$

避けられないパターンを調べるとき、セスキパワーも研究されます。いくつかのパターン、、の場合、セスキパワーは、、、 の形になります。これは、スクエアフリーパターンや避けられないパターンなどの別のパターンです。Coudrain とSchützenberger は、主に群論への応用のためにこれらのセスキパワーを研究しました。さらに、Zimin はセスキパワーがすべて避けられないことを証明しました。パターン全体が現れるか、セスキパワーの一部だけが繰り返し現れるかに関係なく、それを避けることはできません。^[1]${\displaystyle x}$${\displaystyle y}$${\displaystyle z}$${\displaystyle x}$${\displaystyle xyx}$${\displaystyle xyxzxyx}$${\displaystyle \ldots ~}$

ネックレスとは、円形の列からなる単語から構成される。音楽や天文学で最もよく使われる。1894年にFlye Sainte-Marieは長さのバイナリde Bruijnネックレスが存在することを証明した。de Bruijnネックレスには、一定数の文字からなる長さnの単語からなる因数が含まれる。単語はネックレスに1度だけ現れる。^[1]${\displaystyle 2^{2^{n-1}-n}}$ ${\displaystyle 2^{n}}$

1874年、ボードットはバイナリ・ド・ブリュイン・ネックレス理論を応用して、最終的にモールス信号に取って代わることになるコードを開発した。この問題はサント＝マリーから1934年にマルティンへと引き継がれ、マルティンはド・ブリュイン構造の単語を作成するアルゴリズムを検討し始めた。その後、1943年にクラース・ポスチュムスが取り組んだ。^[1]

おそらく、単語の組合せ論で最も応用された結果は、ノーム・チョムスキーが開発したチョムスキー階層でしょう。彼は1950年代に形式言語を研究しました。^[2] 彼の言語の見方は主題を単純化しました。彼は単語の実際の意味を無視し、頻度や文脈などの特定の要素を考慮せず、短い用語のパターンをすべての長さの用語に適用します。チョムスキーの研究の基本的な考え方は、言語を4つのレベル、つまり言語階層に分割することです。4つのレベルは、規則的、文脈自由、文脈依存、および計算可能列挙または無制限です。^[2] 規則的は最も複雑ではなく、計算可能列挙は最も複雑です。彼の研究は単語の組合せ論から生まれましたが、他の分野、特にコンピューターサイエンスに大きな影響を与えました。^[3]

フランソワ・シュトゥルムによって作られたシュトゥルム語は、語の組合せ論に由来する。シュトゥルム語には、同等の定義がいくつか存在する。例えば、無限語がシュトゥルム語であるためには、任意の非負整数 に対して、長さ の異なる因数を持つ必要がある。^[1]${\displaystyle n+1}$${\displaystyle n}$${\displaystyle n}$

リンドン語は、与えられたアルファベット上の、それぞれの共役類から最も単純で最も整然とした形式で書かれた語である。リンドン語が重要であるのは、任意のリンドン語 に対して、 、となるリンドン語とが存在するからである。さらに、チェン、フォックス、リンドンによる定理があり、それによれば、任意の語にはリンドン語の一意の因数分解があり、因数分解語は非増加である。この特性のため、リンドン語は代数、特に群論の研究に用いられる。それらは交換子の考え方の基礎となる。^[1]${\displaystyle x}$${\displaystyle y}$${\displaystyle z}$${\displaystyle y<z}$${\displaystyle x=yz}$

コブハムは、ウジェーヌ・プルーエの有限オートマトンに関する研究を寄稿した。数学的なグラフは、エッジとノードで構成される。有限オートマトンでは、エッジにアルファベットの文字が付けられる。グラフを使用するには、ノードから始めて、エッジに沿って移動し、最終ノードに到達する。グラフに沿ってたどるパスが単語を形成する。ノードとエッジの数は数えられるが、2つの異なるノードを接続するパスは1つだけであるため、これは有限グラフである。 ^[1]

1838年にカール・フリードリヒ・ガウスによって作成されたガウスコードは、グラフから開発されました。具体的には、平面上の閉じた曲線が必要です。曲線が有限回数だけ交差する場合、交差点に使用されているアルファベットの文字でラベルを付けます。曲線に沿って移動し、交差点を通過するたびに各文字を記録することで単語を決定します。ガウスは、単語内で同じ記号が現れる間隔が偶数であることに気付きました。 [ ^1]

ヴァルター・フランツ・アントン・フォン・ディックは、 1882年と1883年に発表した論文によって、群論における単語の組合せ論の研究を始めた。彼は単語を群の要素として使用することから始めた。 ラグランジュも1771年に順列群に関する研究で貢献した。^[1]

群論で研究される単語の組み合わせ論の一つの側面は、簡約語である。グループは、アルファベット上の単語で構成され、生成元と逆元を含み、アルファベット中のいくつかのaに対してaāまたはāaの形式で現れる因子は除外される。 簡約語は、因子aā、āaを使用して要素を相殺し、一意の単語に達すると形成される。^[1]

ニールセン変換も開発された。自由群の要素の集合に対して、ニールセン変換は3つの変換によって達成される。要素をその逆数で置き換える、要素をそれ自身と別の要素の積で置き換える、 1に等しい要素をすべて削除する。これらの変換を適用することで、ニールセンの縮小集合が形成される。縮小集合とは、どの要素も他の要素と掛け合わせて完全に打ち消すことができない集合である。ニールセン変換とシュトゥルム語との関連もある。^[1]

群論における単語の組合せ論の研究で検討される問題の一つは、半群の2 つの要素 に対して、は との定義関係を法として成り立つというものである。 ポストとマルコフはこの問題を研究し、決定不可能 であると判断した。これは、あらゆる場合に質問に答えられるアルゴリズムは存在しないことを意味する（そのようなアルゴリズムは、そのアルゴリズムが解くことができない単語問題にエンコードできるため）。^[1]${\displaystyle x}$${\displaystyle y}$${\displaystyle x=y}$ ${\displaystyle x}$${\displaystyle y}$

バーンサイド問題は、無限立方体のない語の存在を利用して証明されました。この問題は、群が有限個の生成元を持ち、群内で の基準 を満たす場合に群が有限であるかどうかを尋ねます。[ ^1]${\displaystyle x^{n}=1}$${\displaystyle x}$

多くの単語問題は、ポスト対応問題に基づくと決定不可能である。共通の定義域と共通の余域を持つ任意の2つの準同型 写像は、定義域内に となる単語が存在するかどうかを問うポスト対応問題の例を形成する。ポストは、この問題が決定不可能であることを証明した。したがって、この基本問題に還元できる単語問題も同様に決定不可能である。^[1]${\displaystyle g,h}$${\displaystyle w}$${\displaystyle g(w)=h(w)}$

単語の組合せ論は方程式にも応用できる。マカニンは、方程式が単語から構成される場合、有限の方程式系の解を見つけることが可能であることを証明した。^[1]

• フィボナッチ数列
• コラコスキ配列
• レヴィの補題
• 部分的な単語
• シフトスペース
• 単語メトリック
• 文章題（計算可能性）
• 文章題（数学）
• グループ向けの文章問題
• ヤング・フィボナッチ格子

ウィキメディア・コモンズには、単語の組合せ論に関連するメディアがあります。

• Jean Berstelのページ
• テロ・ハルジュのページ
• ギ・メランソンのページ