Zeroness of weighted basic parallel processes and other finitely generated classes of series

Speaker(s)

Lorenzo Clemente

Affiliation

University of Warsaw

Date

Dec. 13, 2023, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

We consider a weighted model of computation generalising weighted finite automata over fields, namely weighted basic parallel processes (WBPP). The underlying unweighted BPP model, popular in process algebra, was introduced by Christensen in his PhD thesis from 1993 and can be seen as the communication-free variant of Petri nets where each transition consumes exactly one token. BPP are sometimes called commutative context-free grammars since they also arise from grammars by allowing the nonterminals to commute with each other. From the language semantics point of view, concatenation of languages is replaced by their shuffle. We show that equivalence of WBPP is decidable, with elementary complexity (2-EXPSPACE). This should be contrasted with undecidability of BPP language equivalence and undecidability of equivalence for weighted Petri nets. The take-home message is that, once we enter a quantitative semantics, shuffle product starts to be well-behaved. The equivalence algorithm constructs a chain of polynomial ideals and is based on Hilbert's finite basis theorem. In the case of a singleton input alphabet, a result of Novikov and Yakovenko from 1999 on repeated application of a derivation yields a 2-EXP length bound. We generalise their analysis to the more general case of arbitrary finite alphabets, obtaining the same bound for repeated application of finitely many noncommuting derivations. It is remarkable that such a chain of polynomial ideals has elementary length. On the way we remark that the class of WBPP series coincides with the class of finitely generated series over the series ring with shuffle product. We then play a game where different ring products are proposed and the audience has to guess the corresponding class of finitely generated series.

---