Multiset rewriting for the verification of depth-bounded processes with name binding
We combine two of the existing approaches to the study of concurrency by means of multiset rewriting: multiset rewriting with existential quantification (MSR) and constrained multiset rewriting. We obtain nu-MSR, where we rewrite multisets of atomic formulae, in which terms can only be pure names, where some names can be restricted. We consider the subclass of depth-bounded nu-MSR, for which the interdependence of names is bounded. We prove that they are strictly Well Structured Transition Systems, so that coverability, termination and boundedness are all decidable for depth-bounded nu-MSR. This allows us to obtain new verification results for several formalisms with name binding that can be encoded within nu-MSR, namely polyadic nu-PN (Petri nets with tuples of names as tokens), the pi-calculus, MSR or Mobile Ambients. (C) 2012 Elsevier Inc. All rights reserved.
multiset rewriting verification decidability petri nets depth-bounded ness wsts process algebra