観測モードに依らないシステム解析アルゴリズムの開発：ファイバー圏によるアプローチ

开发独立于观察模式的系统分析算法：纤维球方法

基本信息

批准号：
21J13334
负责人：
小森田祐一
金额：
$ 0.64万
依托单位：
The Graduate University for Advanced Studies
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2021
资助国家：
日本
起止时间：
2021-04-28 至 2023-03-31
项目状态：
已结题

项目摘要

本研究では、状態遷移システムの分析に関し、同値関係、距離などの観測モードに依らない形での理論の定式化・実証コードの実装を目指している。令和4年度は、主に以下の2つの、すでに存在するアルゴリズムを圏論的に解釈し、一般化することを目指して研究を行った。1つ目は、無限ゲームに基づいたアルゴリズムである。これは主に、[Tang & van Breugel, CONCUR 2016]、[Bacci+, CONCUR 2019]などの論文で扱われているものである。本研究においてはすでに、LICS2019論文ジャーナル版において、状態遷移システムの無限ゲームによる分析を取り扱っているが、先に述べた論文で扱われているゲームはそれとは大きく異なる性質を持つ。特に、LICS2019論文ジャーナル版におけるゲームは常に決定論的であるが、先に述べた論文で扱われるものは、確率的システムについては確率的ゲームになるのである。本研究ではこの違いを圏論的に、「関手の持ち上げの表式の違い」として定式化した。特に先に述べた論文で扱うものは Wasserstein Lifting と呼ばれるものでとらえられ、これを用いてアルゴリズムの一般化ができる可能性がある。2つ目は、partition refinementと呼ばれる一群のアルゴリズムである。これは観測モードとしては同値関係を扱うものであり、距離などの他の観測モードでは類似のアルゴリズムは提案されていない。そこで、このアルゴリズムを抽象的・圏論的に分析することにより、逆に、観測モードとしての同値関係の持つどのような性質が、このアルゴリズムを成立させているのかの分析を試み、一定の成果を得た。どちらについても、京都大学数理解析研究所の計算機科学チームの複数の研究者と共同研究を行った。現在論文化に向けて研究を進めている。

在这项研究中，我们的目标是制定一种理论并实施一种经验代码来分析状态转移系统，该系统不依赖于等价关系和距离等观察模式。 2020年，我们主要进行研究，目的是通过使用范畴论解释以下两种现有算法来概括它们。第一个是基于无限博弈的算法。这主要在 [Tang & van Breugel, CONCUR 2016] 和 [Bacci+, CONCUR 2019] 等论文中得到解决。在这项研究中，我们已经在 LICS 2019 论文期刊版本中使用无限博弈进行了状态转换系统的分析，但上述论文中处理的博弈具有显着不同的特征。特别是，LICS 2019 论文期刊版本中的博弈始终是确定性的，但上述论文中处理的博弈是随机系统的随机博弈。在这项研究中，我们用范畴论将这种差异表述为“函子提升表达的差异”。特别是，前面提到的论文涉及的是 Wasserstein Lifting，并且可以使用它来推广算法。第二个是称为分区细化的一系列算法。这是一种处理等价关系的观察模式，对于距离等其他观察模式还没有提出类似的算法。因此，我们通过从抽象和范畴论的角度来分析该算法，试图分析等价关系作为一种观察模式具有什么样的性质，使得该算法能够发挥作用，并取得了一定的成果。对于这两个问题，我们与京都大学数学科学研究所计算机科学团队的多名研究人员进行了联合研究。我们目前正在进行研究以期发表。

项目成果

期刊论文数量（12）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Codensity Games for Bisimilarity

相似性的代码密度游戏

DOI：
10.1007/s00354-022-00186-y
发表时间：
2022
期刊：
New Generation Computing
影响因子：
2.6
作者：
Komorida Yuichi;Katsumata Shin-ya;Hu Nick;Klin Bartek;Humeau Samuel;Eberhart Clovis;Hasuo Ichiro
通讯作者：
Hasuo Ichiro

Radboud University, Nijmegen(オランダ)

奈梅亨拉德堡德大学（荷兰）