Adding A/Sync Places to the Synthesis Procedure for Whole-Place Operations Nets with Localities

Published in Volume XXVII, Issue 2, 2017, pages 177-212, doi: 10.7561/SACS.2017.2.177

Authors: J. Kleijn, M. Koutny, M. Pietkiewicz-Koutny

Abstract

Assuming that the behavioural specification of a concurrent system is given in the form of a step transition system, where the arcs between states are labelled by steps (multisets of executed actions), we focus on the problem of synthesising a Petri net generating a reachability graph isomorphic to a given step transition system. To deal with step transition systems more complicated than those generated by standard Place/Transition nets, we consider in this paper Petri nets with wholeplace operations, localities, and a/sync places. We adapt and extend the general approach developed within the framework of τ -nets and the theory of regions of step transition systems. Building on the results presented in [23], emphasis here is on the role of a/sync places with their potential for an instantaneous transfer of tokens within a step. In a series of results we demonstrate the robustness of the notion of region for Petri net synthesis.

Full Text (PDF)

References

[1] P.A. Abdulla, G. Delzanno, and L. Van Begin. A language-based comparison of extensions of Petri nets with and without whole-place operations. In A.-H. Dediu, A.-M. Ionescu, and C. Martın-Vide, editors, Language and Automata Theory and Applications, Third International Conference, LATA 2009, Tarragona, Spain, April 2-8, 2009. Proceedings, volume 5457 of Lecture Notes in Computer Science, pages 71–82. Springer, 2009. doi:10.1007/978-3-642-00982-2_6.

[2] F. Arbab. Reo: a channel-based coordination model for component composition. Mathematical Structures in Computer Science, 14(3):329– 366, 2004. doi:10.1017/S0960129504004153.

[3] E. Badouel, L. Bernardinello, and P. Darondeau. Petri Net Synthesis. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2015. doi:10.1007/978-3-662-47967-4.

[4] E. Badouel and P. Darondeau. Theory of regions. In Wolfgang Reisig and Grzegorz Rozenberg, editors, Lectures on Petri Nets I: Basic Models, Advances in Petri Nets, the volumes are based on the Advanced Course on Petri Nets, held in Dagstuhl, September 1996, volume 1491 of Lecture Notes in Computer Science, pages 529–586. Springer, 1996. doi:10. 1007/3-540-65306-6_22.

[5] R. Bergenthum, J. Desel, R. Lorenz, and S. Mauser. Synthesis of Petri nets from scenarios with VipTool. In K.M. van Hee and R. Valk, editors, Applications and Theory of Petri Nets, 29th International Conference, PETRI NETS 2008, Xi’an, China, June 23-27, 2008. Proceedings, volume 5062 of Lecture Notes in Computer Science, pages 388–398. Springer, 2008. doi:10.1007/978-3-540-68746-7_25.

[6] L. Bernardinello, G. De Michelis, K. Petruni, and S. Vigna. On the synchronic structure of transition systems. In Jo¨rg Desel, editor, Structures in Concurrency Theory, Workshops in Computing, pages 69–84. Springer, 1995. doi:10.1007/978-1-4471-3078-9_5.

[7] R. Bruni and U. Montanari. Zero-safe nets: Comparing the collective and individual token approaches. Information and Computation, 156(1- 2):46–89, 2000. doi:10.1006/inco.1999.2819.

[8] N. Busi and G. Michele Pinna. Synthesis of nets with inhibitor arcs. In
A.W. Mazurkiewicz and J. Winkowski, editors, CONCUR ’97: Concurrency Theory, 8th International Conference, Warsaw, Poland, July 1-4, 1997, Proceedings, volume 1243 of Lecture Notes in Computer Science, pages 151–165. Springer, 1997. doi:10.1007/3-540-63141-0_11.

[9] J. Carmona, J. Cortadella, and M. Kishinevsky. Genet: A tool for the synthesis and mining of Petri nets. In Ninth International Conference on Application of Concurrency to System Design, ACSD 2009, Augsburg, Germany, 1-3 July 2009, pages 181–185. IEEE Computer Society, 2009. doi:10.1109/ACSD.2009.6.

[10] N. Chernikova. Algorithm for finding a general formula for the non- negative solutions of a system of linear inequalities. USSR Computational Mathematics and Mathematical Physics, 5:228–233, 1965. doi:10.1016/0041-5553(65)90045-5.

[11] S. Christensen and N.D. Hansen. Coloured Petri nets extended with channels for synchronous communication. In R. Valette, editor, Application and Theory of Petri Nets 1994, 15th International Conference, Zaragoza, Spain, June 20-24, 1994, Proceedings, volume 815 of Lecture Notes in Computer Science, pages 159–178. Springer, 1994. doi:10.1007/3-540-58152-9_10.

[12] J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, and A. Yakovlev. Logic Synthesis of Asynchronous Controllers and Interfaces, volume 8 of Springer Series in Advanced Microelectronics. Springer, 2002. doi:10.1007/978-3-642-55989-1.

[13] P. Darondeau. Deriving unbounded Petri nets from formal languages. In D. Sangiorgi and R. de Simone, editors, CONCUR ’98: Concurrency Theory, 9th International Conference, Nice, France, September 8-11, 1998, Proceedings, volume 1466 of Lecture Notes in Computer Science, pages 533–548. Springer, 1998. doi:10.1007/BFb0055646.

[14] P. Darondeau, M. Koutny, M. Pietkiewicz-Koutny, and A. Yakovlev. Synthesis of nets with step firing policies. Fundamenta Informaticae, 94(3-4):275–303, 2009. doi:10.3233/FI-2009-132.

