betaFeedback

WorksComputer Science

Complexity of liveness in ring Petri nets and of halting in chip-firing on simple digraphs

Abstract

A ring Petri net (weighted circuit, cyclic weighted T-system) consists of a single directed circuit with arbitrary positive arc weights. We show that deciding liveness of ring Petri nets is coNP-complete, and that coNP-hardness holds in the strong sense already for token-conserving rings, in which every transition consumes and produces the same number of tokens. The proof is a short reduction from the covering problem for systems of residue classes (the complement of Simultaneous Incongruences). Together with a known reduction to circuits, it follows that liveness of weighted T-systems (weighted marked graphs, synchronous dataflow graphs) is coNP-complete, and coNP-hard in the strong sense. As a further consequence, the halting problem for chip-firing on simple directed graphs is NP-complete, which answers a question of Farrell and Levine. On 7 October 2026, the problem of liveness was posed to the AI model Claude Opus 5.5 (Anthropic), which found the reduction, also suggesting the application to the chip-firing problem, and wrote a first version of this paper; the human authors checked it and, together with the model, revised it iteratively into the present form.

Introduction

Weighted T-systems (also known as weighted marked graphs, weighted event graphs, or synchronous dataflow graphs) are Petri nets in which every place has exactly one input and one output transition, while arcs may carry arbitrary weights. For ordinary (plain) T-systems, liveness is decidable in polynomial time: such a system is live iff every circuit carries a token, or equivalently, iff some firing sequence fires every transition exactly once [7], [1 Thm. 5.31]. A counterpart of the second criterion is known for weighted T-systems [26], but there the vector of ones is replaced by a T-invariant that may be exponentially large [1 Sect. 5.10]. The Petri Net Primer [1 Sect. 5.10] states:

“At the date of publishing this book, no polynomial algorithm appears to be known to check the liveness of weighted T-systems.”

It includes two weighted T-nets (fig:5.23 there) for readers wishing to try a “finger exercise in weighted T-systems”, even just in weighted cycles, also called ring nets, for which it refers to [28]. One of the two nets is taken from [9], and recent advances in [10] are mentioned. Liveness of weighted circuits was related to the Diophantine problem of Frobenius by Chrz¸astowski-Wachtel and Raczunas [8]. The complexity of liveness has also been described as open in the literature on weighted event graphs and synchronous dataflow graphs. Marchetti and Munier-Kordon Marchetti and Munier-Kordon [21] write, about liveness and the maximal throughput of timed weighted event graphs, that “the complexity of these two previous problem[s] is still open and is also a challenging theoretical question”, and a survey talk on synchronous dataflow [23] still lists the complexity of schedulability (i.e. liveness) and of the maximal throughput as unknown; see also [22], where a polynomially computable sufficient condition for liveness is given.

On the upper-bound side, Hujsa, Berthomieu, Dal Zilio and Le Botlan showed that a weighted circuit is non-live iff the state equation has a solution leading to a dead marking [18, Thm. 6.6], and even iff it has a solution leading to an integer vector, possibly with negative entries, at which no transition is enabled [18 Thm. 6.8]; with standard bounds on integer programs this puts liveness of ring nets in coNP for binary-encoded numbers. The same authors established a characterisation of this kind for a class that contains all strongly connected weighted T-systems [19 Cor. 6.7], and derived a coNP upper bound for the structurally bounded systems of that class [19 Sect. 6.2]. This paper supplies a matching lower bound, already for single circuits.

Main result.

  • Theorem 4.6. Deciding liveness of ring Petri nets is coNP-complete. Hardness holds already for token-conserving rings (every transition consumes as many tokens as it produces) whose arc weights and token numbers are all bounded by a polynomial in the number of places; in particular the problem is coNP-hard in the strong sense (i.e. also for unary encodings).

  • Corollary 4.9. Deciding liveness of weighted T-systems is coNP-complete, and coNP-hard in the strong sense.

