Hasse Diagram Generators and Petri Nets

• Autorzy: Oliveira Oliveira M.de
• Języki publikacji: EN

Abstrakty

EN

In [18] Lorenz and Juh'as raised the question of whether there exists a suitable formalism for the representation of infinite families of partial orders generated by Petri nets. Restricting ourselves to bounded p/t-nets, we propose Hasse diagram generators as an answer. We show that Hasse diagram generators are expressive enough to represent the partial order language of any bounded p/t net. We prove as well that it is decidable both whether the (possibly infinite) family of partial orders represented by a given Hasse diagram generator is included in the partial order language of a given p/t-net and whether their intersection is empty. Based on this decidability result, we prove that the partial order languages of two given Petri nets can be effectively compared with respect to inclusion. Finally we address the synthesis of k-safe p/t-nets from Hasse diagram generators.

Słowa kluczowe

EN

Petri net; causality/partial order theory of concurrency

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 105, nr 3
• Strony: 263--289
• Opis fizyczny: Bibliogr. 20 poz., wykr.

Twórcy

autor

Oliveira Oliveira M.de

• Blavatnik School of Computer Science, Tel-Aviv University, Ramat Aviv, Tel-Aviv 69978, Israel,

Bibliografia

• [1] E. Badouel and P. Darondeau. On the synthesis of general Petri nets. Technical Report PI-1061, IRISA, 1996.
• [2] E. Badouel and P. Darondeau. Theory of regions. In Lectures on Petri Nets I: Basic Models, volume 1491 of LNCS, pages 529-586, 1998.
• [3] R. Bergenthum, J. Desel, G. Juhás, and R. Lorenz. Can I execute my scenario in your net? viptool tells you! In Proc. of ICATPN 2006, volume 4024 of LNCS, pages 381-390, 2006.
• [4] R. Bergenthum, J. Desel, R. Lorenz, and S. Mauser. Synthesis of Petri nets from finite partial languages. Fundamenta Informaticae, 88(4):437-468, 2008.
• [5] R. Bergenthum, J. Desel, R. Lorenz, and S. Mauser. Synthesis of Petri nets from infinite partial languages. In Proc. of 8th ACSD, pages 170-179. IEEE, 2008.
• [6] R. Bergenthum, J. Desel, R. Lorenz, and S. Mauser. Synthesis of Petri nets from scenarios with viptool. In Proc. of 29th ICATPN, volume 5062 of LNCS, pages 388-398, 2008.
• [7] E. Best and H. Wimmel. Reducing k -safe Petri nets to pomset-equivalent 1-safe Petri nets. In Proc. of 21th ICATPN, volume 1825 of LNCS, pages 63-82, 2000.
• [8] P. Darondeau. Deriving unbounded Petri nets from formal languages. LNCS, 1466:533-548, 1998.
• [9] P. Darondeau. Region based synthesis of P/T-nets and its potential applications. In Proc. of 21th ICATPN, volume 1825 of LNCS, pages 16-23, 2000.
• [10] R. Dilworth. A decomposition theorem for partially ordered sets. Annals of Mathematics, 51:161-166, 1950.
• [11] A. Ehrenfeucht and G. Rozenberg. Partial (set) 2-structures. Part I: Basic notions and the representation problem. Acta Informatica, 27(4):315-342, 1989.
• [12] A. Ehrenfeucht and G. Rozenberg. Partial (set) 2-structures. Part II: State spaces of concurrent systems. Acta Informatica, 27(4):343-368, 1989.
• [13] J. Esparza and M. Nielsen. Decidability issues for Petri nets - a survey. Bulletin of the EATCS, 52:244-262, 1994.
• [14] U. Goltz and W. Reisig. Processes of place/transition-nets. In Proc. of ICALP, volume 154 of LNCS, pages 264-277, 1983.
• [15] P. Hoogers, H. Kleijn, and P. Thiagarajan. A trace semantics for Petri nets. Information and Computation, 117(1):98-114, 1995.
• [16] L. Jategaonkar and A. Meyer. Deciding true concurrency equivalences on safe, finite nets. Theoretical Computer Science, 154:107-143, 1996.
• [17] G. Juhás, R. Lorenz, and J. Desel. Can I execute my scenario in your net? In Proc. of 26th ICATPN, volume 3536 of LNCS, pages 289-308, 2005.
• [18] R. Lorenz and G. Juhás. Towards synthesis of Petri nets from scenarios. In Proc. of 27th ICATPN, volume 4024 of LNCS, pages 302-321, 2006.
• [19] E. Post. A variant of a recursively unsolvable problem. Bulletin of the American Mathematical Society, 52:264-268, 1946.
• [20] W. Vogler. Petri nets and their semantics. In Modular Constructions and Partial Order Semantics of Petri Nets, volume 625 of LNCS, pages 9-32, 1992.