ポジティブ関係計算とポジティブ存在論理の相互的研究

正关系计算与正存在逻辑的相互学习

• 批准号: 21K13828
• 负责人: 中村 誠希
• 金额: $ 2.91万
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Early-Career Scientists
• 财政年份: 2021
• 资助国家: 日本
• 起止时间: 2021-04-01 至 2026-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-21K13828/
• 关键词: 関係代数; 有限モデル理論; 数理論理学; 計算困難さ; グラフ; オートマトン; 関係計算; 計算複雑さ

本課題では、ポジティブ性をもつ（否定演算を持たない）論理・関係代数の高い決定可能性を起点として、論理と関係代数の双方向的な視点から、新たな決定可能な体系の解明やより精密な計算困難さの解析を与えることを目的として、研究を進めている。2022年度においては以下をおこなった。（１）推移閉包演算を持つ"存在関係計算"の決定可能性／計算困難さに関する研究：３変数存在論理と等価な表現力を持つ関係計算である"存在関係計算"を導入した。この体系は制限された否定演算で拡張されており、ポジティブ関係計算と比べて真に表現力が高い。推移閉包演算で拡張した存在関係計算の体系に対して、辺飽和（edge saturations）を用いたグラフの集合による特徴付けを与え、これを用いて決定可能性／計算困難さを調べた。より具体的には、この体系の等式理論はフルの場合では決定不可能だが、関係積の演算を持たない体系ではcoNEXPで決定可能となることを示し、さらにその２つの部分体系に関してはオートマトンの構築方法を与えることによってPSPACEで決定可能（PSPACE完全）であることを示した。また、推移閉包演算を持たない体系では、coNP完全であることを示した。本結果は、国際会議LICS2023に採択された（to appear）。（２）変数出現を制限した関係計算の決定可能性に関する研究：kをある自然数として、等式の左右の項それぞれに変数が出現する回数を高々k回に制限した場合の等式理論の決定可能性を考えた。具体例として、関係計算のdot-dagger交替階層の各階層における決定可能性を考察し、国内研究集会MLG2022で口頭発表をおこなった。

In this paper, we discuss the starting point of possibility determination in algebra, the point point in both directions of algebra, the system of precision calculation, the analysis of precision calculation, and the improvement of research. The following is the year 2022. (1) the possibility of determining the possibility of decision

项目成果

Spatial Existential Positive Logics for Hyperedge Replacement Grammars

超边替换文法的空间存在正逻辑

• 发表时间: 2022
• 期刊: Proceedings of the 30th EACSL Annual Conference on Computer Science Logic
• 作者: Lorenzo Cavallina;Giorgio Poggesi;Toshiaki Yachimura;谷地村 敏明;谷地村 敏明;谷地村 敏明;Yoshiki Nakamura;野口 健太;Yoshiki Nakamura
• 通讯作者: Yoshiki Nakamura

変数出現を制限した関係計算について

关于限制变量出现的关系计算

• 发表时间: 2023
• 作者: Lorenzo Cavallina;Giorgio Poggesi;Toshiaki Yachimura;谷地村 敏明;谷地村 敏明;谷地村 敏明;Yoshiki Nakamura;野口 健太;Yoshiki Nakamura;Kenta Noguchi;中村誠希
• 通讯作者: 中村誠希

Expressive power and succinctness of the positive calculus of binary relations

二元关系正演算的表达力和简洁性

• DOI: 10.1016/j.jlamp.2022.100760
• 发表时间: 2022
• 期刊: Journal of Logical and Algebraic Methods in Programming
• 影响因子: 0.9
• 作者: Lorenzo Cavallina;Giorgio Poggesi;Toshiaki Yachimura;谷地村 敏明;谷地村 敏明;谷地村 敏明;Yoshiki Nakamura
• 通讯作者: Yoshiki Nakamura

ハイパーエッジ置換文法のための空間ポジティブ存在論理について

超边替换文法的空间正存在逻辑

• 发表时间: 2022
• 作者: Lorenzo Cavallina;Giorgio Poggesi;Toshiaki Yachimura;谷地村 敏明;谷地村 敏明;谷地村 敏明;Yoshiki Nakamura;野口 健太;Yoshiki Nakamura;Kenta Noguchi;中村誠希;中村誠希
• 通讯作者: 中村誠希

ポジティブ関係計算の formula-size game について

关于正关系计算的公式大小游戏

• 发表时间: 2021
• 作者: Lorenzo Cavallina;Giorgio Poggesi;Toshiaki Yachimura;谷地村 敏明;谷地村 敏明;谷地村 敏明;Yoshiki Nakamura;野口 健太;Yoshiki Nakamura;Kenta Noguchi;中村誠希;中村誠希;Yoshiki Nakamura;中村 誠希
• 通讯作者: 中村 誠希