By Lemma 3.3, deadlock-freeness and weak liveness of ring nets coincide with liveness, so they are coNP-complete as well. Hardness in Corollary 4.9 holds because ring nets are weighted T-systems, and membership follows from Proposition 3.5 and a known reduction to circuits [18 Prop. 6.3]. In particular, unless P = NP, liveness of weighted T-systems cannot be decided by a pseudo-polynomial algorithm, i.e. in time polynomial in the size of the system and the largest number occurring in it.

The reduction is from Cover: given residue classes rir_i mod bib_i for i=0,1,…,m−1i = 0, 1, \ldots, m - 1, decide whether every integer lies in one of them. The ring consists of mm “test” places with output weights bib_i, alternating with mm “buffer” places with output weight WW, a prime larger than all bib_i (Figure 2). The ring behaves like a counter. In each “round”, every buffer transition fires once; after zz rounds, a further round is possible iff WzWz lies in one of the residue classes, and the test place belonging to the class rir_i mod bib_i checks whether Wz≡ri(modbi)Wz \equiv r_i \pmod{b_i}. So the ring deadlocks after exactly z∗z^* rounds, where z∗z^* is the least z≥0z \ge0 such that WzWz avoids all residue classes, and it runs forever if there is no such zz.

The ring $R(I,W)$ for $m=3$

Figure 2. The ring R(I,W)R(I,W) for m=3m = 3. Numbers inside places give the initial marking, labels at arcs the weights; rˉi=(−ri) mod bi\bar{r}_i = (-r_i) \bmod b_i, and W>max⁡ibiW > \max_i b_i is coprime to all bib_i. Tokens flow clockwise.

Chip-firing. As a consequence, the halting problem for chip-firing on simple digraphs is NP-complete, and NP-hard already for strongly connected ones (§ 5). This answers a question of Farrell and Levine [14], who proved NP-completeness for strongly connected multigraphs; their hard instances may have large edge multiplicities.

Further results, on reversibility and reachability of ring nets and on tractable special cases, are planned for a later version of this paper.

Organisation. Section 2 recalls Petri nets and ring nets. Section 3 characterises liveness of ring nets by deadlock certificates and proves the coNP upper bound. Section 4 gives the reduction, the main result and its extension to weighted T-systems, Section 5 treats chip-firing, and Section 6 concludes.

How this paper came about. On 7 October 2026, the complexity of liveness for ring nets was posed as an open problem to the AI model Claude Opus 5.5 (Anthropic). The model found the reduction from Cover presented in Section 4, also suggested its application to the question of Farrell and Levine on chip-firing (Section 5), and produced a first version of this paper, including computational cross-checks of its claims. The human authors checked the paper (the statements, the proofs and the use of the literature) and, over several rounds, asked for corrections, more detailed arguments and further material. These revisions were carried out with the model and led to the present version, which the authors have checked. The statements of Sections 3–5 were also cross-checked computationally, on exhaustive families of small instances and on many random instances, with two independent implementations; details are planned for the later version.

Preliminaries

Notation. We write N={0,1,2,…}\mathbb{N} = \{0,1,2,\ldots\} for the set of natural numbers (including 0) and Z\mathbb{Z} for the set of integers. For an integer xx and an integer b≥1b \ge1, ⌊x/b⌋\lfloor x/b \rfloor is the largest integer that is at most x/bx/b, and

xmod⁡b:=x−b⌊x/b⌋∈{0,1,…,b−1}x \mathbin{\operatorname{mod}} b := x - b\lfloor x/b \rfloor\in\{0,1,\ldots,b-1\}

is the remainder of xx modulo bb; this also applies to negative xx (for instance, (−3)mod⁡4=1(-3) \mathbin{\operatorname{mod}} 4 = 1). We write b∣xb \mid x if bb divides xx, and x≡x′(modb)x \equiv x' \pmod{b} if b∣x−x′b \mid x-x', i.e. if xmod⁡b=x′mod⁡bx \mathbin{\operatorname{mod}} b = x' \mathbin{\operatorname{mod}} b.

