表題番号：2002C-006 日付：2004/03/19
研究課題形式文法・オートマン理論における計算量理論的再考察
研究者所属（当時） 資格 氏名
（代表者） 教育学部 教授 守屋　悦朗
（連携研究者） Kassel University 教授 Friedrich Otto
研究成果概要
　本研究は、形式言語理論およびオートマトン理論におけるいくつかの問題を計算量理論的視点から再考察することを目指したものである。ドイツ・カッセル大学のOtto教授との国際共同研究である。
　主たる研究目標は、並列計算の概念、とくに、もともとオートマトン理論において導入された「交代性(alternation)」という概念を形式文法にも導入し、従来の形式文法とオートマトンとの間に成り立っていた相関関係が交代性の導入によってどのように変わるのかを明らかにすることにあった。守屋により1989年に導入されたalternating CFG（以下、ACFGと略記する）は、alternationを持たない従来のCFGと等価であるプッシュダウンオートマトンにalternationを持たせたalternating PDA（以下、APDAと略記）を特徴付けることを目指したものであったが、当時は成功するに至らなかった。本研究では、ACFGの新しいバージョンであるstate-alternating CFG（以下、state-ACFGと略記）を導入することにより、この特徴づけに成功した。これは、O.H.Ibarra - T.Jiang - H.WangによるACFGの変形版によるAPDAの特徴づけよりもずっと自然で美しいものである。また、この新しいstate-ACFGは従来のACFGよりも言語生成能力が高いこと（真に高いかどうかは未解決）、先に導入したACFGはAPDAの特殊ケースとして特徴付けられることも示すことができた。これらの成果により、APDAをalternationをもつCFGにより特徴付けるという当初の目標はようやく解決された。本研究では、こういったメインな結果以外にも、ACFGおよびstate-ACFGに関する基本的性質について研究成果を挙げることができた。
　また、交代性の概念を導入したshrinking two-pushdownオートマトンの言語受理能力についての研究も行ない、文脈依存言語のクラスに含まれる等の基本的結果を得た。
　主たる目標を支える基礎研究として並行して研究を行なったのが、グラフアルゴリズムの計算量の研究である。１つの決定問題から多くの特殊形が自然に導かれ、それらがいろんな計算量のクラスに対する完全問題になるという例は多くは知られていない。そのような新しい例として、グラフとそのその部分グラフに関するある種の問題を考え、それがさまざまな特殊形を自然に導き、しかも５つの主要な計算量のクラス NL, P, NP, PSPACE, NEXPに対する完全問題になることを示した。
　また、グラフのマッチング問題に関する並列近似アルゴリズムを提案し、その計算量について考察した。