An Algebraic Framework for Defining Behaviours of Concurrent System

• Autorzy: Winkowski J.

Warianty tytułu

PL

O pewnych algebrach do definiowania zachowań systemów współbieżnych

• Języki publikacji: EN

Abstrakty

EN

The paper contributes with a concept of process viewed as a model of a run of a phenomenon (discrete, continuous, or of a mixed type), with operations allowing to define complex processes in terms of their components, and with the idea of using the formal tools thus obtained to define the behaviours of concurrent systems. A process may have an initial state (a source), a final state (a target), or both. Processes of which one is a continuation of the other can be composed sequentially. Independent processes, i.e. processes which do not disturb each other, can be composed in parallel. Processes may be prefixes, i.e. independent components of initial segments of other processes. Processes in a universe of objects and operations on such processes form a partial algebra, called algebra of processes. Algebras of processes belong to an axiomatically defined class of partial algebras, called behaviour-oriented algebras. Formally, members of this class are partial categories with respect to the sequential composition, and partial monoids with respect to the parallel composition. Moreover, members of a subclass of this class can be represented as algebras of processes. Algebras of processes and behaviour-oriented algebras can be used to define behaviours of concurrent systems. Namely, the behaviour of a system can be defined as the set of possible processes of this system with a structure on this set. Such a set is prefix-closed. The structure on this set reflects how processes compose, the prefix order, and possibly specific features of the behaviour like observability, the relation to flow of real time, etc. Algebras of processes can also be used to define behaviours with states and processes provided with specific structures, to define operations on behaviours similar to those in the existing calculi of behaviours, and to define random behaviours.

PL

W pracy sformułowano pojęcie procesu rozumianego jako model przebiegu pewnego zjawiska (dyskretnego, ciągłego, lub mieszanego typu), wprowadzono operacje pozwalające wyrażać procesy złożone przez ich składowe, oraz przedstawiono ideę użycia tych środków do definiowania zachowań systemów współbieżnych. Proces może mieć stan początkowy, stan końcowy, lub oba te stany. Procesy z których jeden jest kontynuacją innego mogą być złożone szeregowo. Procesy niezależne, tzn. takie, które sobie nie przeszkadzają, mogą być złożone równolegle. Procesy mogą być prefiksami, tzn. niezależnymi składowymi segmentów początkowych innych procesów. Procesy w pewnym uniwersum obiektów i operacje na takich procesach tworzą algebrę częściową, zwaną algebrą procesów. Algebry procesów należą do aksjomatycznie definiowalnej klasy algebr częściowych zwanych algebrami zachowaniowo-zorientowanymi. Formalnie są to kategorie częściowe ze względu na składanie szeregowe i monoidy częściowe ze względu na składanie równoległe. Ponad to, algebry pewnej podklasy tej klasy mogą być reprezentowane jako podalgebry algebr procesów. Algebry procesów i algebry zachowaniowo-zorientowane mogą służyć do definiowania zachowań systemów współbieżnych. Mianowicie, zachowanie systemu można definiować jako zbiór możliwych procesów tego systemu. Taki zbiór jest prefiksowo-zamknięty. Jego struktura opisuje jak procesy się składają, ich porządek prefiksowy, oraz ewentualnie specyficzne cechy zachowania takie jak obserwowalność, upływ czasu itp. Algebry procesów i algebry zachowaniowo-zorientowane mogą służyć m.in. do definiowania zachowań o stanach i procesach ze specyficznymi strukturami wewnętrznymi, do definiowania operacji na zachowaniach, podobnych do operacji w znanych rachunkach zachowań, oraz do definiowania zachowań losowych.

Słowa kluczowe

EN

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

PL

proces; stan; składanie szeregowe; składanie równoległe; kategoria; kategoria częściowa; monoid częściowy; niezależność; struktura; zachowanie; zachowanie losowe

• Wydawca: Instytut Podstaw Informatyki PAN
• Czasopismo: Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk
• Rocznik: 2009
• Tom: Nr 1014
• Strony: 1--125
• Opis fizyczny: Bibliogr. 47 poz., rys.

Twórcy

autor

Winkowski J.

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

Bibliografia

