Nothing Special   »   [go: up one dir, main page]

Skip to main content

Elementary Net Synthesis Remains NP-Complete Even for Extremely Simple Inputs

  • Conference paper
  • First Online:
Application and Theory of Petri Nets and Concurrency (PETRI NETS 2018)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 10877))

Abstract

Elementary net systems (ENS) are the most fundamental class of Petri nets. Their synthesis problem has important applications in the design of digital hardware and commercial processes. Given a labeled transition system (TS) A, feasibility is the NP-complete decision problem whether A can be synthesized into an ENS. It is known that A is feasible if and only if it has the event state separation property (ESSP) and the state separation property (SSP). Recently, these properties have also been studied individually for their practical implications. A fast ESSP algorithm, for instance, would allow applications to at least validate the language equivalence of A and a synthesized ENS. Being able to efficiently decide SSP, on the other hand, could serve as a quick-fail preprocessing mechanism for synthesis. Although a few tractable subclasses have been found, this paper destroys much of the hope that many practically meaningful input restrictions make feasibility or at least one of ESSP and SSP efficient. We show that all three problems remain NP-complete even if the input is restricted to linear TSs where every event occurs at most three times.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Agostini, A., De Michelis, G.: Improving flexibility of workflow management systems. In: van der Aalst, W., Desel, J., Oberweis, A. (eds.) Business Process Management. LNCS, vol. 1806, pp. 218–234. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45594-9_14

    Chapter  Google Scholar 

  2. Badouel, E., Darondeau, P.: Trace nets and process automata. Acta Informatica 32(7), 647–679 (1995)

    Article  MathSciNet  Google Scholar 

  3. Badouel, E., Bernardinello, L., Darondeau, P.: The synthesis problem for elementary net systems is NP-complete. Theor. Comput. Sci. 186(1–2), 107–134 (1997)

    Article  MathSciNet  Google Scholar 

  4. Badouel, E., Bernardinello, L., Darondeau, P.: Petri Net Synthesis. Texts in Theoretical Computer Science. An EATCS Series, pp. 1–325. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47967-4. ISBN 978-3-662-47966-7

    Book  MATH  Google Scholar 

  5. Best, E., Erofeev, E., Schlachter, U., Wimmel, H.: Characterising Petri net solvable binary words. In: Kordon, F., Moldt, D. (eds.) PETRI NETS 2016. LNCS, vol. 9698, pp. 39–58. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-39086-4_4

    Chapter  MATH  Google Scholar 

  6. Cortadella, J.: Private correspondence (2017)

    Google Scholar 

  7. Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L., Yakovlev, A.: Complete state encoding based on the theory of regions. In: International Symposium on Advanced Research in Asynchronous Circuits and Systems, pp. 36–47. IEEE (1996)

    Google Scholar 

  8. Hiraishi, K.: Some complexity results on TS and elementary net systems. Theor. Comput. Sci. 135(2), 361–376 (1994)

    Article  Google Scholar 

  9. Kleijn, J., Koutny, M., Pietkiewicz-Koutny, M., Rozenberg, G.: Step semantics of Boolean nets. Acta Informatica 50(1), 15–39 (2013)

    Article  MathSciNet  Google Scholar 

  10. Moore, C., Robson, J.M.: Hard tiling problems with simple tiles. Discret. Comput. Geom. 26(4), 573–590 (2001)

    Article  MathSciNet  Google Scholar 

  11. Rosenke, C., Tredup, R.: The hardness of synthesizing elementary net systems from highly restricted inputs. arXiv:1711.00220 (2017)

  12. 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_42

    Chapter  Google Scholar 

  13. Yakovlev, A.V., Koelmans, A.M.: Petri nets and digital hardware design. In: Reisig, W., Rozenberg, G. (eds.) ACPN 1996. LNCS, vol. 1492, pp. 154–236. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-65307-4_49

    Chapter  Google Scholar 

  14. OMG. Business Process Model and Notation (BPMN). Object Management Group (2016)

    Google Scholar 

  15. Scheer, A.-W.: Business Process Engineering, Reference Models for Industrial Enterprises. Springer, Heidelberg (1994). https://doi.org/10.1007/978-3-642-79142-0

    Book  Google Scholar 

  16. UML. Unified Modeling Language (UML). Object Management Group (2016)

    Google Scholar 

Download references

Acknowledgements

We thank the anonymous reviewers for their helpful suggestions. The first author thanks Eric Badouel for the inspiring correspondence about the synthesis of ENS.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Ronny Tredup .

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer International Publishing AG, part of Springer Nature

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Tredup, R., Rosenke, C., Wolf, K. (2018). Elementary Net Synthesis Remains NP-Complete Even for Extremely Simple Inputs. In: Khomenko, V., Roux, O. (eds) Application and Theory of Petri Nets and Concurrency. PETRI NETS 2018. Lecture Notes in Computer Science(), vol 10877. Springer, Cham. https://doi.org/10.1007/978-3-319-91268-4_3

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-91268-4_3

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-91267-7

  • Online ISBN: 978-3-319-91268-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics