カテゴリー : Research

DLT’14に論文採択

単著論文が国際学会 DLT’14 (18th International Conference on Developments in Language Theory) に short paper として採択されました.論文は僕のページにて公開しています.
DLTは1993年に A. Salomaaと G. Rozenberg (2人ともヨーロッパ理論計算機科学協会元会長!) が発起人となり始められた形式言語・オートマトン理論のガチ專門会議です(参考)。理論色が強い学会という印象を持っています.

論文内容

Graph Spectral Properties of Deterministic Finite Automata“という,かなり一般的なタイトルの論文となっています.ある正規言語Lを認識するDFA達は無限に存在するのですが,そのDFA達の隣接行列(の固有値)構造に着目した時に,どういった秩序があるのかということを探った研究です.DFAに関して,その隣接行列(の固有値)構造について考察するというのは,いくつか似てる研究はあるものの,新しいと考えこのような一般的なタイトルをつけました.

ここでいうDFAの隣接行列とは,DFAから文字を忘れて単なる多重有向グラフとして見た時の隣接行列のことです.例えば
fib

というDFAに対応する隣接行列は[[1, 1],[1,0]]となります.任意のDFAから隣接行列は一意に定まりますが,隣接行列からそれに対応するDFAは一意に定まりません.隣接行列はDFAから「文字の情報を削ぎ落した構造」なのです.

最小定理

この論文ではDFAと隣接行列の関係に関していくつかの性質を示しています.その中で最も重要なものとして最小定理

DFAが最小 ⇔ DFAの隣接行列の階数と退化次数が共に最小

という最小DFAの線形代数的必要十分条件があります.階数(rank)は線形写像の像空間の次元,退化次数nullity)は線形写像の核(kernel)の次元ですね.ここでいう最小とは「同じ言語を認識するDFAの中で最小」ということを意味しています.最小DFAの存在や構成法は情報科学科の学生さんであれば学部で習う基礎事実です.最小DFAの必要十分条件というfundamentalな内容を「文字の情報を削ぎ落した構造」である隣接行列から導けたということで,僕的にとても気に入っている成果です.

⇐ の方向は階数・退化次数の定理より自明ですが,⇒の方向は自明ではありません.なぜなら,「状態数が小さい ⇒ 階数と退化次数が共に小さい」は一般的に成り立たないからです.次の図がそれを示しています.

Screen Shot 2014-05-03 at 8.08.02 PM

A1,B1,C1はそれぞれ同じ正規言語を認識するDFAで,M(A1),M(B1),M(C1)がそれぞれの隣接行列です.なお,A1は最小DFAとなっています.よく見るとB1はC1よりも状態数が少ないにも関わらず階数はC1の方が小さいことが分かります.同様の事実が退化次数に関しても言えます.A1においては定理に矛盾していない,つまり階数と退化次数がB1やC1に比べ小さいことに注意して下さい.

スペクトラルグラフ理論

この定理の証明には「スペクトラルグラフ理論」というグラフの隣接行列の固有値構造を調べる理論の基礎的な道具:Equitable partition が使われています.スペクトラルグラフ理論は一年前から一年かけて僕が主催して後輩と書籍を輪講をしていたのですが,輪講開始から半年たって Equitable partition がDFAに使えることに気づきました.実は Equitable partition を使わないバージョンの上記定理の証明は輪講を始める前から思いついてたのですが,Equitable partition のおかげで証明を大分ゴルフすることができたのです :-D  とはいえ,スペクトラルグラフ理論の輪講を決定したのは「DFAの解析に使える道具があるのでは?」と思ったから始めたので,当時の僕GJ!

証明は,スペクトラルグラフ理論の道具である Equitable partition と,オートマトン理論の道具である Nerode partitionの2つの登場人物を出会わせるものです.準備や初等的な事実・補題を除くと実質1ページぐらいのとてもコンパクト証明です.異なる2つの理論で使われていた2種類のpartitionが強く関連しているのは興味深いものです.証明が読みたい方は論文を参照して下さい

正規言語による文字列圧縮とのつながり

そもそもこの研究は「正規言語による文字列圧縮の計算量が低いような正規言語のクラス」に興味を持ったところから始まりました.正規言語による圧縮については,過去のエントリ

をご覧下さい.

研究の流れとしては

  1. 正規言語による文字列圧縮はDFAの隣接行列の冪乗が計算大変!
  2. 階数が1の行列は効率よく冪乗が計算できる超単純な構造を持っている.
  3. DFAの階数が1であるような正規言語のクラス:rank-one langugaes を解析しよう!
  4. でも,DFAの階数ってどれが最小なんだろう? 同じ言語を認識するDFAって無限にあるんだけど…
  5. 最小DFAの階数が最小っぽいよな… 常識的に考えて…
  6. 示そう! あ,退化次数も同時に最小になるっぽい!

という流れで上記の定理にいきつきました.線形代数の初等的事実ですが,階数が1の行列はその冪乗(の要素)がO(1)で計算できます(参考: “On rank one matrices and invariant subspaces” ).

発展

実は,この論文では rank-one languages のDFAにおける canoncial form を示しただけで,その性質を十分に解明することができませんでした.正直言うとわからないことだらけです.2つの正規言語が与えられた時,それらから新しい正規言語を作り出す様な演算は正規言語においてはたくさんあります.例えば和集合や積集合,shuffleや連接などなど.このような正規言語の演算とDFAの隣接行列(の固有値)構造がどのように対応するのかということを調べたかったのですが,これがまた難しいのです.むしろDFAだと無理なのでは?という感じです(投げやり).

論文では「ここがわかっていない〜」「こうすれば上手くいくはずなんだけど難しいんだ〜」ということを正直に書き連ねています.発展途中の研究ということで, short paper という結果は納得しています.が,もうちょっと頑張って full paper で通したかったなぁ…

論文採択について

学部〜修士では正規表現マッチングの並列化やコード生成,修士〜博士では正規言語による文字列圧縮,そして今はDFAの固有値構造の解析という流れを見ると,僕自身の興味が応用から基礎理論に向かっていることが分かります.これからは理論バリバリな成果をガンガン出していきたい所存ですが,その意味でDLTという理論色の強い会議にこのような成果で採択されたのは嬉しいです.論文に適切なコメントを着けてくれた @ranha 君,研究生活を全面的に支援してくださった首藤先生,アイディア段階の時に議論に付き合ってくれた @kinaba さんや京大・京産大の研究者方々に感謝を.

応用畑で育った人間として,理論の世界に身を投げるのはなかなか勇気のいる行動でした.実際この一年間は成果もろくに出さずほとんど輪講や論文読みのいわゆる「基礎学習」に時間を費やしてました.分野を変えるまではいきませんが,一般に研究者としての方針を変えるのは時間がかかると思います.今回の結果がDLTに reject されていたら「やっぱり応用の世界で生きていこうかな…」と迷ってた可能性が高いです.怖い.怖くない?怖い!

とはいえこのような結果になったわけですし,いろんな分野の道具をバリバリ使いこなして新たな正規言語の定理をガンガン生み出せるような人間になるために,これからも頑張って行きたい所存です.

 
Better Tag Cloud