pm4py.objects.petri_net.utils.murata module

pm4py.objects.petri_net.utils.murata.apply_reduction(net: PetriNet, im: Marking, fm: Marking) → Tuple[PetriNet, Marking, Marking]

Apply the Murata reduction to an accepting Petri net, removing structurally redundant (implicit) places.

This implementation follows the (Berthelot) implicit-place check by searching, via ILP, for a place-flow f = a_p * p - Σ a_q * q (a_p >= 1, a_q >= 0) such that:

1. f is a P-invariant (flow): a_p*C(p,t) - Σ a_q*C(q,t) = 0 for all transitions t where C(p,t) = Post(p,t) - Pre(p,t)

2. a_p*Pre(p,t) - Σ a_q*Pre(q,t) <= k for all transitions t with k = a_p*M0(p) - Σ a_q*M0(q), and k >= 0

If such a solution exists, the candidate place is implicit and can be removed without changing behavior.

Parameters:

• net – Petri net

• im – Initial marking

• fm – Final marking

Returns:

• net – Reduced Petri net

• im – Initial marking (unchanged)

• fm – Final marking (unchanged)