Thompson群と文脈自由言語

くるる @kururu_goedel

というわけで、記憶の新しいうちに今日のセミナーの報告するよー。Thompson群と形式言語理論っていうやつ。

くるる @kururu_goedel

一般にGを有限生成群として、Sをその有限なgenerating setとする。すると自然にS*からGへの上射が入る。発表者は同一視するねーとか言っていたけど、πで書くことにする。

くるる @kururu_goedel

このとき、WP_S(G)をπ(w)=1_Gとなるようなw∈S*全体とする。WPはWord Problemの意味だそうな。そして、CoWP_S(G)=S*\WP_S(G)とする。こちらはco-Word Problem。

くるる @kururu_goedel

このWPなりcoWPなりの形式言語としての複雑さはどうなの、っていうことが一般に考えられる。例えば、WP(G)が正規言語になることと、Gが有限群であることは同値で、これは1971年の結果ということ。だから歴史のある研究なんですな。

くるる @kururu_goedel

んで、WP(G)が決定性プッシュダウンオートマトンで受理されるような言語になることは、Gがvirtually freeだということと同値になる、というのが80年代に証明されているそうだ。クレジット付けたいんだけど、メモった名前が読めない。

くるる @kururu_goedel

virtually freeって何かとぐぐってみたら、finite index subgroupでfreeなやつがあることを言うらしい。代数わからん。

くるる @kururu_goedel

念のため、ここまでは補集合に関して閉じたクラスだったので、WPを考えるのとcoWPを考えるのは一緒。

くるる @kururu_goedel

CFLの場合、WPがCFLになることはGがvirtually freeになることと同値だそうで、要するに決定性と非決定性プッシュダウンオートマトンの違いはWPでは出てこないんですな。不思議な現象だと思うけど、本題でもないし発表者はサクッと触れてスルー。

くるる @kururu_goedel

文脈依存文法では、なんかShapiroが部分的な結果を残しているけどまだ謎で、それ以上はもっと謎らしい。

くるる @kururu_goedel

そうそう、途中からgenerating setのSを無視しているけど、どのSを取っても言語の複雑さには影響がないそうで。まあそれっぽい感じはする。

くるる @kururu_goedel

coWPがCFLになるような群をcoCF群と呼ぶことにする。coCF群のクラスはいくつかの操作について閉じていて、まあそこそこよい性質を持っているそうな。

くるる @kururu_goedel

でも、その「良い性質」からは導けない事実として、Thompson群はcoCF群であることが、Lehnart -Schweitzenによって2006年に示されているそうだ。けっこう新しい結果になるね、と発表者。

くるる @kururu_goedel

予想としてThompson群はuniversalなcoCF群になる、つまり任意のcoCF群はThompson群に埋め込める、というものがあるそうで。発表者曰く、予想とはいえあまり信じている人はいないそうなんだけど、ともかく。

くるる @kururu_goedel

んで、発表者の仕事としては、Thompson群がcoCFになることの証明を少し変えて、違った群がcoCFであることを示している。それが反例候補として有望なんじゃないかという話。

cocycle @coboundary

@kururu_goedel はじめまして。一般にある性質Aをみたすfinite index subgroupが存在するときvirtually Aという言い方をします。free以外にもvirtually torsion-freeとかvirtually abelianとか。

くるる @kururu_goedel

@coboundary どうもありがとうございます。そのあたりまでwikipediaで読んだんですが、一応表面的な意味は追えても感覚がつかめないので…。

くるる @kururu_goedel

発表は、ここでThompson群がcoCFになることの証明をざっくりやって、これの変形でその発表者の定理も証明できるよってところまで。

くるる @kururu_goedel

これ、形式言語の方の言葉にしっかり翻訳できたら、そちらを本業にしている人からいろいろ教えてもらえるのではないかと思うのだけど、どうかなぁ。

くるる @kururu_goedel

ああ、なんか発表を全部把握したようなふりをしていますが、例として出された群の説明は途中からついていけなかったので、そこは完全省略してます。

くるる @kururu_goedel

ひとまずそんなんでした。このセミナーは代数の人たちのものだったので、皆さんそれっぽいアプローチで聞いていたようだったのですが、形式言語または集合論のノリでなにかできないかなと考えているところです。