有限生成群上の形式言語がどんなオートマトンで受理できるかを考える

こんにちは。finalです。
これは ISer Advent Calendar 2022の12/18の記事です。

adventar.org

なんか1日早いんですけど、まだ明日も書くつもりでいます()
Advent Calendarに面白そうな数学の記事があったので、僕も数学の話がしたくなってしまったのです。

早速ですが、万物の根源は何でしょうか。有限の記号列ですよね。
人間の世界は、有限の記号列から出来ているといっても過言ではありません。
人間の話す言葉、プログラム、等々、世界は有限の記号列からできています。数学も例外ではありません。
数学で問題となる対象は、何らかの有限の記号列で表現されている必要があると思います。

また逆に、ある対象が複数の有限の記号列で表現されることがあります。
例えば、「7」という数は、7,3+4,2+5,1+2+4,1+1+1+1+1+1+1など、複数の記号列がそれを表します。
このような記号列を全部集めると、「整数上で7という数字を表す言語」が作れそうですよね。なんだか形式言語っぽい話になってきました。

有限生成群上の「言語」を考える

 Gを群として、 S\subset G\,(|S|\lt\infty)によって Gが生成されているとします。すなわち、任意の g\in Gは、 s_1,s_2,\ldots,s_n\in Sが存在して g=s_1s_2\cdots s_nと表せます。
