こんにちは。finalです。
これは ISer Advent Calendar 2022の12/18の記事です。
なんか1日早いんですけど、まだ明日も書くつもりでいます()
Advent Calendarに面白そうな数学の記事があったので、僕も数学の話がしたくなってしまったのです。
早速ですが、万物の根源は何でしょうか。有限の記号列ですよね。
人間の世界は、有限の記号列から出来ているといっても過言ではありません。
人間の話す言葉、プログラム、等々、世界は有限の記号列からできています。数学も例外ではありません。
数学で問題となる対象は、何らかの有限の記号列で表現されている必要があると思います。
また逆に、ある対象が複数の有限の記号列で表現されることがあります。
例えば、「7」という数は、7,3+4,2+5,1+2+4,1+1+1+1+1+1+1など、複数の記号列がそれを表します。
このような記号列を全部集めると、「整数上で7という数字を表す言語」が作れそうですよね。なんだか形式言語っぽい話になってきました。
有限生成群上の「言語」を考える
を群として、によってが生成されているとします。すなわち、任意のは、が存在してと表せます。
そこで、次のような言語(#)を考えます。に対し、
とします*1。ここで、の*はKleene starで、をアルファベットとしてみた時そのアルファベットの有限列(空列含む)全体からなる集合です。に対し、は記号列を表しますが、でその記号列が指し示す群の元を指すことにします。
例えば、とします。演算が積でないのはややこしいですが、なので、
となります。
モチベーションについて
有限生成群上の言語(#)を集合としては定義できましたが、具体的にその言語がどのようなクラスに属しているかは気になります。
正則なのか、文脈自由なのか、…ということです。
もし、比較的簡単なクラスに属していたとすれば、それは興味深い事実です。
「群」というのは非常に豊かな対象で、演算も多様な意味で定義されています。
ですが、そのような群上の言語を受理するオートマトンや、言語を生成する規則などは、そのような「豊かな意味」がどんなに豊かなのかを知らなくても、有限の規則に従って演算を処理するだけで「2つの表記が群の中で同じものを指すかどうか」を判定することができる、ということになるのです。
そんなことができるのか、という風に思われるかもしれません。
この問題は「Dehn's problem」や「Word problem」とも呼ばれていて、Wikipediaにも載っています。
実際、ある有限生成群についてこの言語が計算可能にはならないことが示されています。この話はどこかで書きたいです。
いくつかの種類の群の言語(#)については、計算可能ですし、きれいな言語クラスに属します。
以下のような定理が存在します。
有限生成群について次の(1)(2)は同値である*2。
(1) はVirtually free groupである。
(2) についての言語(#)は文脈自由言語である。
(2)⇒(1)は、おそらく難しいと思います。言語に属する記号列に対応するケイリーグラフ上のパスにをかけて閉路にしたものに対角線を引いて三角形に分割していくとき、Chomsky 標準形をうまく使うと対角線の長さに上限を与えることができます。そこからよく意味の分からないことをやると、示せるみたいですね…()(参考文献に証明があるので、どなたか教えてください)。
ここでは、(1)⇒(2)を示そうと思います。
有限生成なVirtually free group
Virtually free groupは自由群を正規部分群に持つ群で、さらに指数が有限になっているもののことです。
すなわち、 (右剰余類)とすると、 で任意のは、を用いて、
と表すことができます。
そして、さらには有限生成なので、有限集合を用いてとなっているとします。
ともに有限集合であり、について、それぞれ次のようなが定まるというわけです(は簡約済み)。
この関係式は有限個しか存在しません。そのため、予め全てのについてこの関係を用意しておきます。
なんだか、プッシュダウンオートマトンに使えそうな気がします。
プッシュダウンオートマトンを構成する
気持ちとしては、のケイリーグラフに判定用のグラフをちょっと付け加えたようなものとしてプッシュダウンオートマトンを作ります。
プッシュダウンオートマトンを次のように構成します。
- : 状態の有限集合。ここでは、とする(は後述)。
- : 入力アルファベットの有限集合。ここでは、とする。
- : スタックアルファベットの有限集合。ここでは、とする*3。
- : 遷移関係。後で定義。
- : 初期状態。ここでは、とする(: の単位元)。
- : 初期スタック記号。
記号列を受理することを考えます。を一致するか判定したい目的の元とします(の)。はと(簡約すれば)一意的に表せるので、まず、の時(またその時に限って)、
となるように遷移関係を設定したいです(括弧内は時点表示:ID を表す3つ組で、現状態、残り文字列、スタックの記号列を表します)。そのためには、次のようにすればよいことがわかります。
状態にいて、記号を次に認識する状況を考えます。この時、 となるとします。 の1番目の文字をとします。
もしスタックの一番上の文字がならば、これをスタックからpopして、2文字目以降があればそれをpush(またはpop)していって、状態に移ります(注: は複数文字のこともあるので、その場合は遷移をいくつかに分けて(中間状態()を用意して)、繰り返しスタックの一番上の文字を見ていくことになります。ですがそれでも遷移と状態は有限個で確定します)。一番上の文字が以外ならば、スタックにをpushします。
さきほど有限個用意しておいたの関係をもとに、これらの遷移関係を全部に入れます。
そうすると、で、となっているとすれば、この遷移に従うことで、
となります(は簡約結果を表す。例: )。さらになので、うまく遷移関係を設定できたことになります。
popとpushをうまく使い分けることで、簡約ができるのがポイントですね。
さて、 という状況になったとします()。この状態になったときに限って、ある状態 において、IDがとなるようにしたいです。
そのためには、の語の長さをとして、新たに状態を個に追加します。それは、状態から一本道で、遷移するごとに、スタックの一番上のアルファベットを見て、それがのものとして正しい場合に限ってpopするように定めればよいです。その道の終点から、さらにもう1つ状態を追加して、そこで初期記号もpopできるようにします。これにより言語(#)は受理できました。
まとめ
知らない世界でしたが、群論と形式言語がつながっている世界で、色々な論文を読んでいると本当にワクワクしてきました。
早く(2)⇒(1)が理解したいです。
参考文献
- Word problem for groups (Wikipedia)
- The Word Problem in the Chomsky Hierarchy
- Word Problemの全体像(どんなクラスのものがどんな種類の群に対応しているか)について書かれています。
- 群の語の問題と Muller–Schupp の定理
- 文脈自由言語とVirtually Free Groupの対応が説明されています。日本語ありがたい…
- Muller, D. E., & Schupp, P. E. (1983). Groups, the theory of ends, and context-free languages. Journal of Computer and system sciences, 26(3), 295-310.
- 文脈自由言語とVirtually Free Groupの対応の証明です。こちらの場合、(2)⇒(1)はThe theory of endsなるものやStalling structure theoremを用いています。
- Diekert, V., & Weiß, A. (2017). Context-free groups and Bass–Serre theory. In Algorithmic and geometric topics around free groups and automorphisms (pp. 43-110). Birkhäuser, Cham.
- 同じく文脈自由言語とVirtually Free Groupの対応の証明なのですが、こちらのほうが分かりやすい気がしました。長くて全部は読めていないのですが、(2)⇒(1)の証明がMuller, Schupp, 1983とは少し違いそうです。
謝辞
このような分野の存在を教えてくださった線形演習でお世話になったN先生に感謝します。