カーナビの「抜け道」通りに走ったらかえって混んでいた、というような経験はありませんか？これは、他人も自分と同じような振舞いをしがち。ということを考えずに行動することが原因です。他人の振舞いを予想しつつ、もっとも良い戦略を探し出すのがゲーム理論です。私の取り組んでいるのはグラフゲームと呼ばれ、ネットワーク上のコンピュータや道路を走る自動車をゲームの参加者（プレイヤー）とみなします。ゲームにおけるよい戦略（必勝戦略、ナッシュ均衡など）が、ネットワークが大混雑してもダウンしないオンラインシステムや、目的地に到着するための最もよい運転経路になります。

有限オートマトンや文脈自由文法（CFG）は、整数などのデータ値を直接扱えないため、現実のプログラムを直接表現することはできません。しかし、有限オートマトンやCFGにデータ値を扱える能力を加えるとすぐにチューリング機械と能力等価になってしまい、いろいろな処理の自動化が困難になります。
　近年、大規模構造化データ処理の基本モデルとして、レジスタオートマトンが再注目されています。レジスタオートマトン（RA）は、有限オートマトンに、データ値を記憶するためのいくつかのレジスタを付加したモデルです。データ値に対しては比較演算のみが許され、そのことで計算能力が大きくなりすぎず、有限オートマトンのよい性質を受け継いでいます。
　私達はこのような背景のもと、以下のような研究を行っています。
- RAをさらに抽象化した計算モデルとして、ノミナルオートマトン（NA）が知られています。NAでは、群作用による軌道が有限であるような（無限）集合に基づいて有限オートマトンを一般化することで、高い抽象度で議論を行うことができます。私たちはノミナル木オートマトンを定義して、正則言語の学習アルゴリズムや正則保存性に基づくモデル検査技法の開発を行っています。
- RAをXML文書問合せに利用しようとすると、いくつかの問題点があります。そこで、文脈自由文法 (CFG) にレジスタを付加したレジスタCFG (RCFG) に着目し、RCFGの諸性質を究明する理論的研究を行っています。現在まで、RCFGの所属問題、空問題はEXPTIME完全であり、ε-規則や単記号規則を禁止すると計算量が下がるなどの興味深い結果を得ています。
- CFGに重みを導入して拡張した計算モデルとして、重み付き文脈自由文法（MCFG）が知られています。重みは、確率、コストなど、計算の進行に付随して発生する定量的尺度を表現する概念であり、一般的には半環上の値として表現されます。通常のオートマトンや文法が言語を表現するのに対して、重み付きモデルは文字列から重みへの関数を定義します。 一方で、オートマトンや文法には曖昧さという概念があります。文字列の曖昧さとは、それを受理（文法の場合は生成）するオートマトンの実行の種類の数（文法の場合は導出木の数）を表します。オートマトンの場合、（重みのない）非決定性オートマトンを決定性オートマトンに等価変換できることはよく知られていますが、重み付きの場合、曖昧さによる関数の階層が存在することが知られています。CFGの場合、重みがなくても曖昧さによる言語階層が存在することが知られていました。本研究室では、WCFGにおいて重みに由来する曖昧さ階層が存在することを証明するなど、WCFGに関する理論的研究を行っています。
- 多重文脈自由文法(MCFG)という文法を提案しその諸性質を解明してきました。MCFGの生成能力は文脈自由文法(CFG) よりも大きく文脈規定文法(CSG) よりも小さいこと、多項式時間構文解析可能性や言語演算に対する閉包性など、CFG のよい性質を受け継いでいることがわかっています。本研究室では、MCFGに重みを導入したWMCFGを定義し、その諸性質を理論的に明らかにするための研究を行っています。これらの成果は理論的に興味深いとともに、(W)MCFGを生物系列解析に応用する際に重要な指針を与えます。