Discovery Sagaサイレントキーワード俯瞰

本課題では、ポジティブ性をもつ（否定演算を持たない）論理・関係代数の高い決定可能性を起点として、論理と関係代数の双方向的な視点から、新たな決定可能な体系の解明やより精密な計算複雑さの解析を与えることを目的として、研究を進めている。2021年度においては以下をおこなった。
（１）ポジティブ関係計算とポジティブ存在論理との間の表現力および簡潔さの比較：ポジティブ関係計算と３変数ポジティブ存在論理は（二項関係に関して）表現力が等価である一方で、３変数ポジティブ存在論理の式からポジティブ関係計算の項への劣指数サイズの変換は存在しない（Nakamura, 2020）。後者の結果について、有限モデル理論で知られるformula-sizeゲームを関係計算に新たに導入し、よりロバストな証明を与えた。また、この指数的な簡潔さの差は、２変数ポジティブ存在論理とそれに対応するポジティブ関係計算の間では発生せず、３変数の場合に限って発生することを明らかにした。（Nakamura, 2020）とそれを拡張した本結果は、論文誌 Journal of Logical and Algebraic Methods in Programming に採録された。
（２）ポジティブ存在論理とハイパーエッジ置換文法との間のグラフ言語に関する表現力の研究：グラフ言語を表現するための空間意味論を導入し、ポジティブ存在論理とハイパーエッジ置換文法のいくつかのクラスの間で、表現可能なグラフ言語のクラスが一致すること（Kleeneの定理）を示した。本結果は、国際会議 30th EACSL Annual Conference on Computer Science Logic (CSL 2022) に採録された。