そこで、次のような言語(#)を考えます。 g\in Gに対し、

 \displaystyle
L_g=\{\sigma\in S^*\mid\bar{\sigma}=g\}

とします*1。ここで、 S^*の*はKleene starで、 Sをアルファベットとしてみた時そのアルファベットの有限列(空列含む)全体からなる集合です。 \sigma\in S^*に対し、 \sigma は記号列を表しますが、 \bar{\sigma}でその記号列が指し示す群の元を指すことにします。

例えば、 G=\mathbb{Z}, S=\{1,2\}とします。演算が積でないのはややこしいですが、 3=1+1+1=1+2=2+1なので、

 \displaystyle
L_3=\{111,12,21\}

となります。

モチベーションについて

有限生成群上の言語(#)を集合としては定義できましたが、具体的にその言語がどのようなクラスに属しているかは気になります。
正則なのか、文脈自由なのか、…ということです。

もし、比較的簡単なクラスに属していたとすれば、それは興味深い事実です。
「群」というのは非常に豊かな対象で、演算も多様な意味で定義されています。
ですが、そのような群上の言語を受理するオートマトンや、言語を生成する規則などは、そのような「豊かな意味」がどんなに豊かなのかを知らなくても、有限の規則に従って演算を処理するだけで「2つの表記が群の中で同じものを指すかどうか」を判定することができる、ということになるのです。

そんなことができるのか、という風に思われるかもしれません。 この問題は「Dehn's problem」や「Word problem」とも呼ばれていて、Wikipediaにも載っています
実際、ある有限生成群についてこの言語が計算可能にはならないことが示されています。この話はどこかで書きたいです。

いくつかの種類の群の言語(#)については、計算可能ですし、きれいな言語クラスに属します。
以下のような定理が存在します。

有限生成群 Gについて次の(1)(2)は同値である*2
(1)  GはVirtually free groupである。
(2)  Gについての言語(#)は文脈自由言語である。

(2)⇒(1)は、おそらく難しいと思います。言語に属する記号列に対応するケイリーグラフ上のパスに g^{-1}をかけて閉路にしたものに対角線を引いて三角形に分割していくとき、Chomsky 標準形をうまく使うと対角線の長さに上限を与えることができます。そこからよく意味の分からないことをやると、示せるみたいですね…()(参考文献に証明があるので、どなたか教えてください)。
ここでは、(1)⇒(2)を示そうと思います。

有限生成なVirtually free group

Virtually free groupは自由群を正規部分群に持つ群で、さらに指数が有限になっているもののことです。
すなわち、  F(X)\lhd G,H=F(X)\backslash G (右剰余類)とすると、 |H|\lt\infty で任意の g\in Gは、 x\in F(X),h\in Hを用いて、

 \displaystyle
g=xh

と表すことができます。

そして、さらに Gは有限生成なので、有限集合 S\subset Gを用いて \langle S\rangle=Gとなっているとします。

 H, Sともに有限集合であり、 \forall h\in H,\forall s\in Sについて、それぞれ次のような x'\in F(X),h'\in Hが定まるというわけです( x'は簡約済み)。

 \displaystyle
hs=x'h'

この関係式は有限個しか存在しません。そのため、予め全ての h\in H,s\in Sについてこの関係を用意しておきます。

なんだか、プッシュダウンオートマトンに使えそうな気がします。

プッシュダウンオートマトンを構成する

気持ちとしては、 Hのケイリーグラフに判定用のグラフをちょっと付け加えたようなものとしてプッシュダウンオートマトンを作ります。

プッシュダウンオートマトン M=(Q,\Sigma,\Gamma,\delta,q_0, Z_0)を次のように構成します。

  •  Q: 状態の有限集合。ここでは、 Q=H\cup Aとする( Aは後述)。
  •  \Sigma: 入力アルファベットの有限集合。ここでは、 \Sigma=Sとする。
  •  \Gamma: スタックアルファベットの有限集合。ここでは、 \Gamma=X\cup X^{-1}\cup\{Z_0\}とする*3
  •  \delta\subset( Q\times (\Sigma\cup\{\varepsilon\})\times\Gamma)\times(Q\times\Gamma^*): 遷移関係。後で定義。
  •  q_0\in Q: 初期状態。ここでは、 q_0=e\in Hとする( e: H単位元)。
  •  Z_0: 初期スタック記号。

記号列 \sigma=s_1s_2\cdots s_n\in S^*を受理することを考えます。 gを一致するか判定したい目的の元とします( L_g g)。 g g=xh,x\in F(X),h\in Hと(簡約すれば)一意的に表せるので、まず、 \bar{\sigma}=gの時(またその時に限って)、

 \displaystyle
(e, \sigma, Z_0) \vdash^* (h, \varepsilon, Z_0x)

となるように遷移関係を設定したいです(括弧内は時点表示:ID を表す3つ組で、現状態、残り文字列、スタックの記号列を表します)。そのためには、次のようにすればよいことがわかります。

状態 hにいて、記号 s\in Sを次に認識する状況を考えます。この時、 hs=x'h' となるとします。  x'の1番目の文字を x_1'\in Xとします。 もしスタックの一番上の文字が x_1'^{-1}ならば、これをスタックからpopして、2文字目以降があればそれをpush(またはpop)していって、状態 h'に移ります(注:  x'は複数文字のこともあるので、その場合は遷移をいくつかに分けて(中間状態( \in A)を用意して)、繰り返しスタックの一番上の文字を見ていくことになります。ですがそれでも遷移と状態は有限個で確定します)。一番上の文字が x_1'^{-1}以外ならば、スタックに x'をpushします。
さきほど有限個用意しておいた hs=x'h'の関係をもとに、これらの遷移関係を全部 \deltaに入れます。

そうすると、 \bar{\sigma}=\overline{s_1s_2\cdots s_n}=gで、 es_1=x_1 h_1,h_1s_2=x_2h_2,h_2s_3=x_3h_3,\ldotsとなっているとすれば、この遷移に従うことで、

 \displaystyle
(e, s_1s_2\cdots s_n, Z_0) \vdash (h_1, s_2s_3\cdots s_n, Z_0\pi(x_1))\vdash(h_2,s_3\cdots s_n, Z_0\pi(x_1x_2))\vdash\cdots\vdash (h_n,\varepsilon, Z_0\pi(x_1x_2\cdots x_n))

となります( \pi(\cdot)は簡約結果を表す。例: \pi(zyzxx^{-1}z^{-1})=zy)。さらに g=\overline{s_1 s_2\cdots s_n}=x_1 x_2\cdots x_n h_nなので、うまく遷移関係を設定できたことになります。
popとpushをうまく使い分けることで、簡約ができるのがポイントですね。

さて、 (h, \varepsilon, Z_0x) という状況になったとします( g=xh)。この状態になったときに限って、ある状態  q において、IDが (q, \varepsilon, \varepsilon)となるようにしたいです。
そのためには、 xの語の長さを lとして、新たに状態を l Aに追加します。それは、状態 hから一本道で、 \varepsilon遷移するごとに、スタックの一番上のアルファベットを見て、それが xのものとして正しい場合に限ってpopするように定めればよいです。その道の終点から、さらにもう1つ状態を追加して、そこで初期記号 Z_0 も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先生に感謝します。

*1:一般的には、それぞれの群に対して「単位元を表す文字列全体」という形でこの言語は定義されるのですが、ここではより問題意識に近い形で定義をしてみました。

*2:注釈*1 の言語に置き換えたものは、Muller-Schuppの定理と呼ばれています。

*3: 本当は X が有限であることを示す必要があります。 G が有限生成であることから示すことができます。