An Algebraic Framework for Defining Behaviours of Concurrent Systems. Part 2: The Axiomatic Presentation

• Autorzy: Winkowski J.
• Języki publikacji: EN

Abstrakty

EN

The paper is the second part of two-part paper that contributeswith a concept of a process, with operations allowing to define complex processes in terms of their components, with the respective algebras, and with the idea of using the formal tools thus obtained to describe the behaviours of concurrent systems. In the first part a universal model of a process have been introduced and operations on processes have been defined. A process is viewed as a model of a run of a system (discrete, continuous, or of a mixed type). A process may have an initial state (a source), a final state (a target), or both. A process can be represented by a partially ordered multiset. Processes of which one is a continuation of the other can be composed sequentially. Independent processes, can be composed in parallel. Processes may be prefixes, i.e. independent components of initial segments of other processes. It has been shown that processes in a universe of objects and operations on such processes form a partial algebra, called algebra of processes, that is a specific partial category with respect to the sequential composition, and a specific partial monoid with respect to the parallel composition. In the second part the properties of algebras of processes described in the first part are regarded as axioms defining a class of abstract partial algebras, called behaviour-oriented algebras, and properties of such algebras are investigated. In particular, it is shown how some of the behaviour-oriented algebras can be represented as algebras of processes, and how to use them to describe phenomena with states and processes provided with specific structures.

Słowa kluczowe

EN

process; state; sequential composition; parallel composition; category; partial category; partial monoid; independence; structure; behaviour; random behaviour

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 97, nr 4
• Strony: 439--470
• Opis fizyczny: Bibliogr. 27 poz.

Twórcy

autor

Winkowski J.

• Instytut Podstaw Informatyki PAN, Ordona 21, 01-237 Warszawa, Poland,

Bibliografia

• [1] Baldan, P., Bruni, R., Montanari, U., Pre-nets, read arcs and unfolding: a functorial presentation, Proceedings of WADT'02,Wirsing, M., Pattison, D., Hennicker, R., (Eds.), Springer LNCS 2755 (2002) 145-164
• [2] Bednarczyk,M. A., Categories of Asynchronous Systems, PhD thesis in Computer Science, University of Sussex, Report no. 1/88 (1988)
• [3] Bergstra, J., Klop, J., The algebra of recursively defined processes and the algebra of regular processes, in Paradaens, J., (Ed.), Proc. of 11th ICALP, Springer LNCS 172 (1984) 82-95
• [4] Best, E., Devillers, R., Sequential and Concurrent Behaviour in Petri Net Theory, Theoret. Comput. Sci. 55 (1987) 87-136
• [5] Bourbaki, N., ´El´ements de math´ematique, Livre I (Th´eorie des ensembles), Chapitre 4 (Structures), Act. Sci. Ind. 1258, Hermann, Paris, 1957
• [6] Bucur, I., Deleanu, A., Introduction to the Theory of Categories and Functors, John Wiley and Sons Ltd., Lozanna, New York, Sydney, 1968
• [7] Corradini, A., Montanari, U., Rossi, F., Graph Processes, Fundamenta Informaticae 26 (1996), 241-265
• [8] Degano, P., Meseguer, J., Montanari, U., Axiomatizing Net Computations and Processes, in Proc. of 4th LICS Symposium, IEEE (1989) 175-185
• [9] Ehrig, H., Kreowski, H. -J., Parallelism of Manipulations in Multidimensional Information Structures, in A. Mazurkiewicz (Ed.): Proc. of MFCS'76, Springer LNCS 45 (1976) 284-293
• [10] Hoogeboom, H. J., Rozenberg, G., Diamond Properties of Elementary Net Systems, Fundamenta Informaticae 14 (1991) 287-300
• [11] Mazurkiewicz, A., Basic Notions of Trace Theory, in J. W. de Bakker,W. P. de Roever and G. Rozenberg (Eds.): Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency, Springer LNCS 354 (1988) 285-363
• [12] Milner, R., A Calculus of Communicating Systems, Springer LNCS 92 (1980)
• [13] Milner, R., Calculi of interaction, Acta Informatica 33 (1996) 707-737
• [14] Montanari, U., Rossi, F., Contextual Nets, Acta Informatica 32 (1995) 545-596
• [15] Petri, C. A., Introduction to General Net Theory, in W. Brauer (Ed.): Net Theory and Applications, Springer LNCS 84 (1980) 1-19
• [16] Reisig, W., Petri Nets: An Introduction, Springer-Verlag (1985)
• [17] Rozenberg, G., Thiagarajan, P. S., Petri Nets: Basic Notions, Structure, Behaviour, in J. W. de Bakker,W. P. de Roever and G. Rozenberg (Eds.): Current Trends in Concurrency, Springer LNCS 224 (1986) 585-668
• [18] Shields, E. W., Concurrent Machines, Computer Journal, vol. 28 (1985) 449-465
• [19] Winkowski, J., Behaviours of Concurrent Systems, Theoret. Comput. Sci. 12 (1980) 39-60
• [20] Winkowski, J., An Algebraic Description of System Behaviours, Theoret. Comput. Sci. 21 (1982) 315-340
• [21] Winkowski, J., An Algebraic Characterization of Independence of Petri Net Processes, Information Processing Letters 88 (2003), 73-81
• [22] Winkowski, J., Towards a Framework for Modelling Systems with Rich Structures of States and Processes, Fundamenta Informaticae 68 (2005), 175-206, http://www.ipipan.waw.pl/~wink/winkowski.htm
• [23] Winkowski, J., An Axiomatic Characterization of Algebras of Processes of Petri Nets, Fundamenta Informaticae 72 (2006), 407-420, http://www.ipipan.waw.pl/~wink/winkowski.htm
• [24] Winkowski, J., Behaviour Algebras, Fundamenta Informaticae 75 (2007), 537-560 http://www.ipipan.waw.pl/~wink/winkowski.htm
• [25] Winkowski, J., Towards a Framework for Modelling Behaviours of Hybrid Systems, Fundamenta Informaticae 80 (2007), 311-332 ICS PAS Report 1002 (2007), http://www.ipipan.waw.pl/~wink/winkowski.htm,
• [26] Winkowski, J., An Algebraic Framework for Defining Behaviours of Concurrent Systems. Part 1: The Constructive Presentation, to appear in Fundamenta Informaticae 97(2009)
• [27] Winskel, G., Nielsen, M., Models for Concurrency, in S. Abramsky, Dov M. Gabbay and T. S. E. Maibaum (Eds.): Handbook of Logic in Computer Science 4 (1995), 1-148