Active learning for sound negotiations

Speaker: Anca Muscholl, LaBRI
Tuesday 18 January 2022, 11:00, (online)

Abstract: We present an active learning algorithm for sound deterministic negotiations. Sound deterministic negotiations are graph-based models of distributed systems, a kind of Petri nets or Zielonka automata with additional structure. We show that sound deterministic negotiations can be minimised. Our learning algorithm has 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.

Joint work with Igor Walukiewicz. Extended abstract: here