表題番号：2009B-064
日付：2010/04/05
研究課題並列書き換え系の研究 － 特に、並列構文解析とその応用
| 研究者所属（当時） | 資格 | 氏名 | |
|---|---|---|---|
| （代表者） | 教育・総合科学学術院 | 教授 | 守屋 悦朗 |
- 研究成果概要
- 研究代表者は従来から、並列計算の概念、とくに交代性（alternation）という概念を、所謂Chomsky階層と呼ばれる形式文法の各クラスやオートマトンのクラスになどに導入し、その記述能力・計算能力について研究を行なってきた。本特定課題研究では、形式文法の中でも実用的にも重要な文法のクラスである文脈自由文法（CFG）に交代性を導入したalternating CFGの構文解析法とその応用について研究することを目的とした。
「交代性」の概念はA.K.Chandra, D.C.Kozen, L.J.Stockmeyer (“Alternation,” J. Assoc. Comput. Mach. 28, 114-133, 1981）によって並列計算の概念の１つとしてTuring machineに対して初めて導入された。研究代表者は、1989年の論文
E.Moriya, A grammatical characterization of alternating pushdown automata, Theor. Comput. Sci. 67, pp.75-85, 1989
において交代性の概念を形式文法に初めて導入した。その後、肯定性の概念を導入した文法やオートマトンの研究を進め、多くの研究成果を発表している。特に、2010年発表の論文
E.Moriya and F.Otto, On Alternating Phrase-Structure Grammars, International J. Foundations of Comput. Sci., Vol.21, pp.1-25, 2010.
において、研究はかなり進展したにもかかわらず、交代性文法の生成能力が完全に解明されたわけではない。多くの未解決問題が残っているし、まったくの手付かずの課題もある。その１つに、交代性を導入した書き換え系（特に alternating CFG）の構文解析法の開発がある。実用的にも重要な文法であるCFGについては、様々な構文解析アルゴリズムが知られている。CFGの非終端記号は名詞、動詞、名詞句、名詞節、文などの文法的カテゴリーを表すものと考えられるので、その非終端記号に交代性を導入したalternating CFGにおいては、「交代性非終端記号」は、それに対応する文法的カテゴリーが複数の意味をもつ場合を表現するものと考えることができる。そのような見地から、alternating CFGの構文解析法を研究することを本特定課題研究の目標の1つとした。
現在までに得られた成果の１つは、
E.Moriya and F.Otto, Syntax analysis for alternating context-free grammars, preprint, 2009.
である。良く知られている(交代性のない)CFGに対する構文解析法では、文法から消去ルールをなくすこと(ε-free CFGに変換すること)が前提となる。この論文では、交代制の入ったalternating CFGにおいて消去ルールをなくすことを証明するための前提として、alternating CFG Gが生成する言語 L(G) が空語εを含むか否かを判定する問題が決定可能であることを証明した。
しかし、alternating CFGから消去ルールをなくすまでの道のりはまだ遠いように思われる。
当面、CFGのサブクラスに交代制を導入した場合について、その構文解析法を開発する研究を継続して進めたい。