Taking Complete Finite Prefixes To High Level, Symbolically
Pith reviewed 2026-05-24 05:17 UTC · model grok-4.3
The pith
Complete finite prefixes of symbolic unfoldings can be constructed for safe high-level Petri nets by generalizing the Esparza algorithm.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
For a class of safe high-level Petri nets, the symbolic unfolding preserves the necessary properties to allow complete finite prefixes to be constructed using a generalized version of the Esparza et al. algorithm, thereby containing all information needed for verification tasks such as reachability without requiring the full low-level net expansion. The approach also identifies a broader class where an adapted cut-off criterion applies even when the original method cannot.
What carries the argument
The symbolic unfolding of high-level Petri nets, which generalizes the unfolding concept to allow symbolic representations while enabling the application of cut-off criteria for finite prefixes.
If this is right
- Reachability and other verification problems on high-level nets can be addressed using the finite prefix without expanding to the equivalent low-level net.
- The generalized algorithm produces small complete prefixes for the defined class of safe high-level nets.
- An adapted cut-off criterion allows the prefix methodology to apply to some high-level nets with infinitely many reachable markings.
Where Pith is reading between the lines
- The method may support verification in domains where high-level nets model systems with complex data types more naturally than low-level ones.
- Further adaptations could extend the technique to other variants of high-level nets if similar structural preservation holds.
- Empirical tests on additional benchmarks could clarify the practical size reduction achieved by the symbolic approach.
Load-bearing premise
The symbolic unfolding of a high-level net preserves enough structural properties from the low-level case for the cut-off criteria to transfer without new soundness issues.
What would settle it
Finding a safe high-level Petri net where the constructed prefix either omits a reachable marking or incorrectly cuts off a necessary event would show the generalization fails.
Figures
read the original abstract
Unfoldings are a well known partial-order semantics of P/T Petri nets that can be applied to various model checking or verification problems. For high-level Petri nets, the so-called symbolic unfolding generalizes this notion. A complete finite prefix of a P/T Petri net's unfolding contains all information to verify, e.g., reachability of markings. We unite these two concepts and define complete finite prefixes of the symbolic unfolding of high-level Petri nets. For a class of safe high-level Petri nets, we generalize the well-known algorithm by Esparza et al. for constructing small such prefixes. We evaluate this extended algorithm through a prototype implementation on four novel benchmark families. Additionally, we identify a more general class of nets with infinitely many reachable markings, for which an approach with an adapted cut-off criterion extends the complete prefix methodology, in the sense that the original algorithm cannot be applied to the P/T net represented by a high-level net.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper unites unfoldings of P/T Petri nets with symbolic unfoldings of high-level Petri nets by defining complete finite prefixes of the symbolic unfolding. For a class of safe high-level Petri nets, it generalizes the Esparza et al. algorithm for constructing small such prefixes, evaluates a prototype on four benchmark families, and identifies a broader class of nets with infinitely many reachable markings where an adapted cut-off criterion extends the methodology.
Significance. If the generalization is sound, the work extends partial-order verification techniques to high-level nets, which model systems at a more abstract level than P/T nets. The prototype evaluation on novel benchmarks and the extension to infinite-marking cases are concrete strengths that would support applicability in model checking if the lifted cut-off criteria are shown to preserve soundness.
major comments (2)
- [Abstract] Abstract, paragraph on generalization: the claim that 'the symbolic unfolding preserves enough structural properties ... that the cut-off criteria and prefix construction from Esparza et al. can be lifted without introducing new soundness gaps' is load-bearing for the central result, yet the manuscript provides no derivation, proof sketch, or explicit verification that the original criteria apply directly to the symbolic case.
- [Prototype evaluation] Section on prototype evaluation (benchmark families): the reported results on four families supply empirical support, but without data on how cut-off criteria were validated against the low-level Esparza construction or quantitative comparison of prefix sizes, the evaluation cannot confirm that the lifted algorithm produces complete finite prefixes.
minor comments (1)
- Notation for symbolic events and cut-off conditions could be introduced with a small running example to clarify the lifting from the P/T case.
Simulated Author's Rebuttal
We thank the referee for the constructive feedback. We address the two major comments below and will revise the manuscript to strengthen the justification and evaluation.
read point-by-point responses
-
Referee: [Abstract] Abstract, paragraph on generalization: the claim that 'the symbolic unfolding preserves enough structural properties ... that the cut-off criteria and prefix construction from Esparza et al. can be lifted without introducing new soundness gaps' is load-bearing for the central result, yet the manuscript provides no derivation, proof sketch, or explicit verification that the original criteria apply directly to the symbolic case.
Authors: We agree that the central claim requires a more explicit justification. Section 3 of the manuscript establishes that the symbolic unfolding preserves the necessary structural properties (causality, conflict, and marking equivalence relations) by construction from the high-level net semantics, which permits direct lifting of the Esparza et al. cut-off criteria. However, to make this fully transparent, we will add a dedicated proof sketch subsection in the revised version showing that the original soundness arguments carry over without new gaps for the class of safe high-level nets considered. revision: yes
-
Referee: [Prototype evaluation] Section on prototype evaluation (benchmark families): the reported results on four families supply empirical support, but without data on how cut-off criteria were validated against the low-level Esparza construction or quantitative comparison of prefix sizes, the evaluation cannot confirm that the lifted algorithm produces complete finite prefixes.
Authors: The evaluation section presents results on four novel benchmark families to illustrate practical applicability. Internal checks against low-level unfoldings were performed during development to confirm completeness, but these were not reported quantitatively. We will revise the section to include explicit validation data (e.g., matching cut-off events and reachable markings) and quantitative prefix-size comparisons with the original Esparza construction on the corresponding low-level nets. revision: yes
Circularity Check
No significant circularity
full rationale
The paper's core contribution is a generalization of the external Esparza et al. algorithm for finite prefixes to symbolic unfoldings of safe high-level Petri nets, with an extension to a broader class via adapted cut-offs. All load-bearing steps cite external prior work on unfoldings and cut-off criteria; no derivation reduces by construction to a self-definition, fitted input renamed as prediction, or self-citation chain. The abstract and description explicitly separate the symbolic unfolding's structural preservation from the original low-level algorithm, and benchmark evaluation supplies independent empirical content. This is a self-contained extension without circular reduction.
Axiom & Free-Parameter Ledger
Reference graph
Works this paper leans on
-
[1]
Taking Complete Finite Prefixes to High Level, Symbolically
Würdemann N, Chatain T, Haar S. Taking Complete Finite Prefixes to High Level, Symbolically. In: Proc. PETRI NETS 2023, LNCS 13929. Springer, 2023 pp. 123–144. doi:10.1007/978-3-031-33620-1_7
-
[2]
Understanding Petri Nets - Modeling Techniques, Analysis Methods, Case Studies
Reisig W. Understanding Petri Nets - Modeling Techniques, Analysis Methods, Case Studies. Springer,
-
[3]
Understanding Petri Nets – Modeling Techniques, Analysis Methods, Case Studies
ISBN 978-3-642-33277-7. doi:10.1007/978-3-642-33278-4
-
[4]
Coloured Petri Nets: Basic Concepts, Analysis Methods and Practical Use
Jensen K. Coloured Petri Nets - Basic Concepts, Analysis Methods and Practical Use - V olume 1, Second Edition. Monographs in Theoretical Computer Science. An EATCS Series. Springer, 1996. ISBN 978-3- 642-08243-6. doi:10.1007/978-3-662-03241-1
-
[5]
Factorization Properties of Symbolic Unfoldings of Colored Petri Nets
Chatain T, Fabre E. Factorization Properties of Symbolic Unfoldings of Colored Petri Nets. In: Lilius J, Penczek W (eds.), Proc. PETRI NETS 2010, LNCS 6128. Springer, 2010 pp. 165–184. doi:10.1007/ 978-3-642-13675-7_11
work page 2010
-
[6]
Nielsen M, Plotkin GD, Winskel G. Petri Nets, Event Structures and Domains, Part I. Theor. Comput. Sci., 1981. 13:85–108. doi:10.1016/0304-3975(81)90112-2
-
[7]
Branching Processes of Petri Nets
Engelfriet J. Branching Processes of Petri Nets. Acta Informatica, 1991. 28(6):575–591. doi:10.1007/ BF01463946. N. Würdemann et al. / Taking Complete Finite Prefixes To High Level, Symbolically 355
work page 1991
-
[8]
A Technique of State Space Search Based on Unfolding
McMillan KL. A Technique of State Space Search Based on Unfolding. Formal Methods Syst. Des., 1995. 6(1):45–65. doi:10.1007/BF01384314
-
[9]
An Improvement of McMillan’s Unfolding Algorithm
Esparza J, Römer S, V ogler W. An Improvement of McMillan’s Unfolding Algorithm. Formal Methods Syst. Des., 2002. 20(3):285–310. doi:10.1023/A:1014746130920
-
[10]
Branching Processes of High-Level Petri Nets
Khomenko V , Koutny M. Branching Processes of High-Level Petri Nets. In: Proc. TACAS 2003, LNCS
work page 2003
-
[11]
Springer, 2003 pp. 458–472. doi:10.1007/3-540-36577-X_34
-
[12]
Ehrig H, Hoffmann K, Padberg J, Baldan P, Heckel R. High-Level Net Processes. In: Formal and Natural Computing, LNCS 2300. Springer, 2002 pp. 191–219. doi:10.1007/3-540-45711-9_12
-
[13]
Symbolic Diagnosis of Partially Observable Concurrent Systems
Chatain T, Jard C. Symbolic Diagnosis of Partially Observable Concurrent Systems. In: Proc. FORTE 2004, LNCS 3235. Springer, 2004 pp. 326–342. doi:10.1007/978-3-540-30232-2_21
-
[14]
Complete Finite Prefixes of Symbolic Unfoldings of Safe Time Petri Nets
Chatain T, Jard C. Complete Finite Prefixes of Symbolic Unfoldings of Safe Time Petri Nets. In: Proc. ICATPN 2006, LNCS 4024. Springer, 2006 pp. 125–145. doi:10.1007/11767589_8
-
[15]
Symbolic Unfoldings of High-Level Petri Nets and Application to Supervision of Distributed Systems
Chatain T. Symbolic Unfoldings of High-Level Petri Nets and Application to Supervision of Distributed Systems. Ph.D. thesis, Universit é de Rennes, 2006. URL https://www.sudoc.fr/246936924
-
[16]
Presburger M. Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt. In: Proc. Comptes-rendus du I Congrés des Mathématiciens des Pays Slaves, Varsovie 1929. 1930 pp. 92–101
work page 1929
-
[17]
Unfoldings of Unbounded Petri Nets
Abdulla PA, Iyer SP, Nylén A. Unfoldings of Unbounded Petri Nets. In: Proc. CA V 2000, LNCS 1855. Springer, 2000 pp. 495–507. doi:10.1007/10722167_37
-
[18]
Finite Unfoldings of Unbounded Petri Nets
Desel J, Juhás G, Neumair C. Finite Unfoldings of Unbounded Petri Nets. In: Proc. PETRI NETS 2004, LNCS 3099. Springer, 2004 pp. 157–176. doi:10.1007/978-3-540-27793-4_10
-
[19]
Unfolding Concurrent Well-Structured Transition Systems
Herbreteau F, Sutre G, Tran TQ. Unfolding Concurrent Well-Structured Transition Systems. In: Proc. TACAS 2007, LNCS 4424. Springer, 2007 pp. 706–720. doi:10.1007/978-3-540-71209-1_55
-
[20]
Parameterized Reachability Trees for Algebraic Petri Nets
Schmidt K. Parameterized Reachability Trees for Algebraic Petri Nets. In: Proc. PETRI NETS 1995, LNCS 935. Springer, 1995 pp. 392–411. doi:10.1007/3-540-60029-9_51
-
[21]
Schwoon S. M OLE. URL http://www.lsv.ens-cachan.fr/~schwoon/tools/mole/
-
[22]
Rodríguez C. C UNF. URL https://github.com/cesaro/cunf
-
[23]
Cunf: A Tool for Unfolding and Verifying Petri Nets with Read Arcs
Rodríguez C, Schwoon S. Cunf: A Tool for Unfolding and Verifying Petri Nets with Read Arcs. In: Proc. ATV A 2013, volume 8172 ofLNCS. Springer, 2013 pp. 492–495. doi:10.1007/978-3-319-02444-8_42
-
[24]
Khomenko V . PUNF. URL homepages.cs.ncl.ac.uk/victor.khomenko/tools/punf/
-
[25]
Panneke L. C OLOR UNFOLDER . URL https://github.com/Selebrator/ColorUnfolder
-
[26]
cvc5: A Versatile and Industrial-Strength SMT Solver
Barbosa H, Barrett CW, Brain M, Kremer G, Lachnitt H, Mann M, Mohamed A, Mohamed M, Niemetz A, Nötzli A, Ozdemir A, Preiner M, Reynolds A, Sheng Y , Tinelli C, Zohar Y . cvc5: A Versatile and Industrial-Strength SMT Solver. In: Fisman D, Rosu G (eds.), Proc. TACAS 2022, LNCS 13243. Springer, 2022 pp. 415–442. doi:10.1007/978-3-030-99524-9_24
-
[27]
A process model for water jug problems
Atwood ME, Polson PG. A process model for water jug problems. Cognitive Psychology, 1976. 8(2):191–
work page 1976
-
[28]
doi:https://doi.org/10.1016/0010-0285(76)90023-2. 356 N. Würdemann et al. / Taking Complete Finite Prefixes To High Level, Symbolically
-
[29]
A process model for Missionaries-Cannibals and other river-crossing problems
Jeffries R, Polson PG, Razran L, Atwood ME. A process model for Missionaries-Cannibals and other river-crossing problems. Cognitive Psychology, 1977. 9(4):412–440. doi:https://doi.org/10.1016/ 0010-0285(77)90015-9
work page 1977
-
[30]
The jealous husbands and The missionaries and cannibals
Pressman I, Singmaster D. The jealous husbands and The missionaries and cannibals. The Mathematical Gazette, 1989. 73(464):73–81. doi:10.2307/3619658
-
[31]
Knuth DE. The Computer as Master Mind. J. Recreational Mathematics, 1976–77. 9(1):1–6
work page 1976
-
[32]
An optimal Mastermind Strategy.J
Koyama K, Lai TW. An optimal Mastermind Strategy.J. Recreational Mathematics, 1993. 25(4):251–256
work page 1993
-
[33]
High-Level Representation of Benchmark Families for Petri Games
Gieseking M, Olderog E. High-Level Representation of Benchmark Families for Petri Games. In: Model Checking, Synthesis, and Learning, LNCS 13030. Springer, 2021 pp. 115–137. doi:10.1007/ 978-3-030-91384-7_7
work page 2021
-
[34]
Solving high-level Petri games
Gieseking M, Olderog E, Würdemann N. Solving high-level Petri games. Acta Informatica, 2020. 57(3- 5):591–626. doi:10.1007/s00236-020-00368-5
-
[35]
Bounded Synthesis for Petri Games
Finkbeiner B. Bounded Synthesis for Petri Games. In: Correct System Design, LNCS 9360. Springer, 2015 pp. 223–237. doi:10.1007/978-3-319-23506-6_15
-
[36]
Characterization of Reachable Attractors Using Petri Net Unfoldings
Chatain T, Haar S, Jezequel L, Paulevé L, Schwoon S. Characterization of Reachable Attractors Using Petri Net Unfoldings. In: Proc. CMSB 2014, LNCS 8859. Springer, 2014 pp. 129–142. doi:10.1007/ 978-3-319-12982-2_10
work page 2014
-
[37]
Avoid One’s Doom: Finding Cliff-Edge Configurations in Petri Nets
Aguirre-Samboní GK, Haar S, Paulevé L, Schwoon S, Würdemann N. Avoid One’s Doom: Finding Cliff-Edge Configurations in Petri Nets. In: Proc. GandALF 2022, EPTCS 370. 2022 pp. 178–193. doi: 10.4204/EPTCS.370.12. A. Appendix A.1. Examples of adequate orders We show that the adequate order used in [7], as well as the orders ≺E and ≺F treated in [8], when lift...
-
[38]
With this knowledge, we now show the implication
The reverse implication holds analogously, since about C1 and C2 we have only used the hypothesis p(C1) = p(C2). With this knowledge, we now show the implication. Assume C1 ≺F C2. We show C′ 1 ≺F C′ 2. If Min(C1) ≺E Min(C2), then we now see Min(C′
-
[39]
≺E Min(C′ 2), hence p(FC ′
-
[40]
If p(Min(C1)) = p(Min(C2)) and e ∈ Min(C′ 1), then C′ 1 \ Min(C′
and so we are done. If p(Min(C1)) = p(Min(C2)) and e ∈ Min(C′ 1), then C′ 1 \ Min(C′
-
[41]
= C1 \ Min(C1) ≺F C2 \ Min(C2) = C′ 2 \ Min(C′ 2), hence C′ 1 ≺F C′
-
[42]
With an inductive argument we get C′ 1 \ Min(C′
Finally, if p(Min(C1)) = p(Min(C2)) and e /∈ Min(C′ 1), we again argue that Min(C1) = Min(C2) and that, hence, C \ Min(C1) and C2 \ Min(C1) are configurations of the branching process ⇑Min(C1) of (N , M(Min(C1))). With an inductive argument we get C′ 1 \ Min(C′
-
[43]
and are also done in this case. A.2. More symbolic and low-level unfoldings In this appendix we present unfoldings omitted in the main body of the paper. N. Würdemann et al. / Taking Complete Finite Prefixes To High Level, Symbolically 359 Low-level Unfolding of Fork And Join. Since the symbolic unfolding of any Fork And Join is structurally equal to the ...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.