Minimal Regions of ENL-Transition Systems

• Autorzy: Koutny M. , Pietkiewicz-Koutny M.
• Języki publikacji: EN

Abstrakty

EN

One of the possible ways of constructing concurrent systems is their automated synthesis from behavioural specifications. In this paper, we look at a particular instance of this approach which aims at constructing GALS (globally asynchronous locally synchronous) systems from specifications given in terms of transition systems with arcs labelled by steps of executed actions. GALS systems are represented by Elementary Net Systems with Localities (ENL-systems), each locality defining a set of co-located actions. The synthesis procedure is based on the regions of transition systems and we provide a number of criteria aimed at generating a minimal set of regions (conditions) of an ENL-system generating a given transition system.

Słowa kluczowe

EN

theory of concurrency; Petri net; localities; analysis and synthesis; step sequence semantics; conflict; theory of regions; transition systems

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 101, nr 1/2
• Strony: 45--58
• Opis fizyczny: Bibliogr. 15 poz., wykr.

Twórcy

autor

Koutny M.

autor

Pietkiewicz-Koutny M.

• School of Computing Science, Newcastle University, Newcastle upon Tyne NE1 7RU, U.K,

Bibliografia

• [1] Arnold, A.: Finite Transition Systems. Prentice Hall International (1994)
• [2] Badouel, E., Bernardinello, L., Darondeau, Ph.: The Synthesis Problem for Elementary Net Systems is NPcomplete. Theoretical Computer Science 186 (1997) 107-134
• [3] Badouel, E., Darondeau, Ph.: Theory of Regions. In: Reisig, W., Rozenberg, G. (eds.): Lectures on Petri Nets I: Basic Models, Advances in Petri Nets. Lecture Notes in Computer Science 1491. Springer-Verlag, Berlin Heidelberg New York (1998) 529-586
• [4] Bernardinello, L.: Synthesis of Net Systems. In: Marsan, M.A. (ed.): Application and Theory of Petri Nets 1993. Lecture Notes in Computer Science 691. Springer-Verlag, Berlin Heidelberg New York (1993) 89-105
• [5] Darondeau, P., Koutny, M., Pietkiewicz-Koutny, M., Yakovlev, A.: Synthesis of Nets with Step Firing Policies. In: van Hee, K.M., Valk, R. (eds.): PETRI NETS 2008. Lecture Notes in Computer Science 5062. Springer-Verlag, Berlin Heidelberg New York (2008) 112-131
• [6] Dasgupta, S., Potop-Butucaru, D., Caillaud, B., Yakovlev, A.: Moving from Weakly Endochronous Systems to Delay-Insensitive Circuits. Electronic Notes in Theoretical Computer Science 146 (2006) 81-103
• [7] Desel, J., Reisig, W.: The Synthesis Problem of Petri Nets. Acta Informatica 33 (1996) 297-315
• [8] Kleijn, H.C.M., Koutny, M., Rozenberg, G.: Towards a Petri Net Semantics for Membrane Systems. In: Freund, R., Paun, G., Rozenberg, G., Salomaa, A. (eds.): WMC 2005. Lecture Notes in Computer Science 3850. Springer-Verlag, Berlin Heidelberg New York (2006) 292-309
• [9] Koutny, M., Pietkiewicz-Koutny, M.: Transition Systems of Elementary Net Systems with Localities. In: Baier, C., Hermanns, H. (eds.): CONCUR 2006. Lecture Notes in Computer Science 4137. Springer-Verlag, Berlin Heidelberg New York (2006) 173-187
• [10] Koutny, M., Pietkiewicz-Koutny, M.: Synthesis of Elementary Net Systems with Context Arcs and Localities. Fundamenta Informaticae 88 (2008) 307-328
• [11] Koutny, M., Pietkiewicz-Koutny, M.: Synthesis of Petri Nets with Localities. Scientific Annals of Computer Science 19 (2009) 1-23
• [12] Mukund, M.: Petri Nets and Step Transition Systems. International Journal of Foundations of Computer Science 3 (1992) 443-478
• [13] Nielsen, M., Rozenberg, G., Thiagarajan, P.S.: Elementary Transition Systems. Theoretical Computer Science 96 (1992) 3-33
• [14] Păun, G.: Membrane Computing, An Introduction. Springer-Verlag, Berlin Heidelberg New York (2002)
• [15] Pietkiewicz-Koutny, M.: The Synthesis Problem for Elementary Net Systems with Inhibitor Arcs. Fundamenta Informaticae 40 (1999) 251-283