Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Report on the Model Checking Contest at Petri Nets 2011

  • Chapter
Transactions on Petri Nets and Other Models of Concurrency VI

Part of the book series: Lecture Notes in Computer Science ((TOPNOC,volume 7400))

Abstract

This article presents the results of the Model Checking Contest held within the SUMo 2011 workshop, a satellite event of Petri Nets 2011. This contest aimed at a fair and experimental evaluation of the performances of model checking techniques applied to Petri nets.

The participating tools were compared on several examinations (state space generation, deadlock detection and evaluation of reachability formulæ) run on a set of common models (Place/Transition and Symmetric Petri nets). The collected data gave some hints about the way techniques can scale up depending on both examinations and the characteristics of the models.

This paper also presents the lessons learned from the organizer’s point of view. It discusses the enhancements required for future editions of the Model Checking Contest event at the Petri Nets conference.

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

Access this chapter

Log in via an institution

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

eBook
USD 15.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 15.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

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Aloul, F.A., Markov, I.L., Sakallah, K.A.: FORCE: a fast and easy-to-implement variable-ordering heuristic. In: ACM Great Lakes Symposium on VLSI, pp. 116–119. ACM (2003)

    Google Scholar 

  2. Berthelot, G.: Transformations and Decompositions of Nets. In: Brauer, W., Reisig, W., Rozenberg, G. (eds.) APN 1986. LNCS, vol. 254, pp. 359–376. Springer, Heidelberg (1987)

    Google Scholar 

  3. Buchs, D., Hostettler, S.: Sigma Decision Diagrams. In: Preliminary Proceedings of the 5th International Workshop on Computing with Terms and Graphs, pp. 18–32. No. TR-09-05 in TERMGRAPH workshops, Università di Pisa (2009)

    Google Scholar 

  4. Buchs, D., Hostettler, S., Marechal, A., Risoldi, M.: AlPiNA: An Algebraic Petri Net Analyzer. In: Esparza, J., Majumdar, R. (eds.) TACAS 2010. LNCS, vol. 6015, pp. 349–352. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  5. Burch, J., Clarke, E., Long, D.: Symbolic Model Checking with Partitioned Transition Relations. In: Halaas, A., Denyer, P.B. (eds.) International Conference on Very Large Scale Integration, pp. 49–58. North-Holland, Edinburgh (1991)

    Google Scholar 

  6. Chiola, G., Dutheillet, C., Franceschinis, G., Haddad, S.: On well-formed coloured nets and their symbolic reachability graph. In: Jensen, K., Rozenberg, G. (eds.) Proceedings of the 11th International Conference on Application and Theory of Petri Nets, ICATPN 1990. Reprinted in High-Level Petri Nets, Theory and Application. Springer (1991)

    Google Scholar 

  7. Chiola, G., Franceschinis, G.: Colored GSPN Models and Automatic Symmetry Detection. In: The Proceedings of the Third International Workshop on Petri Nets and Performance Models, PNPM 1989, pp. 50–60. IEEE Computer Society (1989)

    Google Scholar 

  8. Ciardo, G.: Advances in compositional approaches based on kronecker algebra: Application to the study of manufacturing systems. In: 3rd International Workshop on Performability Modeling of Computer and Communication Systems, pp. 61–65 (1996)

    Google Scholar 

  9. Ciardo, G., Trivedi, K.: A decomposition approach for stochastic reward net models. Perf. Eval. 18, 37–59 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  10. Ciardo, G., Lüttgen, G., Siminiceanu, R.: Efficient Symbolic State-Space Construction for Asynchronous Systems. In: Nielsen, M., Simpson, D. (eds.) ICATPN 2000. LNCS, vol. 1825, pp. 103–122. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  11. Clarke, E., Grumberg, O., Jha, S., Lu, Y., Veith, H.: Counterexample-Guided Abstraction Refinement. In: Emerson, E.A., Sistla, A.P. (eds.) CAV 2000. LNCS, vol. 1855, pp. 154–169. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  12. Colange, M., Baarir, S., Kordon, F., Thierry-Mieg, Y.: Crocodile: A Symbolic/Symbolic Tool for the Analysis of Symmetric Nets with Bag. In: Kristensen, L.M., Petrucci, L. (eds.) PETRI NETS 2011. LNCS, vol. 6709, pp. 338–347. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  13. Couvreur, J.-M., Thierry-Mieg, Y.: Hierarchical Decision Diagrams to Exploit Model Structure. In: Wang, F. (ed.) FORTE 2005. LNCS, vol. 3731, pp. 443–457. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  14. Dijkstra, E.W.: Self-stabilizing systems in spite of distributed control. Commun. ACM 17(11), 643–644 (1974)

    Article  MATH  Google Scholar 

  15. Esparza, J., Melzer, S.: Verification of safety properties using integer programming: Beyond the state equation. Formal Methods in System Design 16, 159–189 (2000)

    Article  Google Scholar 

  16. Evangelista, S.: High Level Petri Nets Analysis with Helena. In: Ciardo, G., Darondeau, P. (eds.) ICATPN 2005. LNCS, vol. 3536, pp. 455–464. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  17. Finnemann, J., Nielsen, T., Kærlund, L.: Petri nets with discrete variables. Tech. rep. (2011), http://jopsen.dk/downloads/PetriNetsWithDiscreteVariables.pdf

  18. Haddad, S., Kordon, F., Petrucci, L., Pradat-Peyre, J.F., Trèves, N.: Efficient State-Based Analysis by Introducing Bags in Petri Net Color Domains. In: 28th American Control Conference, ACC 2009, pp. 5018–5025. Omnipress IEEE, St-Louis (2009)

    Chapter  Google Scholar 

  19. Hamez, A., Thierry-Mieg, Y., Kordon, F.: Building efficient model checkers using hierarchical set decision diagrams and automatic saturation. Fundamenta Informaticae 94(3-4), 413–437 (2009)

    MathSciNet  MATH  Google Scholar 

  20. Heiner, M., Gilbert, D., Donaldson, R.: Petri Nets for Systems and Synthetic Biology. In: Bernardo, M., Degano, P., Zavattaro, G. (eds.) SFM 2008. LNCS, vol. 5016, pp. 215–264. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  21. Hong, S., Kordon, F., Paviot-Adet, E., Evangelista, S.: Computing a Hierarchical Static Order for Decision Diagram-Based Representation from P/T Nets. In: Jensen, K., Donatelli, S., Kleijn, J. (eds.) ToPNoC V. LNCS, vol. 6900, pp. 121–140. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  22. Hostettler, S., Linard, A., Marechal, A., Risoldi, M.: Improving the significance of benchmarks for petri nets model checkers. In: 1st International Workshop on Scalable and Usable Model Checking for Petri Nets and Other Models of Concurrency, pp. 97–111 (2010)

    Google Scholar 

  23. Hostettler, S., Marechal, A., Linard, A., Risoldi, M., Buchs, D.: High-Level Petri Net Model Checking with AlPiNA. Fundamenta Informaticae 113 (2011)

    Google Scholar 

  24. Klebanov, V., Müller, P., Shankar, N., Leavens, G.T., Wüstholz, V., Alkassar, E., Arthan, R., Bronish, D., Chapman, R., Cohen, E., Hillebrand, M., Jacobs, B., Leino, K.R.M., Monahan, R., Piessens, F., Polikarpova, N., Ridge, T., Smans, J., Tobies, S., Tuerk, T., Ulbrich, M., Weiß, B.: The 1st Verified Software Competition: Experience Report. In: Butler, M., Schulte, W. (eds.) FM 2011. LNCS, vol. 6664, pp. 154–168. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  25. Kordon, F., Linard, A., Paviot-Adet, E.: Optimized Colored Nets Unfolding. In: Najm, E., Pradat-Peyre, J.-F., Donzeau-Gouge, V.V. (eds.) FORTE 2006. LNCS, vol. 4229, pp. 339–355. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  26. Kristensen, L.M., Schmidt, K., Valmari, A.: Question-guided Stubborn Set Methods for State Properties. Formal Methods in System Design 29(3), 215–251 (2006)

    Article  MATH  Google Scholar 

  27. Kristensen, L.M., Valmari, A.: Improved Question-Guided Stubborn Set Methods for State Properties. In: Nielsen, M., Simpson, D. (eds.) ICATPN 2000. LNCS, vol. 1825, pp. 282–302. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  28. Lampka, K.: A new algorithm for partitioned symbolic reachability analysis. In: Workshop on Reachability Problems. ENTCS, vol. 223 (2008)

    Google Scholar 

  29. Lampka, K., Siegle, M.: Activity-Local State Graph Generation for High-Level Stochastic Models. In: Measuring, Modelling, and Evaluation of Systems 2006, pp. 245–264 (2006)

    Google Scholar 

  30. Lampka, K.: A new algorithm for partitioned symbolic reachability analysis. Electron. Notes Theor. Comput. Sci. 223, 137–151 (2008)

    Article  Google Scholar 

  31. Lampka, K., Siegle, M., Ossowski, J., Baier, C.: Partially-shared zero-suppressed multi-terminal bdds: concept, algorithms and applications. Formal Methods in System Design 36, 198–222 (2010)

    Article  MATH  Google Scholar 

  32. Linard, A., Paviot-Adet, E., Kordon, F., Buchs, D., Charron, S.: polyDD: Towards a Framework Generalizing Decision Diagrams. In: 10th International Conference on Application of Concurrency to System Design, ACSD 2010, pp. 124–133. IEEE Computer Society, Braga (2010)

    Chapter  Google Scholar 

  33. Minato, S.: Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems. In: Proc. of the 30th Design Automation Conference, DAC, pp. 272–277. ACM/IEEE, Dallas (Texas), USA (1993)

    Google Scholar 

  34. Pastor, E., Roig, O., Cortadella, J.: Symbolic Petri Net Analysis using Boolean Manipulation, Technical Report of Departament Arquitectura de Computadors (UPC) DAC/UPC Report No. 97/8 (1997)

    Google Scholar 

  35. Peterson, G.L.: Myths about the mutual exclusion problem. Inf. Process. Lett. 12(3), 115–116 (1981)

    Article  MATH  Google Scholar 

  36. Schmidt, K.: Narrowing petri net state spaces using the state equation. Fundamenta Informaticae 47(3-4), 325–335 (2001)

    MathSciNet  MATH  Google Scholar 

  37. Schmidt, K.: Stubborn Sets for Standard Properties. In: Donatelli, S., Kleijn, J. (eds.) ICATPN 1999. LNCS, vol. 1639, pp. 46–65. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  38. Schmidt, K.: Using Petri Net Invariants in State Space Construction. In: Garavel, H., Hatcliff, J. (eds.) TACAS 2003. LNCS, vol. 2619, pp. 473–488. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  39. Thierry-Mieg, Y., Ilié, J.-M., Poitrenaud, D.: A Symbolic Symbolic State Space Representation. In: de Frutos-Escrig, D., Núñez, M. (eds.) FORTE 2004. LNCS, vol. 3235, pp. 276–291. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  40. Thierry-Mieg, Y., Poitrenaud, D., Hamez, A., Kordon, F.: Hierarchical Set Decision Diagrams and Regular Models. In: Kowalewski, S., Philippou, A. (eds.) TACAS 2009. LNCS, vol. 5505, pp. 1–15. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  41. Wikipedia: Dining philosophers problem (2011), http://en.wikipedia.org/wiki/Dining_philosophers_problem

  42. Wimmel, H., Wolf, K.: Applying CEGAR to the Petri Net State Equation. In: Abdulla, P.A., Leino, K.R.M. (eds.) TACAS 2011. LNCS, vol. 6605, pp. 224–238. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  43. Wolf, K.: Generating Petri Net State Spaces. In: Kleijn, J., Yakovlev, A. (eds.) ICATPN 2007. LNCS, vol. 4546, pp. 29–42. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. LIP6, CNRS UMR 7606, Université P. & M. Curie - Paris 6, 4, place Jussieu, F-75252, Paris Cedex 05, France

    Fabrice Kordon, Maximilien Colange, Emmanuel Paviot-Adet & Yann Thierry-Mieg

  2. Centre Universitaire d’Informatique, Université de Genève, 7, route de Drize, CH-1227, Carouge, Switzerland

    Alban Linard & Didier Buchs

  3. LIPN, CNRS UMR 7030, Université Paris 13, 99, av. J-B Clément, 93430, Villetaneuse, France

    Sami Evangelista

  4. Department of Information Technology, Uppsala University, Sweden

    Kai Lampka

  5. Universität Rostock, 18051, Rostock, Germany

    Niels Lohmann & Harro Wimmel