[15] J. Desel and W. Reisig. The synthesis problem of Petri nets. Acta Informatica, 33(4):297–315, 1996. doi:10.1007/s002360050046.

[16] C. Dufourd, A. Finkel, and P. Schnoebelen. Reset nets between decidability and undecidability. In K.G. Larsen, S. Skyum, and G. Winskel, editors, Automata, Languages and Programming, 25th International Colloquium, ICALP’98, Aalborg, Denmark, July 13-17, 1998, Proceedings, volume 1443 of Lecture Notes in Computer Science, pages 103–115. Springer, 1998. doi:10.1007/BFb0055044.

[17] A. Ehrenfeucht and G. Rozenberg. Partial (set) 2-structures. part I: basic notions and the representation problem. part II: state spaces of concurrent system. Acta Informatica, 27(4):315–368, 1990. doi: 10.1007/BF00264611.

[18] A. Finkel, P. McKenzie, and C. Picaronny. A well-structured framework for analysing Petri net extensions. Information and Computation, 195(1- 2):1–29, 2004. doi:10.1016/j.ic.2004.01.005.

[19] P. W. Hoogers, H. C. M. Kleijn, and P. S. Thiagarajan. A trace semantics for Petri nets. Information and Computation, 117(1):98–114, 1995. doi:10.1006/inco.1995.1032.

[20] J. Kleijn and M. Koutny. Causality in structured occurrence nets. In C.B. Jones and J.L. Lloyd, editors, Dependable and Historic Computing – Essays Dedicated to Brian Randell on the Occasion of His 75th Birthday, volume 6875 of Lecture Notes in Computer Science, pages 283–297. Springer, 2011. doi:10.1007/978-3-642-24541-1_22.

[21] J. Kleijn and M. Koutny. Localities in systems with a/sync communication. Theoretical Computer Science, 429:185–192, 2012. doi: 10.1016/j.tcs.2011.12.038.

[22] J. Kleijn, M. Koutny, and M. Pietkiewicz-Koutny. Regions of Petri nets with a/sync connections. Theoretical Computer Science, 454:189–198, 2012. doi:10.1016/j.tcs.2012.04.016.

[23] J. Kleijn, M. Koutny, and M. Pietkiewicz-Koutny. Synthesis of Petri nets with whole-place operations and localities. In A. Sampaio and F. Wang, editors, Theoretical Aspects of Computing – ICTAC 2016 – 13th International Colloquium, Taipei, Taiwan, ROC, October 24-31, 2016, Proceedings, volume 9965 of Lecture Notes in Computer Science, pages 103–120, 2016. doi:10.1007/978-3-319-46750-4_7.

[24] J. Kleijn, M. Koutny, M. Pietkiewicz-Koutny, and G. Rozenberg. Applying regions. Theoretical Computer Science, 658:205–215, 2017. doi:10.1016/j.tcs.2016.01.040.

[25] M. Koutny and M. Pietkiewicz-Koutny. Synthesis of Petri nets with localities. Scientific Annals of Computer Science, 19:1–23, 2009. URL: http://www.info.uaic.ro/bin/Annals/Article?v=XIX&a=0.

[26] M. Mukund. Petri nets and step transition systems. International Journal of Foundations of Computer Science, 3(4):443–478, 1992. doi: 10.1142/S0129054192000231.

[27] M. Nielsen, G. Rozenberg, and P. S. Thiagarajan. Elementary transition systems. Theoretical Computer Science, 96(1):3–33, 1992. doi:10.1016/ 0304-3975(92)90180-N.

[28] M. Pietkiewicz-Koutny. Transition systems of elementary net systems with inhibitor arcs. In P. Azema and G. Balbo, editors, Application and Theory of Petri Nets 1997, 18th International Conference, ICATPN ’97, Toulouse, France, June 23-27, 1997, Proceedings, volume 1248 of Lecture Notes in Computer Science, pages 310–327. Springer, 1997. doi:10.1007/3-540-63139-9_43.

[29] V. Schmitt. Flip-flop nets. In C. Puech and R. Reischuk, editors, STACS 96, 13th Annual Symposium on Theoretical Aspects of Computer Science, Grenoble, France, February 22-24, 1996, Proceedings, volume 1046 of Lecture Notes in Computer Science, pages 517–528. Springer, 1996. doi:10.1007/3-540-60922-9_42.

[30] M. Sole and J. Carmona. Rbminer: A tool for discovering Petri nets from transition systems. In A. Bouajjani and W.-N. Chin, editors, Automated Technology for Verification and Analysis – 8th International Symposium, ATVA 2010, Singapore, September 21-24, 2010. Proceedings, volume 6252 of Lecture Notes in Computer Science, pages 396–402. Springer, 2010. doi:10.1007/978-3-642-15643-4_33.

[31] J. M. E. M van der Werf, B.F. van Dongen, C.A.J. Hurkens, and A. Serebrenik. Process discovery using integer linear programming.In K.M. van Hee and R. Valk, editors, Applications and Theory of Petri Nets, 29th International Conference, PETRI NETS 2008, Xi’an, China, June 23-27, 2008. Proceedings, volume 5062 of Lecture Notes in Computer Science, pages 368–387. Springer, 2008. doi:10.1007/978-3-540-68746-7_24.

Bibtex

@article{sacscuza:kleijn2017aapttspfwonwl,
  title={Adding A/Sync Places to the Synthesis Procedure for Whole-Place Operations Nets with Localities},
  author={J. Kleijn and M. Koutny and M. Pietkiewicz-Koutny},
  journal={Scientific Annals of Computer Science},
  volume={27},
  number={2},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2017},
  pages={177--212},
  doi={10.7561/SACS.2017.2.177},
  publisher={``A.I. Cuza'' University Press}
}