Modular Stochastic Rewritable Petri Nets

Lorenzo Capra · 2025

Read Modular Stochastic Rewritable Petri Nets by Lorenzo Capra (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-09217.txt.

Introduction

Lorenzo Capra builds Petri nets that can rewrite themselves, then makes them roll dice. Petri nets model concurrent systems well but strain against systems that adapt. His rewritable nets, formalized in the Maude language on rewriting logic, let the net's own structure change under rules.

A modular layer composes big nets from pieces with algebraic operators, using composite labels to mark symmetries that survive the rewrites. The new step adds stochastic timing to the formalism. From the quotient graph of a rewritable net, the paper gives an automatic route to a lumped continuous-time Markov chain, the compressed model analysts actually simulate. The author presents the chain as the bridge from adaptive net models to quantitative performance answers.

Catalog record

CREATORLorenzo Capra
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE21 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-09217

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Modular Stochastic Rewritable Petri Nets Lorenzo Capra Abstract Petri Nets (PN) are widely used for modeling concurrent and distributed systems, but face challenges in modeling adaptive systems. To address this, we have formalized ’rewritable’ PT nets (RwPT) using Maude , a declarative language with sound rewriting logic semantics. Recently, we introduced a modular approach that utilizes algebraic operators to construct large RwPT models. This technique employs composite node labeling to outline symmetries in hierarchical organization, preserved through net rewrites. Once stochastic parameters are added to the formalism, we present an automated process to derive a lumped CTMC from the quotient graph generated by an RwPT. 1 Introduction Traditional formalisms such as Petri Nets, Automata, and Process Algebra do not make it easy for designers to define dynamic system changes. Several extensions inspired by the \pi -calculus and the Nets-within-Nets paradigm have been proposed, but they often lack suitable analysis techniques. Rewritable PT nets (RwPT) [ 7 ] is versatile formalism for analyzing adaptive distributed systems. RwPT is specified using the declarative language Maude , which adopts Rewriting Logic to offer both operational and mathematical semantics, creating a scalable model for self-adapting PT nets. Unlike similar approaches ( [ 3 , 12 ] ), the RwPT formalism provides data abstraction, is concise and efficient, and avoids the limitations posed by ’pushout’ in Graph Transformation Systems. RwPT is an extension of GTS. Considering graph isomorphism (GI) when identifying equivalent states within the model dynamics is crucial to scaling up the model complexity. Recent work has shown that GI is quasi-polynomial [ 2 ] . Graph Canonization (GC) involves finding a representative such that for any two graphs G and G^{\prime} , G\simeq G^{\prime}\Leftrightarrow can(G)=can(G^{\prime}) . We developed a general canonization technique [ 6 ] for use with RwPT, integrated into Maude . This technique works well for irregular models, but it is less effective for more realistic models. In [ 8 ] , we presented a technique for constructing comprehensive RwPT models using algebraic operators. The strategy is simple: leverage the modular characteristics of the models during analysis. By employing composite node labelling, we capture symmetries and sustain the hierarchical organization through net rewrites. A benchmark case study illustrates the effectiveness of our method. In this paper, we demonstrate a procedure to derive a lumped Continuous-Time Markov Chain (CTMC) from the quotient graph formed by an RwPT model, after introducing stochastic parameters into the framework. The potential of Maude as functional logic programming framework was discussed in [ 11 ] and recently in https://logicprogramming.org/2023/02/extensions-of-logic-programming-in-maude/ . Although we do not consider free variables in terms, our work can be seen as an example of symbolic reachability in which we use term rewriting through pattern matching (modulo normalization) instead of narrowing through unification. The use of narrowing to get a quotient state-transition system deserves further study. 2 (Stochastic) PT nets, Maude , and demonstrative example This section provides a concise overview of the (stochastic) PT formalism and emphasizes the key aspects of the Maude framework. For exhaustive information, we direct readers to the reference papers. A multiset (or bag ) b on a set D is a map b:D\rightarrow\mathbb{N} , where b(d) is the multiplicity of d in b . We denote by Bag[D] the set of multisets on D . Standard relational and arithmetic operations can be applied to multisets on a component-by-component basis. A stochastic PT (or SPN) net [ 13 , 9 ] is a 6-tuple (P,T,I,O,H,\lambda) , where: P , T are finite, non-empty, disjoint sets holding the net’s nodes (places and transitions, respectively); I,O,H: T\ \rightarrow Bag[P] represent the transitions’ input , output , and inhibitor incidence matrices, respectively; \lambda:T\ \rightarrow\mathbb{R}^{+} assigns each transition a negative exponential firing rate. A PT net marking (or state) is a multiset m\in Bag[P] . The PT net dynamics is defined by the firing rule : t\in T is enabled in m if I(t)\leq m and \forall p\in P:H(t)(p)=0\vee H(t)(p)>m(p) . If t is enabled in m it may fire, leading to marking m^{\prime}=m+O(t)-I(t) . We denote this: m[t\rangle m^{\prime} . A PT- system is a pair (N,m_{0}) , where N is a PT net and m_{0} is a marking of N . The interleaving semantics of (N,m_{0}) is specified by the reachability graph (RG), an edge-labelled, directed graph (V,E) whose nodes are markings. It is defined inductively: m_{0}\in V ; if m\in V and m[t\rangle m^{\prime} then m^{\prime}\in V , m\xrightarrow{t}m^{\prime}\in E . The timed semantics of a stochastic PT system is a CTMC isomorphic to the RG: For any two m_{i},m_{j}\in V , the transition rate from m_{i} to m_{j} is r_{i,j}:=\sum_{t:m_{i}[t\rangle m_{j}}\lambda(t) . Maude Maude [ 10 ] is an expressive, purely declarative language characterized by a rewriting logic semantics [ 5 ] . Statements consist of equations and rules . Each side of a rule or equation represents terms of a specific kind that might include variables. Rules and equations have intuitive rewriting semantics, where instances of the left-hand side are substituted by corresponding instances of the right-hand side. The expressivity of Maude is realized through the use of matching modulo operator equational attributes, sub-typing, partiality, generic types, and reflection. A functional module comprises only equations and works as a functional program defining operations through equations, utilized as simplification rules. It details an equational theory within membership equational logic [ 4 ] : Formally, a tuple (\Sigma,E\cup A) , with \Sigma representing the signature, which includes the declaration of all sorts, subsorts, kinds 1 1 1 implicit equivalence classes defined by connected components of sorts (as per subsort partial order). Terms in a kind without a specific sort are error terms. , and operators; E being the set of equations and membership axioms; and A as the set of operator equational attributes (e.g., assoc ). The model of (\Sigma,E\cup A) is the initial algebra T_{\Sigma/E\cup A} , which mathematically corresponds to the quotient of the ground-term algebra T_{\Sigma} . Provided that E and A satisfy nonrestrictive conditions, the final (or canonical ) values of ground terms form an algebra isomorphic to the initial algebra, that is, the mathematical and operational semantics coincide. A Maude system module includes rewrite rules and, possibly, equations. Rules illustrate local transitions in a concurrent system. Specifically, a system module describes a generalized rewrite theory [ 5 ] \mathcal{R}=(\Sigma,E\cup A,\phi,R) , where (\Sigma,E\cup A) constitutes a membership equation theory; \phi identifies the frozen arguments for each operator in \Sigma ; and R contains a set of rewrite rules. A rewrite theory models a concurrent system: (\Sigma,E\cup A) establishes the algebraic structure of the states, while R and \phi define the concurrent transitions of the system. The initial model of \mathcal{R} assigns to each kind k a labeled transition system (TS) where the states are the elements of T_{\Sigma/E\cup A,k} , and transitions occur as [t]\overset{[\alpha]}{\rightarrow}[t^{\prime}] , with [\alpha] representing equivalent rewrites. The property of coherence guarantees that a strategy that reduces terms to their canonical forms before applying the rules is sound and complete. A Maude system module is an executable specification of distributed systems. Given finite reachability, it enables the verification of invariant properties and the discovery of counterexamples. Running example: fault-tolerant production line

Read the complete text