動的論理の代数的一般化とその複雑さの理論解析

动态逻辑的代数推广及其复杂性的理论分析

• 批准号: 16J08119
• 负责人: 中村 誠希
• 金额: $ 1.22万
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2016
• 资助国家: 日本
• 起止时间: 2016-04-22 至 2019-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-16J08119/
• 关键词: ポジティブ関係計算; ポジティブ存在論理; 等式理論; 一階述語論理; 推移閉包演算; 決定可能性; 計算複雑性; 有限モデル論; 動的論理; クリーニ代数; 関係代数; Antimirov微分; パス幅; グラフ; 正規表現; Antimirov偏微分

本年度の前半は、前年度の Kleene 寓圏（推移閉包演算付きポジティブ関係計算）の EXPSPACE 決定可能性の結果の動的論理的な拡張を試みた。しかし、その体系が複雑化したため、いま一度問題の単純化に切り替えて研究をおこない、以下の結果を得た。1. 関係計算と３変数一階述語論理の間の表現力の等価性をポジティブな場合に拡張した。とくに推移閉包付きポジティブ関係計算が、３変数単項推移演算閉包付きポジティブ存在論理と表現力が等価であることがわかった。この結果は、申請者博士論文に記載した。2. 1. の対応関係の基づいて上記の結果を拡張して、（変数制限のない）単項推移閉包演算付きポジティブ存在論理の等式理論の EXPSPACE 決定可能性を示した。本結果については、現在投稿準備中である。3. 決定不能性に関して、１文字制限付き関係計算の決定不能性を示した。既存の（ポジティブでない）一般の関係計算の等式理論の決定不能性の結果を強化して、文字を１種類だけに制限した（結合・和・補のみの演算からなる）関係計算についても決定不能であることを示した。この結果の系として、グラフ上の３変数一階述語論理の決定不能性も明らかにした。この結果は、国際会議 ICLA '19 で発表をおこなった。また、上記と並行して、十数年の間未解決問題であった中間論理に関する問題である「古森-鹿島の問題」に対する反例を与え、数理論理学に関するいくつかの国内会議で発表をおこなった。

In the first half of this year, Kleene's logic of determining the possibility of the result (calculation of the relationship between the closure and the previous year) was tested. The following results were obtained from the study of the purification of the first degree problem. 1. The expression of the relationship between the first order predicate logic and the third order predicate logic is equivalent to the first order predicate logic The closure of the closure. The results were recorded in the doctoral thesis of the applicant. 2. 1. The results of the relationship are shown in the following table. This result is in preparation. 3. Determination of non-determinability is related to the calculation of non-determinability of a literal constraint. The existence of a general relationship calculation equation theory can not determine the results of strengthening, text, a type of limit (combination, and complement) relationship calculation can not determine the results of this The result of this is that the logic of the first order predicate is not determinable. ICLA '19 International Conference on International Trade and Development. The problem that has not been solved for more than ten years is related to the problem of intermediate logic. The problem of "Goossen-Kashima" is related to the counterexample of mathematics theory.

项目成果

Partial derivatives on graphs for Kleene allegories

Kleene 寓言图的偏导数

• DOI: 10.1109/lics.2017.8005132
• 发表时间: 2017
• 期刊: IEEE Computer Society
• 作者: 辻本真規;酒井明人;松本洋介;中辻知;Nakamura Yoshiki;Nakamura Yoshiki
• 通讯作者: Nakamura Yoshiki

「古典論理で極小な論理式だけで公理化できる論理に関する予想」の反例について

关于“经典逻辑中仅用最小逻辑公式即可公理化的逻辑猜想”的反例

• 发表时间: 2018
• 作者: 辻本真規;酒井明人;松本洋介;中辻知;Nakamura Yoshiki;Nakamura Yoshiki;Yoshiki Nakamura;Yoshiki Nakamura;中村誠希;中村誠希;中村誠希
• 通讯作者: 中村誠希

ポジティブ関係計算について

关于正相关计算

• 发表时间: 2019
• 作者: 辻本真規;酒井明人;松本洋介;中辻知;Nakamura Yoshiki;Nakamura Yoshiki;Yoshiki Nakamura;Yoshiki Nakamura;中村誠希
• 通讯作者: 中村誠希

Partial Derivatives for Relation Models

关系模型的偏导数

• 发表时间: 2017
• 作者: 辻本真規;酒井明人;松本洋介;中辻知;Nakamura Yoshiki;Nakamura Yoshiki;Yoshiki Nakamura;Yoshiki Nakamura;中村誠希;中村誠希;中村誠希;中村誠希;中村誠希;Yoshiki Nakamura;Yoshiki Nakamura;Yoshiki Nakamura;Yoshiki Nakamura
• 通讯作者: Yoshiki Nakamura

Antimirov's partial derivatives for Kleene allegories

安蒂米洛夫对克林寓言的偏导数

• 发表时间: 2017
• 作者: 辻本真規;酒井明人;松本洋介;中辻知;Nakamura Yoshiki;Nakamura Yoshiki;Yoshiki Nakamura;Yoshiki Nakamura;中村誠希;中村誠希;中村誠希;中村誠希;中村誠希;Yoshiki Nakamura;Yoshiki Nakamura
• 通讯作者: Yoshiki Nakamura