• [BBM 02]  Baldan, R, 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
• [Bedn 88] Bednarczyk, M. A., Categories of Asynchronous Systems, PhD thesis in Computer Science, University of Sussex, Report no. 1/88 (1988)
• [BK 84]   Bergstra, J., Klop, J., The algebra of recursively defined processes and the algebra of regular processes, in Paradaens, J., (Ed.), Proc. of llth ICALP, Springer LNCS 172 (1984) 82-95
• [BD 87]   Best, E., Devillers, R., Sequential and Concurrent Behaviour in Petri Net Theory, Theoret. Comput. Sci. 55 (1987) 87-136
• [Bou 57]  Bourbaki, N., Elements de mathematique, Livre I (Theorie des ensembles), Chapitre 4 (Structures), Act. Sci. Ind. 1258, Hermann, Paris, 1957
• [BuDe 68] Bucur, L, Deleanu, A., Introduction to the Theory of Categories and Functors, John Wiley and Sons Ltd., Lozanna, New York, Sydney, 1968
• [Carn 58] Carnap, R., Introduction to Symbolic Logic and Its Applications , Chapter G: ASs of physics, Dover Publications, Inc., New York, 1958
• [CMR 96] Corradini, A., Montanari, U., Rossi, F., Graph Processes, Fundamenta Informaticae 26 (1996), 241-265
• [David 91]David, R., Modeling of Dynamic Systems by Petri Nets, in Proc. of European Control Conference, Grenoble, France, July 2-5 1991, 136-147
• [DMM 89]  Degano, P., Meseguer, J., Montanari, U.,Axiomatizing Net Computations and Processes, in Proc. of 4th LICS Symposium, IEEE (1989) 175-185
• [DS 01]   Droste, M., Shortt, R. M., Continuous Petri Nets and Transition Systems, in Ehrig, H., et al. (Eds.), Unifying Petri Nets, Springer LNCS 2128 (2001) 457-484
• [EK 76]   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
• [Eng 91]  Engelfriet, J., Branching Processes of Petri Nets,Acta Informatica 28 (1991) 575-591
• [GP 95]   Glabbeek, R., J., van, Plotkin, G., D.,Configuration Structures, Proceedings of LICS'95, Kozen, D., (Ed.), IEEE Computer Society Press (1995) 199-209
• [HR 91]   Hoogeboom, H. J., Rozenberg, G., Diamond Properties of Elementary Net Systems, Fundamenta Informaticae 14 (1991) 287-300
• [HSP 83]  Hart, S., Sharir, M., Pnueli, A., Termination of Probabilistic Concurrent Programs, ACM Trans, on Programming Languages and Systems, Vol. 5, No. 3, July 1083, 356-380
• [Kw 03] Kwiatkowska, M., Model checking for probability and time: from theory to practice, Proc. of 18th IEEE Symposium on Logic in Computer Science (LICS'03), IEEE Computer Society Press (2003), 351-360
• [LSV 07] Lynch, N., Segala, R., Vaandrager, F., Observing Branching Structure Through Probabilistic Contexts, Siam Journal on Computing 37 (4), 977-1013, September 2007
• [Maz 88] 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
• [MMS 96] Meseguer, J., Montanari, U., Sassone, V., Process versus Unfolding semantics for Place/Transition Nets, Theoret. Comput. Sci. 153, n. 1-2 (1996) 171-210
• [Mey 66] Meyer, P. A., Probability and Potentials, Blaisdell Publishing Company, Waltham, Massachusetts, Toronto, London (1966)
• [Miln 78] Milner, R., Synthesis of Communicating Behaviour, Proc. of MFCS'78, Winkowski, J. (Ed.), Springer LNCS 64 (1978) 71-83 (1980)
• [Miln 80] Milner, R., A Calculus of Communicating Systems, Springer LNCS 92 (1980)
• [Miln 96] Milner, R., Calculi of interaction, Acta Informatica 33 (1996) 707-737
• [ML 07]   Mitra, S., Lynch, N., Trace-based Semantics for Probabilistic Timed I/O Automata, Hybrid Systems: Computation and Control (HSCC 2007), Pisa, Italy, April 3-5, 2007, Springer LNCS 4416, Full version: http://theory.lcs. mit. edu/~mitras/research/PTIOA-066-full.pdf (1980)
• [MR 95]   Montanari, U., Rossi, F., Contextual Nets, Acta Informatica 32 (1995) 545-596
• [NK 93]   Nerode, A., Kohn, W., Models for Hybrid Systems: Automata, Topologies, Controllability, Observability, Springer LNCS 736 (1993) 317-356
• [Par 80]  Parthasarathy, K. R., Introduction to Probability and Measure, New Delhi (1980)
• [Petri 62]Petri, C. A., Kommunikation mit Automaten, PhD thesis, Institut fuer Instrumentelle Mathematik, Bonn, Germany (1962)
• [Petri 77]Petri, C., A., Non-Sequential Processes, Interner Bericht ISF-77-5, Gesellschaft fuer Mathematik und Datenverarbeitung, 5205 St. Augustin, Germany (1977)
• [Petri 80]Petri, C. A., Introduction to General Net Theory, in W. Brauer (Ed.): Net Theory and Applications, Springer LNCS 84 (1980) 1-19
• [Plue 85] Pluenecke, H., K-density, N-density and finiteness properties, APN 84, Springer LNCS 188 (1985) 392-412
• [Pn 86]   Pnueli, A., Applications of temporal logic to the specification and verification of reactive systems: a survey of current trends, in: J. W. de Bakker, W.-P. de Roever and G. Rozenberg, eds., Lecture Notes in Comp. Sc. 224, Springer, Berlin, 1986, 510-584
• [Re 85]   Reisig, W., Petri Nets: An Introduction,Springer- Verlag (1985)
• [RT 86]   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
• [Sh 85]   Shields, E. W., Concurrent Machines, Computer Journal, vol. 28 (1985) 449-465
• [VVW 04]  Varacca, D., Volzer, H., Winskel, G., Probabilistic Event Structures and Domains, in P. Gardner and N. Yoshida (eds.), CONCUR 2004, Springer LNCS 3170 (2004), 497-511
• [Wink 80] Winkowski, J., Behaviours of Concurrent Systems, Theoret. Comput. Sci. 12 (1980) 39-60
• [Wink 82] Winkowski, J., An Algebraic Description of System Behaviours, Theoret. Comput. Sci. 21 (1982) 315-340
• [Wink 03] Winkowski, J., An Algebraic Characterization of Independence of Petri Net Processes, Information Processing Letters 88 (2003), 73-81
• [Wink 05] 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
• [Wink 06] 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
• [Wink 07a]Winkowski, J., Behaviour Algebras, Fundamenta Informaticae 75 (2007), 537-560 http://www.ipipan.waw.pl/~wink/winkowski.htm
• [Wink 07b]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,
• [Wink 08] Winkowski, J., An Algebraic Framework for Defining Random Concurrent Behaviours, Fundamenta Informaticae 85 (2008), 481-496, http://www.ipipan.waw.pl/~wink/winkowski.htm,
• [WiMa 87] Winkowski, J., Maggiolo-Schettini, A., An Algebra of Processes, Journal of Comp. and System Sciences, Vol. 35, No. 2, October 1987, 206-228
• [WN 95]   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