Authors
  1. Fabrice Kordon
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alban Linard
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Didier Buchs
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Maximilien Colange
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Sami Evangelista
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Kai Lampka
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Niels Lohmann
    View author publications

    You can also search for this author in PubMed Google Scholar

  8. Emmanuel Paviot-Adet
    View author publications

    You can also search for this author in PubMed Google Scholar

  9. Yann Thierry-Mieg
    View author publications

    You can also search for this author in PubMed Google Scholar

  10. Harro Wimmel
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Faculty of Science, Department of Computer Science, University of Aarhus, IT-parken, Aabogade 34, 8200, Aarhus N, Denmark

    Kurt Jensen

  2. Department of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, NL-5600, Eindhoven, MB, The Netherland

    Wil M. van der Aalst

  3. Dipartimento di Elettronica e Telecomunicazioni, Politecnico di Torino, Corso Duca degli Abruzzi 24, 10129, Torino, Italy

    Marco Ajmone Marsan

  4. Dipartimento di Informatica, Università del Piemonte Orientale ”Amedeo Avogadro”, Viale T. Michel 11, 15121, Alessandria, Italy

    Giuliana Franceschinis

  5. Leiden Institute of Advanced Computer Science, LIACS, P.O. Box 9512, 2300, Leiden, RA, The Netherlands

    Jetty Kleijn

  6. Department of Computer Engineering, Faculty of Engineering, Bergen University College, Nygaardsgaten 112, Postbox 7030, 5020, Bergen, Norway

    Lars Michael Kristensen

Rights and permissions

Reprints and permissions

Copyright information

© 2012 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Kordon, F. et al. (2012). Report on the Model Checking Contest at Petri Nets 2011. 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. Lecture Notes in Computer Science, vol 7400. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-35179-2_8

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-35179-2_8

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-35178-5

  • Online ISBN: 978-3-642-35179-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation