Zeroness of weighted basic parallel processes

[see the attached PDF for the same abstract + references] We study weighted basic parallel processes (WBPP), a nonlinear recursive generalisation of Schutzenberger's weighted finite automata inspired from process algebra and Petri net theory. Formally, they can be defined as communication free Petri nets, which means that each transition can remove a token from exactly one place; tokens can be added without restrictions. Each transition is labelled with a weight from a field, say the rationals $\mathbb Q$. The weight of a run is the product of the weights of the transitions occurring in the run; the weight of an input word is the sum of the weights of the runs accepting the word. (Alternatively, a WBPP can be seen as a weighted context-free grammar where the nonterminal symbols commute with each other.) Like BPP recognise languages $\subseteq \Sigma^ $, WBPP recognise series $\Sigma^ \to \mathbb Q$. The WBPP-recognisable series form an interesting class of series generalising the rational series (those recognised by weighted finite automata). For example, 1) they are effectively closed under many operations such as scalar product, sum, shuffle, shuffle-inverse, and derivation; 2) a version of the implicit functions theorem applies to them, which provides a very general way to construct WBPP series from previous ones; 3) the commutative subclass of WBPP series (i. e. , those for which the output weight does not depend on the order of the input symbols) corresponds to multivariate constructible differentially finite power series, introduced by Bergeron, Reutenauer, and Sattler in the context of combinatorial enumeration. Our main result is an algorithm of 2EXPSPACE complexity for the WBPP equivalence problem. While (unweighted) BPP language equivalence is undecidable, we can use this algorithm decide multiplicity equivalence of BPP and language equivalence of unambiguous BPP, with the same complexity. Decidability of the latter problems was not known before. The corresponding problems for weighted context-free grammars are open since a long time. The complexity analysis of the equivalence algorithm is based on effective bounds from algebraic geometry. More precisely, we study the length of chains of polynomial ideals constructed by repeated application of finitely many, not necessarily commuting derivations of a multivariate polynomial ring. This is obtained by generalising a result of Novikov and Yakovenko in the case of a single derivation. The fact that we obtain an elementary bound is noteworthy, since generic bounds on ideal chains are only non-primitive recursive in general.

Authors

• Lorenzo Clemente

Keywords

No keywords are indexed for this paper.