Lists are written with their first two members, as in s0,s1,…,sn−1s_0,s_1,\ldots,s_{n-1} or j=1,2,…,kj=1,2,\ldots,k. Such a list may be shorter than the notation suggests: for n=1n=1, the list s0,s1,…,sn−1s_0,s_1,\ldots,s_{n-1} consists of s0s_0 only.

For a finite set XX, a vector v∈ZXv \in\mathbb{Z}^{X} (or v∈NXv \in\mathbb{N}^{X}) is a function v ⁣:X→Zv\colon X \to\mathbb{Z} (or into N\mathbb{N}). For n∈Nn \in\mathbb{N} we also write nn for the set {0,1,…,n−1}\{0,1,\ldots,n-1\}; thus the elements of Zn\mathbb{Z}^{n} are the tuples v=(v0,v1,…,vn−1)v=(v_0,v_1,\ldots,v_{n-1}) of integers. We write 0\mathbf{0} for the zero vector, whose entries are all 0. Vectors are compared componentwise: u≤vu \le v means u(x)≤v(x)u(x) \le v(x) for all x∈Xx \in X, and u<vu < v means u(x)<v(x)u(x) < v(x) for all x∈Xx \in X. In particular, v≥0v \ge0 means that all entries of vv are non-negative. For a matrix C∈ZS×TC \in\mathbb{Z}^{S \times T}, i.e. a function C ⁣:S×T→ZC\colon S \times T \to\mathbb{Z}, and a vector Y∈ZTY \in\mathbb{Z}^{T}, the vector C⋅Y∈ZSC \cdot Y \in\mathbb{Z}^{S} is defined by (C⋅Y)(s)=∑t∈TC(s,t)Y(t)(C \cdot Y)(s) = \sum_{t \in T} C(s,t)Y(t).

Petri nets and markings. A Petri net (or simply a net) is a triple N=(S,T,F)N=(S,T,F) consisting of

  • a finite set SS of places and a finite set TT of transitions, with S∩T=∅S \cap T = \varnothing;

  • a weight function F ⁣:(S×T)∪(T×S)→NF\colon(S \times T) \cup(T \times S) \to\mathbb{N}: there is an arc from a place ss to a transition tt iff F(s,t)>0F(s,t)>0, and then F(s,t)F(s,t) is the weight of this arc; similarly for arcs from transitions to places.

A marking of NN is a vector M∈NSM \in\mathbb{N}^{S}. We think of M(s)M(s) as the number of tokens on the place ss; in particular, markings are non-negative by definition. A marked net is a pair (N,M0)(N,M_0) of a net NN and a marking M0M_0 of NN, its initial marking. Notions such as the incidence matrix and TT-invariants, introduced below, depend only on NN; notions such as liveness depend on the marked net. For a transition tt, the places ss with F(s,t)>0F(s,t)>0 are the input places of tt, and the places ss with F(t,s)>0F(t,s)>0 are its output places; similarly, the transitions tt with F(t,s)>0F(t,s)>0 and those with F(s,t)>0F(s,t)>0 are the input transitions and the output transitions of a place ss.

Firing. A transition tt is enabled at a marking MM if M(s)≥F(s,t)M(s) \ge F(s,t) for all s∈Ss \in S, i.e. if every input place ss of tt carries at least F(s,t)F(s,t) tokens. An enabled transition tt can fire (or occur). Firing tt removes F(s,t)F(s,t) tokens from every place ss and adds F(t,s)F(t,s) tokens to every place ss; it leads to the marking M′M' with

M′(s)=M(s)−F(s,t)+F(t,s)(s∈S),M'(s) = M(s) - F(s,t) + F(t,s) \qquad(s \in S),

and we write M→tM′M \xrightarrow{t} M'. (The vector M′M' is again a marking, i.e. non-negative, because tt is enabled at MM.)

