pith. sign in

arxiv: 2203.09233 · v3 · submitted 2022-03-17 · 💻 cs.CC

On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets

Raymond Devillers , Ronny Tredup This is my paper

Pith reviewed 2026-05-24 11:45 UTC · model grok-4.3

classification 💻 cs.CC
keywords transition systemsBoolean netsflip-flop netssynthesisNP-completenessmodification techniquescomputational complexity
0
0 comments X

The pith

Making transition systems implementable by flip-flop nets via bounded modifications is NP-complete

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper examines the complexity of synthesis tasks that start from a labeled transition system and apply a limited number of changes to produce a system realizable by a flip-flop Boolean net. The changes include relabeling edges that share a label and suppressing selected edges, states, or events. The authors establish NP-completeness for most decision problems of this form when the target net type belongs to the flip-flop family or its close variants. A reader would care because the result shows that no polynomial-time procedure exists for these bounded-adjustment tasks unless P equals NP.

Core claim

The paper claims that most of the decision problems for converting a transition system into one implementable by a flip-flop net or derivative, using at most a given number of modifications such as relabeling or suppression, are NP-complete.

What carries the argument

The bounded modification techniques of relabeling edges with identical labels and suppressing edges, states or events while requiring the result to remain close to the original transition system.

If this is right

  • Unless P equals NP, no efficient algorithm decides whether a given transition system can be turned into a flip-flop-net realization with at most k modifications.
  • The same hardness applies to several derivatives of flip-flop nets.
  • Exact synthesis under a modification budget must in general consume exponential time.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Analogous bounded-modification problems for other net types may also prove hard.
  • Practical synthesis tools would likely need heuristics or approximations rather than exact bounded search.
  • The same modification framework could be used to study complexity in related models of concurrency.

Load-bearing premise

The decision problems are defined precisely around the listed modification techniques and the requirement to stay close to the original transition system.

What would settle it

A polynomial-time algorithm that solves any one of the bounded-modification problems for flip-flop nets would falsify the NP-completeness claim.

Figures

Figures reproduced from arXiv: 2203.09233 by Raymond Devillers, Ronny Tredup.

