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 についての結果で残された表現力の分離と標準形に関する二つの未解決問題を肯定的に解決した。

研究人员今年的主要研究结果是在计算机科学领域的最高国际计算机科学会议上接受了论文。这项工作既关联有限的模型理论和描述性计算理论，并定义了称为单独的分支机构的blum-shub-sale机器的替代方法，称为单独的分支blum-shub-sale-sale机器（作为S-BSS机器的缩写为S-BSS机器），从而使逻辑表征（通过概率与概率（一阶）逻辑）从该语言中的fagin and pynemins ne-noDneDneNders中确定。在这里，BSS机器将实际数字作为输入，可以被视为一台图灵机，可以在一步中对实数执行算术操作。与BSS机器相比，S-BSS计算机计算实数的方法更有限。共享者在国际计算机科学逻辑会议（CSL）上发表的论文将结果从LICS论文扩展到了Complectity Class Ptime的结果。此外，我们与主持人研究人员进行了准备研究，以在命题逻辑的设置中检查这些结果。此外，我写了一篇有关模态逻辑研究的论文，该论文是去年推出的，这对于对执行痕迹的超构造进行了建模非常有用。 “关于二阶布尔逻辑的Horn和Krom片段的复杂性”提供了表征计算复杂性时的结果，当时二阶QBF仅限于角节点和相关片段。主持人的研究人员和共享者积极解决了两个未解决的问题，这些问题涉及寄宿研究者直觉主义好奇逻辑结果中留下的表达能力和标准形式的分离。

项目成果

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

赫尔辛基大学（芬兰）

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 的主页