Behaviour algebras

• Autorzy: Winkowski J.

Warianty tytułu

PL

Algebry zachowań

• Języki publikacji: EN

Abstrakty

EN

The paper is concerned with algebras whose elements can be used to represent runs of a system, called processes. These algebras, called behaviour algebras, are categories with respect to a partial binary operation called seąuential composition, and they arę partial monoids with respect to a partial binary operation called parallel composition. They are characterized by axioms such that their elements and operations can be represented as specific pomsets and specific operations on such pomsets. The respective representation theorem is universal in the sense that it is obtained without assuming a discrete nature of represented elements. In particular, it remains true for behaviour algebras with infinitely divisible elements, and thus also with elements which can represent continuous processes. An important consequence of the representation theorem is that elements of some subalgebras of behaviour algebras can be endowed in a consistent way with structures such as a graph structure etc.

PL

Praca dotyczy algebr częściowych, których elementy mogą służyć do reprezentowania procesów, tzn. przebiegów zachowania się systemów. Algebry te, zwane algebrami zachowań, są kategoriami ze względu na częściową operację binarną składania szeregowego, oraz są monoidami częściowymi ze względu na częściową operację binarną składania równoległego. Zostały one scharakteryzowane aksjomatycznie tak, że ich elementy i operacje można reprezentować klasami izomorficznych poetykietowanych zbiorów częściowo uporządkowanych i operacjami na takich klasach. Orzekające o tym twierdzenie o reprezentacji jest uniwersalne w tym sensie, że zostało uzyskane bez zakładania dyskretnej natury reprezentowanych elementów. W szczególności pozostaje prawdziwe dla algebr zachowań z nieskończenie podzielnymi elementami, które mogą reprezentować procesy ciągłe. Ważną konsekwencją tego twierdzenia jest też to, że elementy pewnych podalgebr algebr zachowań można wyposażać sensownie w struktury takie jak struktury grafowe itp.

Słowa kluczowe

EN

sequential composition; processes; states; parallel composition; category; partial monoid; structure

• Wydawca: Instytut Podstaw Informatyki PAN
• Czasopismo: Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk
• Rocznik: 2006
• Tom: Nr 992
• Strony: 1--36
• Opis fizyczny: Bibliogr. 19 poz.

Twórcy

autor

Winkowski J.

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

Bibliografia

• [BBM 02] 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
• [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., Seguential 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
• [DMM 89] Degano, P., Meseguer, J., Montanari, U., Axiomatizing Net Computations and Processes, in Proc. of 4th LICS Symposium, IEEE (1989) 175-185
• [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
• [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
• [MR 95] Montanari, U., Rossi, F., Contextual Nets, Acta Informatica 32 (1995) 545-596
• [Petri 77] Petri, C., A., Non-Sequential Processes, Interner Bericht ISF-77-5, Gesellschaft fuer Mathematik und Datenverarbeitung, 5205 St. Augustin, Germany (1977)
• [Plue 85] Pluenecke, H., K-density, N-density and finiteness properties, APN 84, Springer LNCS 188 (1985) 392-412
• [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
• [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 05a] Winkowski, J., Towards a Framework for Modelling Systems with Rich Structures of States and Processes, ICS PAS Report 973 (2004), Fundamenta Informaticae 68 (2005), 175-206, http://www.ipipan.waw.pl/~wink/winkowski.htm
• [Wink 05b] Winkowski, J., An Axiomatic Characterization of Algebras of Processes of Petri Nets, ICS PAS Report 987 (2005), http://www.ipipan.waw.pl/~wink/winkowski.htm