Figure 1
Figure 1. Figure 1: All interactions i of I. If a cell is empty, then i is undefined on the respective x. nop 0 1 nop inp, swap swap Aτ R1 inp a a nop ′ swap R2 inp N AN (1, 0) (0, 1) (0, 0) a a ′ [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Left: Aτ for the the type τ = {nop, inp, swap}. Middle: A τ -net N (as usual, the initial marking is indicated by putting a token in the places p such that M0(p) = 1). Right: The reachability graph AN of N, where each state M is represented by its marking (M(R1), M(R2)), and the initial state is indicated by the arrow without source state. Definition 2.4. (τ -Nets) Let τ ⊆ I. A Boolean net N = (P, T, f, M0… view at source ↗
Figure 3
Figure 3. Figure 3: Left: The TS A with event set E = {a}. Middle: The TS B with event set E′ = {a, a′}. Right: The image BR1 of the τ -region R1 = (sup1, sig1) of B, where sup1(t0) = 1, sup1(t1) = sup1(t2) = 0, sig1(a) = inp and sig1(a ′ ) = nop, and τ = {nop, inp, swap}. Later, we shall also represent a region by a color convention indicating the support of each state. Every set R of τ -regions of A implies a particular syn… view at source ↗
Figure 4
Figure 4. Figure 4: A running graph example G; a 2-VC is {v0,v2} (in bold). In the remainder of this paper, let (G, λ) be an input of 3BVC, where G = (U, M) is a graph with n vertices U = {v0, . . . , vn−1} and m edges M = {M0, . . . , Mm−1} such that Mi = {vi0 , vi1 } and i0 < i1 for all i ∈ {0, . . . , m − 1}. For the proof of Theorem 3.3, we polynomially reduce (G, λ) to a pair (AG, κ) of TS AG = (S, E, δ, ⊥0) and natural … view at source ↗
Figure 5
Figure 5. Figure 5: The transition systems AG (top) and BG (bottom) that originate from Example 3.4. They will serve for illustrating some region constructions in the proofs below [PITH_FULL_IMAGE:figures/full_fig_p011_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Region R0 = (sup, sig) for v = v1. v occurs in T ′ 0 and T ′ 3 . The supports of t1,0, t2,0, t4,0 are chosen 0. The colored nodes have support 1, otherwise 0. When not indicated, signatures are nop. If v ∈ S, it may only occur in at most three paths of BG of the form T ′ i = ti,0 v ′ ti,1 vi ti,2 v ti,3 vi ti,4 or T ′ i = ti,0 vi ti,1 v ti,2 vi ti,3 v ′ ti,4, or T ′ i = ti,0 v ti,1 vi ti,2 v ′ ti,3 v ′ i t… view at source ↗
Figure 7
Figure 7. Figure 7: Region R1 = (sup, sig) for v = v1. v occurs in T ′ 0 and T ′ 3 . The supports of t1,0, t2,0, t4,0 are chosen 1. The colored nodes have support 1, otherwise 0. When not indicated, signatures are nop. fact that the companion vertex vi belongs to S or not. Again, if v belongs to several edges, all the corresponding companions must be different. Also, v occurs only once, as well as v ′ . For v, we may thus cho… view at source ↗
Figure 8
Figure 8. Figure 8: Region R2 = (sup, sig) for v = v0. v occurs in T ′ 0 , T ′ 1 and T ′ 2 . The supports of t3,0, t4,0 are chosen 0. The colored nodes have support 1, otherwise 0. When not indicated, signatures are nop. ⊥0 t0,0 t0,1 t0,2 t0,3 t0,4 w0 : swap v ′ 0 v1 v0 : inp v1 ⊥1 t1,0 t1,1 t1,2 t1,3 t1,4 w1 : swap v0 : inp v2 v ′ 0 v ′ 2 ⊥2 t2,0 t2,1 t2,2 t2,3 t2,4 w2 : swap v ′ 0 v3 v0 : inp v3 ⊥3 t3,0 t3,1 t3,2 t3,3 t3,4 … view at source ↗
Figure 9
Figure 9. Figure 9: Region R3 = (sup, sig) for v = v0. v occurs in T ′ 0 , T ′ 1 and T ′ 2 . The supports of t3,0, t4,0 are chosen 0. The colored nodes have support 1, otherwise 0. When not indicated, signatures are nop. Note that here no vi with i 6= 0 needs to have a signature swap; hence we do not need to add a region with signature swap for wj when T ′ j does not contain v [PITH_FULL_IMAGE:figures/full_fig_p017_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: The new transition systems AG (top) and BG (bottom) that originate from Example 3.4. Lemma 3.12. If there is an E′ -label-splitting of AG such that |E′ | ≤ κ that has the τ -ESSP, then G has a λ-VC. Proof: The proof is similar to the one of Lemma 3.10. ⊓⊔ Conversely, let S be a λ-VC of G, and let BG = (S(BG), E′ , δ′′ , ⊥0) be the bi-directed extension of the TS BG = (S(BG), E′ , δ′ , ⊥0), which has been … view at source ↗
read the original abstract

Synthesis consists in deciding whether a given labeled transition system (TS) $A$ can be implemented by a net $N$ of type $\tau$. In case of a negative decision, it may be possible to convert $A$ into an implementable TS $B$ by applying various modification techniques, like relabeling edges that previously had the same label, suppressing edges/states/events, etc. It may however be useful to limit the number of such modifications to stay close to the original problem, or optimize the technique. In this paper, we show that most of the corresponding problems are NP-complete if $\tau$ corresponds to the type of flip-flop nets or some flip-flop net derivatives.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper studies decision problems arising in the synthesis of flip-flop nets (and some derivatives) from labeled transition systems (TS). It defines problems in which a given TS is modified by a bounded number of operations (edge relabeling of same-label edges, suppression of edges/states/events) so that the resulting TS becomes implementable by a net of the target type, and proves that most of these problems are NP-complete.

Significance. The results establish NP-completeness for a family of bounded-modification synthesis problems that remain close to the original TS. If the reductions hold, they provide a precise complexity map for these practically motivated variants of net synthesis.

minor comments (2)
  1. [Abstract] Abstract: the claim that 'most of the corresponding problems are NP-complete' is stated without any indication of the reduction sources or proof structure; a single sentence sketching the main reduction technique would improve readability.
  2. [§2–3] The decision problems are defined around specific modification operations and a 'stay close' requirement; ensure that the formal definitions in §2–3 make the distance measure (number of modifications) explicit and polynomial-time checkable.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary and recommendation of minor revision. No specific major comments were listed in the report.

Circularity Check

0 steps flagged

No significant circularity; standard NP-completeness reductions from external problems

full rationale

The paper frames its results as polynomial-time reductions establishing NP-completeness for decision problems on bounded modifications (edge relabeling, suppression) to make transition systems implementable by flip-flop nets. These are standard complexity arguments relying on known external NP-complete problems rather than any self-definition, fitted inputs renamed as predictions, or load-bearing self-citations. The abstract and problem definitions are self-contained against external benchmarks with no quoted reduction that collapses to the paper's own inputs by construction. No steps meet the criteria for circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on standard definitions of transition systems, Boolean net types, and NP-completeness via reductions from the existing literature on net synthesis.

axioms (1)
  • standard math NP-completeness established via polynomial-time reductions from known NP-complete problems
    Implicit foundation for all such complexity results in the field.

pith-pipeline@v0.9.0 · 5642 in / 927 out tokens · 24913 ms · 2026-05-24T11:45:52.544452+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

  1. [1]

    Distributing Finite Automata Through Petri Net Synthesis

    Badouel E, Caillaud B, Darondeau P . Distributing Finite Automata Through Petri Net Synthesis. F ormal Asp. Comput., 2002. 13(6):447–470. doi:10.1007/s001650200022

    work page doi:10.1007/s001650200022 2002

  2. [2]

    Springer, Germany (2011)

    van der Aalst WMP . Process Mining - Discovery, Conforman ce and Enhancement of Business Processes. Springer, 2011. doi:10.1007/978-3-642-19345-3

    work page doi:10.1007/978-3-642-19345-3 2011

  3. [3]

    A Survey of Petri Net Method s for Controlled Discrete Event Systems

    Holloway LE, Krogh BH, Giua A. A Survey of Petri Net Method s for Controlled Discrete Event Systems. Discrete Event Dynamic Systems , 1997. 7(2):151–190. doi:10.1023/A:1008271916548

    work page doi:10.1023/a:1008271916548 1997

  4. [4]

    A region-based theory for state assignment in speed-independent circuits

    Cortadella J, Kishinevsky M, Kondratyev A, Lavagno L, Y a kovlev A. A region-based theory for state assignment in speed-independent circuits. IEEE Trans. on CAD of Integrated Circuits and Systems , 1997. 16(8):793–812. doi:10.1109/43.644602

    work page doi:10.1109/43.644602 1997

  5. [5]

    Petri Net Synth esis

    Badouel E, Bernardinello L, Darondeau P . Petri Net Synth esis. Texts in Theoretical Computer Science. An EA TCS Series. Springer, 2015. doi:10.1007/978-3-662-4 7967-4

    work page doi:10.1007/978-3-662-4 2015

  6. [6]

    The Label Splitting Problem

    Carmona J. The Label Splitting Problem. Trans. Petri Nets Other Model. Concurr ., 2012. 6:1–23. doi: 10.1007/978-3-642-35179-2 \

    work page doi:10.1007/978-3-642-35179-2 2012

  7. [7]

    URL https://doi.org/10.1007/978-3-642-35179-2_1

    work page doi:10.1007/978-3-642-35179-2_1

  8. [8]

    Deri ving Petri nets from finite transition systems

    Cortadella J, Kishinevsky M, Lavagno L, Y akovlev A. Deri ving Petri nets from finite transition systems. IEEE Transactions on Computers, 1998. 47(8):859–882

    work page 1998

  9. [9]

    Relabelling LTS for Petri Net Syn thesis via Solving Separation Problems

    Schlachter U, Wimmel H. Relabelling LTS for Petri Net Syn thesis via Solving Separation Problems. Trans. Petri Nets Other Model. Concurr ., 2019. 14:222–254. doi:10.1007/978-3-662-60651-3 \ 9

    work page doi:10.1007/978-3-662-60651-3 2019

  10. [10]

    Optimal Label Splitting for Embe dding an LTS into an arbitrary Petri Net Reachability Graph is NP-complete

    Schlachter U, Wimmel H. Optimal Label Splitting for Embe dding an LTS into an arbitrary Petri Net Reachability Graph is NP-complete. CoRR, 2020. abs/2002.04841. 2002.04841

    work page arXiv 2020

  11. [11]

    Finding an Optimal Label-Splitting to Make a T ransition System Petri Net Implementable: a Complete Complexity Characterization

    Tredup R. Finding an Optimal Label-Splitting to Make a T ransition System Petri Net Implementable: a Complete Complexity Characterization. In: Proceedings of the 21st Italian Conference on Theoretical Computer Science, Ischia, Italy, September 14-16, 2020. 20 20 pp. 131–144

    work page 2020

  12. [12]

    Some Basic Techniques allowing Petri Net Synthesis: Complexity and Algorith- mic Issues

    Devillers RR, Tredup R. Some Basic Techniques allowing Petri Net Synthesis: Complexity and Algorith- mic Issues. CoRR, 2021. abs/2112.03605. 2112.03605, URL https://arxiv.org/abs/2112.03605

    work page arXiv 2021

  13. [13]

    Edge, Event and State Removal: The Complexity of Some Basic Techniques that Make Transi- tion Systems Petri Net Implementable

    Tredup R. Edge, Event and State Removal: The Complexity of Some Basic Techniques that Make Transi- tion Systems Petri Net Implementable. In: Application and T heory of Petri Nets and Concurrency - 42nd International Conference, PETRI NETS 2021, Virtual Event, June 23-25, 2021, Proceedings. 2021 pp. 253–273. doi:10.1007/978-3-030-76983-3 \ 13

    work page doi:10.1007/978-3-030-76983-3 2021

  14. [14]

    Trace Nets and Process Automata

    Badouel E, Darondeau P . Trace Nets and Process Automata . Acta Inf. , 1995. 32(7):647–679. doi: 10.1007/BF01186645

    work page doi:10.1007/bf01186645 1995

  15. [15]

    Step semantics of boolean nets

    Kleijn J, Koutny M, Pietkiewicz-Koutny M, Rozenberg G. Step semantics of boolean nets. Acta Inf., 2013. 50(1):15–39. doi:10.1007/s00236-012-0170-2

    work page doi:10.1007/s00236-012-0170-2 2013

  16. [16]

    Contextual Nets

    Montanari U, Rossi F. Contextual Nets. Acta Inf., 1995. 32(6):545–596. doi:10.1007/BF01178907. 296 R. Devillers and R. Tredup / The Complexity of Techniques That Make Transition Systems I mplementable

    work page doi:10.1007/bf01178907 1995

  17. [17]

    Transition Systems of Elementa ry Net Systems with Inhibitor Arcs

    Pietkiewicz-Koutny M. Transition Systems of Elementa ry Net Systems with Inhibitor Arcs. In: ICA TPN, volume 1248 of Lecture Notes in Computer Science . Springer, 1997 pp. 310–327. doi: 10.1007/3-540-63139-9 \ 43

    work page doi:10.1007/3-540-63139-9 1997

  18. [18]

    Elementary Net Systems

    Rozenberg G, Engelfriet J. Elementary Net Systems. In: Petri Nets, volume 1491 of Lecture Notes in Computer Science. Springer, 1996 pp. 12–121. doi:10.1007/3-540-65306-6 \ 14

    work page doi:10.1007/3-540-65306-6 1996

  19. [19]

    Flip-Flop Nets

    Schmitt V . Flip-Flop Nets. In: STACS, volume 1046 of Lecture Notes in Computer Science . Springer, 1996 pp. 517–528. doi:10.1007/3-540-60922-9 \ 42

    work page doi:10.1007/3-540-60922-9 1996

  20. [20]

    The Synthesis Problem for Elementary Net Systems is NP- Complete

    Badouel E, Bernardinello L, Darondeau P . The Synthesis Problem for Elementary Net Systems is NP- Complete. Theor . Comput. Sci., 1997. 186(1-2):107–134. doi:10.1016/S0304-3975(96)00219-8

    work page doi:10.1016/s0304-3975(96)00219-8 1997

  21. [21]

    The Complexity of Synthesizing nop-Equipped Boolean Petri Nets from g-Bounded Inputs

    Tredup R. The Complexity of Synthesizing nop-Equipped Boolean Petri Nets from g-Bounded Inputs. Trans. Petri Nets Other Model. Concurr ., 2021. 15:101–125

    work page 2021

  22. [22]

    In: Fodor, P., Montali, M., Calvanese, D., Roman, D

    Tredup R, Rosenke C. The Complexity of Synthesis for 43 B oolean Petri Net Types. In: TAMC, volume 11436 of Lecture Notes in Computer Science . Springer, 2019 pp. 615–634. doi:10.1007/978-3-030- \ linebreak14812-6

    work page doi:10.1007/978-3-030- 2019

  23. [23]

    On the Hardness of Synthesizing Boo lean Nets

    Tredup R, Rosenke C. On the Hardness of Synthesizing Boo lean Nets. In: A TAED@Petri Nets/ACSD, volume 2371 of CEUR W orkshop Proceedings. CEUR-WS.org, 2019 pp. 71–86

    work page 2019

  24. [24]

    The Complexity of Boolean State Sep aration

    Tredup R, Erofeev E. The Complexity of Boolean State Sep aration. In: Theoretical Aspects of Com- puting - ICTAC 2020 - 17th International Colloquium, Macau, China, November 30 - December 4, 2020, Proceedings. 2020 pp. 123–142. doi:10.1007/978-3-030-64 276-1\ 7

    work page doi:10.1007/978-3-030-64 2020

  25. [25]

    Polynomial Al gorithms for the Synthesis of Bounded Nets

    Badouel E, Bernardinello L, Darondeau P . Polynomial Al gorithms for the Synthesis of Bounded Nets. In: TAPSOFT, volume 915 of Lecture Notes in Computer Science . Springer, 1995 pp. 364–378. doi: 10.1007/3-540-59293-8 \ 207

    work page doi:10.1007/3-540-59293-8 1995

  26. [26]

    The Complexity of the Label-Splitting-Probl em for Flip-Flop-Nets

    Tredup R. The Complexity of the Label-Splitting-Probl em for Flip-Flop-Nets. In: Reachability Problems - 14th International Conference, RP 2020, Paris, France, Oc tober 19-21, 2020, Proceedings. 2020 pp. 148–163. doi:10.1007/978-3-030-61739-4 \ 10

    work page doi:10.1007/978-3-030-61739-4 2020

  27. [27]

    Computers and Intractability: A G uide to the Theory of NP-Completeness

    Garey MR, Johnson DS. Computers and Intractability: A G uide to the Theory of NP-Completeness. W . H. Freeman, 1979. ISBN 0-7167-1044-7

    work page 1979