Kleijn, Jetty; Koutny, Maciej; Pietkiewicz-Koutny, Marta Regions of Petri nets with a/sync connections. (English) Zbl 1267.68156 Theor. Comput. Sci. 454, 189-198 (2012). Authors’ abstract: Automated synthesis from behavioural specifications, such as transition systems, is an attractive way of constructing correct concurrent systems. In this paper, we investigate the synthesis of Petri nets which use special connections between transitions and places. Along these a/sync connections tokens can be transferred instantaneously between transitions executed in a single step. We show that for place/transition nets with a/sync connections the synthesis problem can be treated within the general approach based on regions of step transition systems. We also show that the problem is decidable for finite transition systems, and outline a suitable construction algorithm. Reviewer: Krassimir Atanassov (Sofia) Cited in 4 Documents MSC: 68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) Keywords:concurrency; transition system; Petri net; theory of regions; synthesis problem; place transition net; step sequence semantics; synchronous and asynchronous communication; a/sync connection Software:VipTool; rbminer; Genet; Reo PDFBibTeX XMLCite \textit{J. Kleijn} et al., Theor. Comput. Sci. 454, 189--198 (2012; Zbl 1267.68156) Full Text: DOI References: [1] Arbab, F., Reo: a channel-based coordination model for component composition, Mathematical Structures in Computer Science, 14, 329-366 (2004) · Zbl 1085.68552 [2] Badouel, E.; Bernardinello, L.; Darondeau, P., The synthesis problem for elementary net systems is NP-complete, Theoretical Computer Science, 186, 107-134 (1997) · Zbl 0893.68111 [3] Badouel, E.; Darondeau, P., Theory of Regions, (Reisig, W.; Rozenberg, G., Lectures on Petri Nets I: Basic Models, Advances in Petri Nets. Lectures on Petri Nets I: Basic Models, Advances in Petri Nets, Lecture Notes in Computer Science, vol. 1491 (1998), Springer), 529-586 · Zbl 0926.68088 [4] Bergenthum, R.; Desel, J.; Lorenz, R.; Mauser, S., (Synthesis of Petri Nets from Scenarios with VipTool. Synthesis of Petri Nets from Scenarios with VipTool, Lecture Notes in Computer Science, 5062 (2008), Springer), 388-398 [5] Bruni, R.; Montanari, U., Zero-safe nets: comparing the collective and individual token approaches, Information and Computation, 156, 46-89 (2000) · Zbl 1046.68615 [6] Busi, N.; Pinna, G. M., (Synthesis of Nets with Inhibitor Arcs. Synthesis of Nets with Inhibitor Arcs, Lecture Notes in Computer Science, 1243 (1997), Springer), 151-165 · Zbl 1512.68162 [7] J. Carmona, J. Cortadella, M. Kishinevsky, Genet: a tool for the synthesis and mining of Petri nets, in: Proc. of ACSD’09, IEEE Computer Society, 2009, pp. 181-185.; J. Carmona, J. Cortadella, M. Kishinevsky, Genet: a tool for the synthesis and mining of Petri nets, in: Proc. of ACSD’09, IEEE Computer Society, 2009, pp. 181-185. [8] Chernikova, N., 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) · Zbl 0171.35701 [9] Christensen, S.; Hansen, D., (Coloured Petri Nets Extended with Channels for Synchronous Communication. Coloured Petri Nets Extended with Channels for Synchronous Communication, Lecture Notes in Computer Science, vol. 815 (1994), Springer), 159-178 [10] Cortadella, J.; Kishinevsky, M.; Kondratyev, A.; Lavagno, L.; Yakovlev, A., Logic Synthesis of Asynchronous Controllers and Interfaces (2002), Springer · Zbl 1013.68273 [11] Darondeau, P., (Deriving Unbounded Petri Nets from Formal Languages. Deriving Unbounded Petri Nets from Formal Languages, Lecture Notes in Computer Science, vol. 1466 (1998), Springer), 533-548 · Zbl 0940.68097 [12] Darondeau, P., On the Petri net realization of context-free graphs, Theoretical Computer Science, 258, 573-598 (2001) · Zbl 0973.68171 [13] Darondeau, P.; Koutny, M.; Pietkiewicz-Koutny, M.; Yakovlev, A., Synthesis of nets with step firing policies, Fundamenta Informaticae, 94, 275-303 (2009) · Zbl 1182.68139 [14] Desel, J.; Reisig, W., The synthesis problem of Petri nets, Acta Informatica, 33, 297-315 (1996) · Zbl 0849.68085 [15] Desel, J., Yakovlev, A. (Eds.): Applications of Region Theory 2011. Proc. of the Workshop Applications of Region Theory 2011, ART-2011, CEUR-WS vol. 725, 2011 http://ceur-ws.org/Vol-725/; Desel, J., Yakovlev, A. (Eds.): Applications of Region Theory 2011. Proc. of the Workshop Applications of Region Theory 2011, ART-2011, CEUR-WS vol. 725, 2011 http://ceur-ws.org/Vol-725/ [16] Ehrenfeucht, A.; Rozenberg, G., Partial 2-structures; Part I: basic notions and the representation problem, and Part II: state spaces of concurrent systems, Acta Informatica, 27, 315-368 (1990) · Zbl 0696.68083 [17] F. Fernandez, P. Quinton, Extension of Chernikova’s algorithm for solving general mixed linear programming problems, Technical Report RR-943, INRIA Rennes, 1988.; F. Fernandez, P. Quinton, Extension of Chernikova’s algorithm for solving general mixed linear programming problems, Technical Report RR-943, INRIA Rennes, 1988. [18] Hoogers, P. W.; Kleijn, H. C.M.; Thiagarajan, P. S., A trace semantics for Petri nets, Information and Computation, 117, 98-114 (1995) · Zbl 0826.68085 [19] Kleijn, J.; Koutny, M., (Causality in Structured Occurrence Nets. Causality in Structured Occurrence Nets, Lecture Notes in Computer Science, vol. 6875 (2011), Springer), 283-297 [20] J. Kleijn, M. Koutny, Localities in Systems with a/sync Communication, Technical Report CS-TR-1285, School of Computing Science, Newcastle University, 2011.; J. Kleijn, M. Koutny, Localities in Systems with a/sync Communication, Technical Report CS-TR-1285, School of Computing Science, Newcastle University, 2011. · Zbl 1238.68099 [21] Koutny, M.; Pietkiewicz-Koutny, M., Synthesis of Petri Nets with Localities, Scientific Annals of Computer Science, 19, 1-23 (2009) · Zbl 1424.68107 [22] Koutny, M.; Randell, B., Structured occurrence nets: a formalism for aiding system failure prevention and analysis techniques, Fundamenta Informaticae, 97, 41-91 (2009) · Zbl 1187.68328 [23] Mukund, M., Petri nets and step transition systems, International Journal of Foundations of Computer Science, 3, 443-478 (1992) · Zbl 0774.68086 [24] Nielsen, M.; Rozenberg, G.; Thiagarajan, P. S., Elementary transition systems, Theoretical Computer Science, 96, 3-33 (1992) · Zbl 0759.68022 [25] Pietkiewicz-Koutny, M., Synthesising elementary net systems with inhibitor arcs from step transition systems, Fundamenta Informaticae, 50, 175-203 (2002) · Zbl 1003.68097 [26] Schmitt, V., (Flip-Flop Nets. Flip-Flop Nets, Lecture Notes in Computer Science, vol. 1046 (1996), Springer), 517-528 · Zbl 1379.68247 [27] Solé, M.; Carmona, J., (Rbminer: A Tool for Discovering Petri Nets from Transition Systems. Rbminer: A Tool for Discovering Petri Nets from Transition Systems, Lecture Notes in Computer Science, vol. 6252 (2010), Springer), 396-402 [28] van der Werf, J. M.E. M.; van Dongen, B. F.; Hurkens, C. A.J.; Serebrenik, A., (Process Discovery Using Integer Linear Programming. Process Discovery Using Integer Linear Programming, Lecture Notes in Computer Science, vol. 5062 (2008), Springer), 368-387 · Zbl 1143.68497 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.