2013/07/08 by Javier Esparza, Esparza, Javier, Joerg Desel +1 · 1 citation
Computer Science · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO) #cs.FL #cs.LO
paper · pdf · doi:10.48550/arxiv.1307.2145
arxiv created 2013/07/08 · arxiv updated 2013/07/09
We introduce negotiations, a model of concurrency close to Petri nets, with multiparty negotiation as primitive. We study the problems of soundness of negotiations and of, given a negotiation with possibly many steps, computing a summary, i.e., an equivalent one-step negotiation. We provide a complete set of reduction rules for sound, acyclic, weakly deterministic negotiations and show that, for deterministic negotiations, the rules compute the summary in polynomial time.