Model Theory and proof theory of probabilistic logic in propositional and modal team semantics

命题和模态团队语义中概率逻辑的模型理论和证明理论

• 批准号: 19F19797
• 负责人: 佐野 勝彦
• 金额: $ 1.47万
• 依托单位: Hokkaido University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2019
• 资助国家: 日本
• 起止时间: 2019-11-08 至 2021-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19F19797/
• 关键词: 有限モデル理論; 計算機科学における論理; 様相モデル理論; 論理の計算量; 実数計算の記述計算量; ハイパー性質のための論理; 直観主義 inquisitive logic の定義可能性; Team Semantics; BSS Machines; Modal Logic; Hyperproperties

研究分担者の、本年度の主要な研究成果は計算機科学のトップ国際会議である Logic in Computer Science に論文がアクセプトされたことである。この研究は有限モデル理論と記述計算量という計算量理論の両方に関するもので、Separate Branching Blum-Shub-Smale 機械 (S-BSS 機械と略記)という Blum-Shub-Smale 機械の代替を定義し、このS-BSS機械を使って非決定的かつ多項式時間で決定できる言語のFaginに由来する論理的な特徴付け（確率独立（一階述語）論理による）を与えた。ここでBSS機械は実数を入力としてとり、１ステップで実数上の算術的演算を行うことができるチューリング機械とみなせる。S-BSS機械はBSS機械よりも実数を計算する仕方がより制限されている。分担者が国際会議CSL (Computer Science Logic)で発表した論文は、LICS論文での結果を、計算量クラスPTIMEに関する結果へと拡張した。さらにこういった結果を命題論理の設定で考察する準備的研究を受入研究者と行った。さらに、昨年度に着手した、実行トレースについてのhyperpropertyをモデルするのに役立つ、チーム意味論をもつ様相論理の研究については論文執筆を行った。分担者の論文　``On the Complexity of Horn and Krom Fragments of Second-Order Boolean Logic''では、二階QBFがホーン節やそれに関連する断片に制限された場合の計算量の特徴付けの結果を得た。受入研究者と分担者は受入研究者の直観主義 inquisitive logic についての結果で残された表現力の分離と標準形に関する二つの未解決問題を肯定的に解決した。

The main research results of this year are presented at the International Conference on Computer Science, Logic in Computer Science. This research includes finite element theory, description of computational quantities, formulation of computational quantity theory, definition of Blum-Shub-Smale mechanical substitution, definition of S-BSS mechanical substitution of non-deterministic polynomial time, determination of speech Fagin logic, and characterization of speech logic (accuracy independence (first-order statement) logic). The BSS machine is a machine that works on arithmetic. S-BSS mechanical and BSS mechanical calculation of the number of official restrictions Contributors to the International Conference CSL (Computer Science Logic) presented papers, LICS papers, results, calculations and results related to PTIME. The results of this study are set out in the following paragraphs: In the past year, we have started to carry out the research on hyperproperty, meaning theory and phase logic, and write papers. On the Complexity of Horn and Krom Fragments of Second-Order Boolean Logic The researcher and the participant are the direct inquisitive logic of the researcher and the result is the separation of the performance and the standard form. The unresolved problem is definitely solved.

项目成果

Complexity of probabilistic inclusion logic and additive real arithmetics

概率包含逻辑和加法实数运算的复杂性

• 发表时间: 2020
• 期刊: Workshop on Logics of Dependence and Independence (LoDE 2020V)
• 作者: Miika Hannula;Juha Kontinen;Jan Van den Bussche;and Jonni Virtema;Miika Hannula and Jonni Virtema
• 通讯作者: Miika Hannula and Jonni Virtema

ヘルシンキ大学(フィンランド)

赫尔辛基大学（芬兰）

ザールランド大学(ドイツ)

萨尔大学（德国）

Saarland University(ドイツ)

萨尔大学（德国）

Homepage of Jonni Virtema

Jonni Virtema 的主页