Published in Volume XIX, 2009, pages 1-23

Authors: M. Koutny and M. Pietkiewicz-Koutny

Abstract

Automated synthesis from behavioural specifications is an attractive way of constructing computational systems. In this paper, we look at a specific instance of this approach which aims at constructing GALS (globally asynchronous locally synchronous) systems. GALS systems are represented by Petri nets with localities, each locality defining a set of co-located actions, and specifications are given in terms of transition systems with arcs labelled by steps of executed actions. The proposed synthesis procedures are based on the regions of transition systems, and work without knowing which actions are to be co-located.

Full Text (PDF)

References

[1] E. Badouel, L. Bernardinello, Ph. Darondeau. The Synthesis Problem for Elementary Net Systems is NP-complete. Theoretical Computer Science 186, pp. 107-134, 1997.

[2] E. Badouel, Ph. Darondeau. Theory of Regions. In: W. Reisig, G. Rozenberg (eds.) Lectures on Petri Nets I: Basic Models, Advances in Petri Nets. Lecture Notes in Computer Science 1491. Springer-Verlag, Berlin Heidelberg New York, pp. 529-586, 1998.

[3] L. Bernardinello. Synthesis of Net Systems In: M.A. Marsan (ed.) Application and Theory of Petri Nets 1993. Lecture Notes in Computer Science 691. Springer-Verlag, Berlin Heidelberg New York, pp. 89-105, 1993.

[4] N. Chernikova. Algorithm for Finding a General Formula for the Nonnegative Solutions of a System of Linear Inequalities. USSR Computational Mathematics and Mathematical Physics 5, pp. 228-233, 1965.

[5] P. Darondeau, M. Koutny, M. Pietkiewicz-Koutny, A. Yakovlev. Synthesis of Nets with Step Firing Policies. Fundamenta Informaticae 94, pp. 275-303, 2009.

[6] S. Dasgupta, D. Potop-Butucaru, B. Caillaud, A. Yakovlev. Moving from Weakly Endochronous Systems to Delay-Insensitive Circuits. Electronic Notes in Theoretical Computer Science 146, pp. 81-103, 2006.

[7] J. Desel, W. Reisig. The Synthesis Problem of Petri Nets. Acta Informatica 33, pp. 297-315, 1996.

[8] A. Ehrenfeucht, G. Rozenberg. Partial 2-structures; Part I: Basic Notions and the Representation Problem, and Part II: State Spaces of Concurrent Systems. Acta Informatica 27, pp. 315-368, 1990.

[9] H.C.M. Kleijn, M. Koutny, G. Rozenberg. Towards a Petri Net Semantics for Membrane Systems. In: R. Freund, G. Paun, G. Rozenberg, A. Salomaa (eds.) WMC 2005. Lecture Notes in Computer Science 3850. Springer-Verlag, Berlin Heidelberg New York, pp. 292-309, 2006.

[10] M. Koutny, M. Pietkiewicz-Koutny. Transition Systems of Elementary Net Systems with Localities. In: C. Baier, H. Hermanns (eds.) CONCUR 2006. Lecture Notes in Computer Science 4137. Springer-Verlag, Berlin Heidelberg New York, pp. 173-187, 2006.

[11] M. Koutny, M. Pietkiewicz-Koutny. Synthesis of Elementary Net Systems with Context Arcs and Localities. Fundamenta Informaticae 88, pp. 307-328, 2008.

[12] M. Koutny, M. Pietkiewicz-Koutny. Synthesis of PTL-nets with Partially Localised Conflicts. In: D. Moldt (ed.) PNSE’2009, Universit´e Paris 13, pp. 247-254, 2009.

[13] M. Koutny, M. Pietkiewicz-Koutny. Minimal Regions of ENL-transition Systems. In: L. Czaja, M. Szczuka (eds.) CS&P’2009, Warsaw University, pp. 303-314, 2009.

[14] M. Mukund. Petri Nets and Step Transition Systems. International Journal of Foundations of Computer Science 3, pp. 443-478, 1992.

[15] M. Nielsen, G. Rozenberg, P.S. Thiagarajan. Elementary Transition Systems. Theoretical Computer Science 96, pp. 3-33, 1992.

[16] G. Paun. Membrane Computing, An Introduction. Springer-Verlag, Berlin Heidelberg New York, 2002.

[17] M. Pietkiewicz-Koutny. The Synthesis Problem for Elementary Net Systems with Inhibitor Arcs. Fundamenta Informaticae 40, pp. 251- 283, 1999.

[18] X. Yang, Z. Duan. Operational semantics of Framed Tempura. Journal of Logic and Algebraic Programming 78, pp. 22-51, 2008.

Bibtex

@article{sacscuza:koutny2009sopnwl,
  title={Synthesis of Petri Nets with Localities},
  author={M. Koutny and M. Pietkiewicz-Koutny},
  journal={Scientific Annals of Computer Science},
  volume={19},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2009},
  pages={1--23},
  publisher={``A.I. Cuza'' University Press}
}