paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Active learning for sound negotiations✱

面向可靠确定型协商的主动学习
LICS Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science2022匹配度 2/10 · 论文研究可靠确定型协商的主动学习算法，属于形式化方法与自动机学习，未涉及 LLM/Agent、静态分析、浮点程序分析或贝叶斯程序分析，与用户研究画像的核心交叉方向关联很弱。引用 1 inbox
Anca Muscholl, Igor Walukiewicz
逻辑与自动机并发、并行与内存模型
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话：为可靠确定型协商提出两种主动学习算法，利用其结构实现最小化，查询复杂度与协商规模多项式相关。

论文研究可靠确定型协商（sound deterministic negotiations）的主动学习问题。这类模型可视为带额外结构的 Petri 网或 Zielonka 自动机，用于描述分布式系统。作者首先证明该额外结构使得此类协商可以被最小化。在此基础上，提出两种主动学习算法，区别在于所使用的成员查询类型。两种算法的复杂度均与 Angluin 的 L* 算法类似，查询数量是协商规模的多项式，而非其配置数的多项式。

问题
如何对可靠确定型协商这一分布式系统模型进行主动学习，并避免查询量随配置数爆炸。
方法
利用协商的额外结构进行最小化，并设计两种采用不同成员查询的主动学习算法。
评估
通过复杂度分析表明，两种算法的查询数量均为协商规模的多项式，与 Angluin L* 算法类似。
原文摘要（Abstract）

We present two active learning algorithms for sound deterministic negotiations. Sound deterministic negotiations are models of distributed systems, a kind of Petri nets or Zielonka automata with additional structure. We show that this additional structure allows to minimize such negotiations. The two active learning algorithms differ in the type of membership queries they use. Both have similar complexity to Angluin’s L* algorithm, in particular, the number of queries is polynomial in the size of the negotiation, and not in the number of configurations.

链接与引用

DOI 原文 · arXiv · PDF（开放获取） · DBLP

BibTeX 
@inproceedings{MuschollW22,
  title = {Active learning for sound negotiations✱},
  author = {Anca Muscholl and Igor Walukiewicz},
  booktitle = {LICS},
  year = {2022},
  doi = {10.1145/3531130.3533342}
}