Top

Published in:

2020 | OriginalPaper | Chapter

The Complexity of the Label-Splitting-Problem for Flip-Flop-Nets

Author : Ronny Tredup

Published in: Reachability Problems

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Let \(\tau \) be a type of nets. Synthesis consists in deciding whether a given labelled 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 \(A'\) by relabeling edges that previously had the same label differently: Label-splitting is the problem to decide for a TS A and a natural number \(\kappa \) whether there is an implementable TS B with at most \(\kappa \) labels, which is derived from A by splitting labels. In this paper, we show that label-splitting is NP-complete if \(\tau \) corresponds to the type of flip-flop nets or some flip-flop net derivatives.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter The Collatz Process Embeds a Base Conversion Algorithm

van der Aalst, W.M.P.: Process Mining - Discovery, Conformance and Enhancement of Business Processes. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19345-3CrossRefMATH

Badouel, E., Bernardinello, L., Darondeau, P.: Polynomial algorithms for the synthesis of bounded nets. In: Mosses, P.D., Nielsen, M., Schwartzbach, M.I. (eds.) CAAP 1995. LNCS, vol. 915, pp. 364–378. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-59293-8_207CrossRef

Badouel, E., Bernardinello, L., Darondeau, P.: The synthesis problem for elementary net systems is NP-complete. Theoret. Comput. Sci. 186(1–2), 107–134 (1997). https://doi.org/10.1016/S0304-3975(96)00219-8MathSciNetCrossRefMATH

Badouel, E., Bernardinello, L., Darondeau, P.: Petri Net Synthesis. TTCSAES. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47967-4CrossRefMATH

Badouel, E., Caillaud, B., Darondeau, P.: Distributing finite automata through Petri net synthesis. Formal Asp. Comput. 13(6), 447–470 (2002). https://doi.org/10.1007/s001650200022CrossRefMATH

Badouel, E., Darondeau, P.: Trace nets and process automata. Acta Informatica 32(7), 647–679 (1995). https://doi.org/10.1007/BF01186645MathSciNetCrossRefMATH

Carmona, J.: The label splitting problem. In: Jensen, K., van der Aalst, W.M., Ajmone Marsan, M., Franceschinis, G., Kleijn, J., Kristensen, L.M. (eds.) Transactions on Petri Nets and Other Models of Concurrency VI. LNCS, vol. 7400, pp. 1–23. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-35179-2_1CrossRef

Cortadella, J., Kishinevsky, M., Lavagno, L., Yakovlev, A.: Deriving petri nets from finite transition systems. IEEE Trans. Comput. 47(8), 859–882 (1998)MathSciNetCrossRef

Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L., Yakovlev, A.: A region-based theory for state assignment in speed-independent circuits. IEEE Trans. CAD Integr. Circuits Syst. 16(8), 793–812 (1997). https://doi.org/10.1109/43.644602CrossRefMATH

10.

Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)MATH

11.

Holloway, L.E., Krogh, B.H., Giua, A.: A survey of Petri net methods for controlled discrete event systems. Discrete Event Dyn. Syst. 7(2), 151–190 (1997). https://doi.org/10.1023/A:1008271916548CrossRefMATH

12.

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

13.

Montanari, U., Rossi, F.: Contextual nets. Acta Informatica 32(6), 545–596 (1995). https://doi.org/10.1007/BF01178907MathSciNetCrossRefMATH

14.

Pietkiewicz-Koutny, M.: Transition systems of Elementary Net Systems with inhibitor arcs. In: Azéma, P., Balbo, G. (eds.) ICATPN 1997. LNCS, vol. 1248, pp. 310–327. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-63139-9_43CrossRef

15.

Rozenberg, G., Engelfriet, J.: Elementary net systems. In: Reisig, W., Rozenberg, G. (eds.) ACPN 1996. LNCS, vol. 1491, pp. 12–121. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-65306-6_14CrossRef

16.

Schlachter, U., Wimmel, H.: Relabelling LTS for Petri net synthesis via solving separation problems. In: Koutny, M., Pomello, L., Kristensen, L.M. (eds.) Transactions on Petri Nets and Other Models of Concurrency XIV. LNCS, vol. 11790, pp. 222–254. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-662-60651-3_9CrossRef

17.

Schlachter, U., Wimmel, H.: Optimal label splitting for embedding an LTS into an arbitrary Petri net reachability graph is NP-complete. CoRR abs/2002.04841 (2020). https://arxiv.org/abs/2002.04841

18.

Schmitt, V.: Flip-flop nets. In: Puech, C., Reischuk, R. (eds.) STACS 1996. LNCS, vol. 1046, pp. 515–528. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-60922-9_42CrossRef

19.

Tredup, R.: The complexity of synthesizing nop-equipped Boolean nets from g-bounded inputs. Technical report (2019)

20.

Tredup, R.: Finding an optimal label-splitting to make a transition system petri net implementable: a complete complexity characterization. In: Italian Conference on Theoretical Computer Science - 21st Annual Conference, ICTCS 2020 (2020, to appear )

21.

Tredup, R., Erofeev, E.: The complexity of Boolean state separation (2020). Submitted to ICTAC 2020 (2020)

22.

Gopal, T.V., Watada, J. (eds.): TAMC 2019. LNCS, vol. 11436. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-14812-6CrossRef

23.

Tredup, R., Rosenke, C.: On the hardness of synthesizing Boolean nets. In: ATAED@Petri Nets/ACSD. CEUR Workshop Proceedings, vol. 2371, pp. 71–86 (2019). CEUR-WS.org

Title: The Complexity of the Label-Splitting-Problem for Flip-Flop-Nets
Author: Ronny Tredup
Publisher: Springer International Publishing
Book: Reachability Problems
Print ISBN: 978-3-030-61738-7

Electronic ISBN: 978-3-030-61739-4

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-61739-4_10

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner