Logical analysis and optimization of distributed systems

分布式系统的逻辑分析与优化

• 批准号: 06044112
• 负责人: IBARAKI Toshihide
• 金额: $ 7.55万
• 依托单位: KYOTO UNIVERSITY
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for international Scientific Research
• 财政年份: 1994
• 资助国家: 日本
• 起止时间: 1994 至 1996
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-06044112/
• 关键词: distributed systems; logical analysis; optimization; Boolean function; coterie; プール関数

In these three years of joint research, we could invite Professor Tiko Kameda (Simon Fraser University), Professor Endre Boros (Rutgers University), Professor Thomas Eiter (Wien Institute of Technology), Professor Jan C.Bioch (Erasmus University), Professor Alexander Kogan (Rutgers University), Professor Alexander Karzanov (Russian Academy of Sciences) to Kyoto University. Also Toshihide Ibaraki visited Simon Fraser University, Rutgers University and Wien Institute of Technology. As a result of this series of joint research, we could publish several papers in professional journals and international conferences on the following topics.(1) Theory of distributed systems, particularly mutual exclusion based on coteries. We have clarified the relationship between coteries and self-dual positive Boolean functions.(2) Identification and dualization of positive functions. As a key question in the research of (1), this problem has been studied by various groups, including us. Some partial results were obtained.(3) Partially defined Boolean functions and knowledge ackquisition. The above research has been extended to this new interesting field of data analysis.(4) Minimum cuts in graphs and theory of network flows. To exploit the results of graph and network theory, we studied algorithmic aspects of these problems, and proposed new efficient algorithms.

在这三年的联合研究中，我们可以邀请Tiko Kameda教授（西蒙弗雷泽大学）、Endre Boros教授（罗格斯大学）、Thomas Eiter教授（维也纳理工学院）、Jan C.Bioch教授（伊拉斯姆斯大学）、Alexander教授Kogan（罗格斯大学）、Alexander Karzanov 教授（俄罗斯科学院）到京都大学。茨城俊英还访问了西蒙弗雷泽大学、罗格斯大学和维也纳理工大学。通过这一系列的联合研究，我们在专业期刊和国际会议上发表了多篇论文，主题如下：（1）分布式系统理论，特别是基于群的互斥。阐明了群与自对偶正布尔函数的关系。(2)正函数的辨识与对偶化。作为(1)研究的关键问题，这个问题已经被包括我们在内的各个团体进行了研究。得到了部分结果。(3)布尔函数的部分定义及知识获取。上述研究已扩展到数据分析这个新的有趣领域。(4)图和网络流理论的最小割。为了利用图和网络理论的成果，我们研究了这些问题的算法方面，并提出了新的有效算法。

项目成果

E.Boros: "Polynomial time recognition of 2-monotonic positive Boolean functions given by an oracle" SIAM J.on Computing. (掲載予定).

E.Boros：“预言机给出的 2-单调正布尔函数的多项式时间识别”SIAM J.on 计算（待出版）。

K.Makino,T.Ibaraki: "The maximum latency and identification of positive Boolean functions" SIAM J.on Computing. (掲載予定).

K. Makino、T. Ibaraki：“正布尔函数的最大延迟和识别”SIAM J.on 计算（待出版）。

E.Boros, P.L.Hammer, T.Ibaraki, K.Kawakami: "Polynomial time recognition of 2-monotonic positive Boolean functions given by an oracle" SIAM J.on Computing. (to appear).

E.Boros、P.L.Hammer、T.Ibaraki、K.Kawakami：“预言机给出的 2 单调正布尔函数的多项式时间识别”SIAM J.on 计算。

E.Boros,P.L.Hammer,T.Ibaraki,K.Kawakami: "Polynomial time recognition of 2-monotonic positive Boolean functions given by an oracle" SIAM J.on Computing. (掲載予定).

E.Boros、P.L.Hammer、T.Ibaraki、K.Kawakami：“预言机给出的 2-单调正布尔函数的多项式时间识别”SIAM J.on 计算（即将出版）。

E.Boros: "Boolean analysis of incomplete examples" Algorithm Theory,Lecture Notes in Computer Science. 1097. 440-451 (1996)

E.Boros：“不完整示例的布尔分析”算法理论，计算机科学讲义。