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
项目状态：
已结题

项目摘要

研究分担者の、本年度の主要な研究成果は計算機科学のトップ国際会議である 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 についての結果で残された表現力の分離と標準形に関する二つの未解決問題を肯定的に解決した。

两位研究员今年的主要研究成果是论文被计算机科学国际顶级会议Logic in Computer Science接收。这项研究涉及有限模型理论和描述复杂性理论，并定义了 Blum-Shub-Smale 机器的替代方案，称为分离分支 Blum-Shub-Smale 机器（缩写为 S-BSS 机器）。可以使用 S-BSS 机器在多项式时间内非确定性地确定语言的派生逻辑特征（通过随机独立（一阶谓词）逻辑）。这里，BSS机可以看作是一台图灵机，它以实数为输入，可以一步对实数进行算术运算。 S-BSS 机器在计算实数方面比 BSS 机器受到更多限制。共同作者在国际会议 CSL（计算机科学逻辑）上发表的论文将 LICS 论文的结果扩展到有关复杂性类别 PTIME 的结果。此外，我与我的主持研究员进行了初步研究，以在命题逻辑的背景下检验这些结果。此外，我还写了一篇关于去年开始的关于具有团队语义的模态逻辑的研究的论文，这对于对执行跟踪的超属性进行建模非常有用。在合作者的论文《On the Complexity of Horn and Krom Fragments of Second-Order Boolean Logic》中，我们得到了表征二阶QBF仅限于Horn节点和相关片段时的计算复杂度的结果。主持研究员和他的合作者积极解决了主持研究员关于探究逻辑的研究结果留下的关于表达性和标准形式分离的两个未解决的问题。

项目成果

期刊论文数量（17）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

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

赫尔辛基大学（芬兰）

DOI：
发表时间：
期刊：
影响因子：
0
作者：
通讯作者：

Complexity of probabilistic inclusion logic and additive real arithmetics

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

DOI：
发表时间：
2020
期刊：
Workshop on Logics of Dependence and Independence (LoDE 2020V)
影响因子：
0
作者：
Miika Hannula;Juha Kontinen;Jan Van den Bussche;and Jonni Virtema;Miika Hannula and Jonni Virtema
通讯作者：
Miika Hannula and Jonni Virtema

Saarland University(ドイツ)

萨尔大学（德国）

DOI：
发表时间：
期刊：
影响因子：
0
作者：
通讯作者：

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

萨尔大学（德国）

DOI：
发表时间：
期刊：
影响因子：
0
作者：
通讯作者：

Homepage of Jonni Virtema

Jonni Virtema 的主页

DOI：
发表时间：
期刊：
影响因子：
0
作者：
通讯作者：

DOI：
{{ item.doi }}
发表时间：
{{ item.publish_year }}
期刊：
{{ item.journal_name }}
影响因子：
{{ item.factor }}
作者：
{{ item.authors }}
通讯作者：
{{ item.author }}

数据更新时间：{{ journalArticles.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ monograph.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ sciAawards.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ conferencePapers.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ patent.updateTime }}

佐野勝彦其他文献

細菌叢または遺伝子発現情報からバイオフィルムを解析する

从细菌菌群或基因表达信息中分析生物膜

DOI：
发表时间：
2019
期刊：
影响因子：
0
作者：
田堀朱音;佐野勝彦;小川亜希子;矢野真弓;廣部崚馬;寺田聡;Morii T，Kishino T，Shimamori N，Motohashi M，Ohnishi H，Honya K，Aoyagi T，Tajima T，Ichimura S;小川亜希子
通讯作者：
小川亜希子