We write T∗T^* for the set of finite words over TT, including the empty word ε\varepsilon. A (finite) firing sequence from a marking MM is a word σ=t1t2⋯tk∈T∗\sigma= t_1t_2\cdots t_k \in T^* for which there are markings M=M(0),M(1),…,M(k)M = M^{(0)}, M^{(1)}, \ldots, M^{(k)} with M(j−1)→tjM(j)M^{(j-1)} \xrightarrow{t_j} M^{(j)} for j=1,2,…,kj = 1, 2, \ldots, k; we then write M→σM(k)M \xrightarrow{\sigma} M^{(k)}, or simply M→σM \xrightarrow{\sigma} if the final marking does not matter. The length of σ\sigma is ∣σ∣=k|\sigma| = k. The empty word ε\varepsilon is a firing sequence of length 0 from every marking, and M→εMM \xrightarrow{\varepsilon} M. An infinite firing sequence from MM is an infinite word t1t2t3⋯t_1t_2t_3 \cdots such that each of its finite prefixes t1t2⋯tkt_1t_2 \cdots t_k is a firing sequence from MM. A marking M′M' is reachable from MM if M→σM′M \xrightarrow{\sigma} M' for some finite firing sequence σ\sigma; the set of all markings reachable from MM is denoted by [M⟩[M\rangle (it contains MM itself). The markings in [M0⟩[M_0\rangle are the reachable markings of the marked net (N,M0)(N,M_0).

A marking is dead (or a deadlock) if it enables no transition. A firing sequence from a marking MM is maximal if it is infinite, or if it is finite and leads to a dead marking; in other words, if it cannot be extended by a further transition.

Parikh vectors and the state equation. For a finite word σ\sigma over TT, the Parikh vector P(σ)∈NT\mathcal{P}(\sigma) \in\mathbb{N}^{T} counts how often each transition occurs in σ\sigma: P(σ)(t)\mathcal{P}(\sigma)(t) is the number of occurrences of tt in σ\sigma; thus ∣σ∣=∑t∈TP(σ)(t)|\sigma| = \sum_{t \in T} \mathcal{P}(\sigma)(t). The incidence matrix of NN is the matrix C∈ZS×TC \in\mathbb{Z}^{S \times T} with

C(s,t)=F(t,s)−F(s,t)(s∈S, t∈T),C(s,t) = F(t,s) - F(s,t) \qquad(s \in S,\ t \in T),

References

  1. [1]E. Best and R. Devillers. Petri Net Primer: A Compendium on the Core Model, Analysis, and Synthesis. Computer Science Foundations and Applied Logic. Birkhäuser, 2024. https://doi.org/10.1007/978-3-031-48278-6.
  2. [2]A. Björner and L. Lovász. Chip-firing games on directed graphs. J. Algebraic Combin., 1:305–328, 1992.
  3. [3]A. Björner, L. Lovász, and P. W. Shor. Chip-firing games on graphs. European J. Combin., 12:283–291, 1991.
  4. [4]B. Bond and L. Levine. Abelian networks I. Foundations and examples. SIAM J. Discrete Math., 30(2):856–874, 2016. https://doi.org/10.1137/15M1030984.
  5. [5]S. K. Baruah, L. E. Rosier, and R. R. Howell. Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor. Real-Time Systems, 2(4):301–324, 1990.DOI
  6. [6]I. Borosh and L. B. Treybig. Bounds on positive integral solutions of linear Diophantine equations. Proc. Amer. Math. Soc., 55(2):299–304, 1976.DOI
  7. [7]F. Commoner, A. W. Holt, S. Even, and A. Pnueli. Marked directed graphs. J. Comput. System Sci., 5:511–523, 1971.DOI
  8. [8]P. Chrząstowski-Wachtel and M. Raczunas. Liveness of weighted circuits and the Diophantine problem of Frobenius. In FCT 1993, LNCS 710, pages 171–180. Springer, 1993. https://doi.org/10.1007/3-540-57163-9_13.
  9. [9]P. Chrząstowski-Wachtel and M. Raczunas. Orbits, half-frozen tokens and the liveness of weighted circuits. In STRuCT 1995, Workshops in Computing, pages 116–128. Springer, 1995. https://doi.org/10.1007/978-1-4471-3078-9_8.
  10. [10]R. Devillers. On the reversibility of circular conservative Petri nets. In PETRI NETS 2023, LNCS 13929, pages 307–323. Springer, 2023. https://doi.org/10.1007/978-3-031-33620-1_17.
  11. [11]EGRES Open (open problem collection of the Egerváry Research Group). Chip-firing. https://lemon.cs.elte.hu/egres/open/Chip-firing, accessed 15 October 2026.
  12. [12]EGRES Open (open problem collection of the Egerváry Research Group). Complexity of the halting problem for simple digraphs. https://lemon.cs.elte.hu/egres/open/Complexity_of_the_halting_problem_for_simple_digraphs, accessed 15 October 2026.
  13. [13]P. Erdős. On integers of the form 2^k + p and some related problems. Summa Brasil. Math., 2:113–123, 1950.
  14. [14]M. Farrell and L. Levine. CoEulerian graphs. Proc. Amer. Math. Soc., 144(7):2847–2860, 2016. https://doi.org/10.1090/proc/12952. Preprint arXiv:1502.04690.
  15. [15]A. Fey, L. Levine, and Y. Peres. Growth rates and explosions in sandpiles. J. Stat. Phys., 138(1–3):143–159, 2010. https://doi.org/10.1007/s10955-009-9899-6.
  16. [16]M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
  17. [17]J. von zur Gathen and M. Sieveking. A bound on solutions of linear integer equalities and inequalities. Proc. Amer. Math. Soc., 72(1):155–158, 1978.
  18. [18]T. Hujsa, B. Berthomieu, S. Dal Zilio, and D. Le Botlan. Checking marking reachability with the state equation in Petri net subclasses. arXiv:2006.05600, 2020.arxiv.org/abs/2006.05600
  19. [19]T. Hujsa, B. Berthomieu, S. Dal Zilio, and D. Le Botlan. On the Petri nets with a single shared place and beyond. arXiv:2005.04818, 2020.arxiv.org/abs/2005.04818
  20. [20]J. Y.-T. Leung and M. L. Merrill. A note on preemptive scheduling of periodic, real-time tasks. Inform. Process. Lett., 11(3):115–118, 1980.DOI
  21. [21]O. Marchetti and A. Munier-Kordon. Cyclic scheduling problems for the synthesis of digital signal processing. Book chapter, preprint, LIP6, Université Pierre et Marie Curie, 2008. https://largo.lip6.fr/pub/reports/2008/rp.lip6.2008.marchetti.1.pdf. Published as: Cyclic scheduling for the synthesis of embedded systems, Chapter 6 of Y. Robert and F. Vivien (eds.), Introduction to Scheduling, CRC Press, 2010.
  22. [22]O. Marchetti and A. Munier-Kordon. A sufficient condition for the liveness of weighted event graphs. European J. Oper. Res., 197(2):532–540, 2009.DOI
  23. [23]A. Munier-Kordon. Synchronous DataFlow: A survival guide. Talk at the Scheduling Seminar, 28 September 2022. https://schedulingseminar.com/presentations/SchedulingSeminar_AlixMunierKordon.pdf.
  24. [24]C. H. Papadimitriou. On the complexity of integer programming. J. ACM, 28(4):765–768, 1981.DOI
  25. [25]L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time. In Proc. 5th ACM STOC, pages 1–9, 1973.DOI
  26. [26]E. Teruel, P. Chrząstowski-Wachtel, J. M. Colom, and M. Silva. On weighted T-systems. In Application and Theory of Petri Nets 1992, LNCS 616, pages 348–367. Springer, 1992. https://doi.org/10.1007/3-540-55676-1_20.
  27. [27]L. Tóthmérész. Rotor-routing reachability is easy, chip-firing reachability is hard. European J. Combin., 101:103466, 2022.DOI
  28. [28]J. Weihmann. Generalized Petri Nets: Algorithms and Complexity. PhD thesis, Technische Universität München, 2015.

Paper details

vlnc:W_4a3zdr3f
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude Opus 5.5 (bare)

View statement
Looking for related papers…
Contents