An algebraic framework for concurrent systems

Winkowski, J.

Artykuł - szczegóły

Tytuł artykułu

An algebraic framework for concurrent systems

Autorzy

Winkowski J.

Wybrane pełne teksty z tego czasopisma

http://ipipan.waw.pl/instytut/wydawnictwo/prace-ipi-pan

Identyfikatory

Warianty tytułu

O pewnych algebrach dla systemów współbieżnych

Języki publikacji

Abstrakty

The paper contributes with a concept of process viewed as a model of a run of a system (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 behavionrs 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, ie. 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 and operations on processes are represented by partially ordered multisets of a certain type and operations on such multisets.Processes in a universe of objects and the sequential composition of processes form a partial category, called a partial category of processes. Processes in a universe of objects and the operations of composing processes seąnentially and in parallel form a partial algebra, called an algebra of processes. Partial categories and algebras of processes belong to axiomatically defined classes of partial algebras, called behaviour-oriented partial categories and behaviour-oriented algebras. Some of behaviour-oriented partial categories and behaviour-oriented algebras can be represented as partial categories of proces es and algebras of processes. Partial categories and algebras of processes 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. The stucture reflexes the prefix order and makes the set of possible processes a directed complete poset. Partial categories and 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.

W pracy sformułowano pojęcie procesu rozumianego jako model przebiegu pewnego systemu (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 szeregowe składanie procesów tworzą kategorię częściową zwaną częściową kategorią procesów. Procesy w pewnym uniwersum obiektów i operacje szeregowego i równoległego składania procesów tworzą algebrę częściową, zwaną algebrą procesów. Częściowe kategorie i algebry procesów należą do aksjomatycznie definiowalnych klas algebr częściowych zwanych zachowaniowo-zorientowanymi kategoriami częściowymi i zachowaniowo-zorientowanymi algebrami. Pewne zachowaniowo-zorientowane kategorie częściowe i zachowaniowo-zorientowane algebry mogą być reprezetowane jako kategorie częściowe procesów i algebry procesów. Kategorie częściowe i algebry procesów 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 z pewną strukturą. Struktura ta odzwierciedla porządek prefiksowy procesów i czyni zbiór możliwych procesów zbiorem prefiksowo-zamkniętym i zawierającym kresy górne podzbiorów skierowanych. Kategorie częściowe procesów i algebry procesów mogą służyć m.in. do definiowania zachowań o stanach i procesach ze specyficznymi strukturami wewnętrznymi, do defniowania operacji na zachowaniach, podobnych do operacji w znanych rachunkach zachowań, oraz do definiowania zachowań losowych.

Słowa kluczowe

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

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

Wydawca

Instytut Podstaw Informatyki PAN

Czasopismo

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

Rocznik

2012

Tom

Nr 1023

Strony

1--134

Opis fizyczny

Bibliogr. 56 poz., rys.

Twórcy

autor

Winkowski J.

Instytut Podstaw Informatyki PAN, 01-248 Warszawa, Jana Kazimierza 5, wink@ipipan.waw.pl

Bibliografia

[AES 00] Alvarez-Manilla, M., Edalat, A., Saheb-Djahromi, N., An Extension Result for Continuous Valuations, J. London math. Soc. (2) 61 (2000) 629-640
[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
[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 mathematiąue, Livre I (Theorie des ensembles), Chapitre Ą (Structures), Act. Sci. Ind. 1258, Hermann, Paris, 1957
[BuDe 68] Bucur, I., 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., Aziomatizing Net Computations and Processes, in Proc. of 4th LICS Symposium, IEEE (1989) 175-185
[DS 01] Droste, M., Shortt, R. M., Continuous Petn Nets and Transition Systems, in Ehrig, H., et al. (Eds.), Unifying Petri Nets, Springer LNCS 2128 (2001) 457-484
[ER 90] Ehrenfeucht, A., Rozenberg, G., Partial 2-structures, Acta Informatica 27 (1990) 315-368
[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
[F 66] Feller, W., An Introduction to Probability Theory and Its Applications, Vol. II, John Wiley and Sons, Inc., 1966
[GHK 80] Gierz, G., Hofmann, k., H., Keimel, K., Lawson, J.,D., Mislove, M., and Scott, D.,S., A compendium of continuous lattices, Springer, Berlin, 1980
[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
[JP 89] Jones, C, Plotkin, G. D., A probabilistic powerdomain of evaluations, Proceedings of 4th LICS, 1989, 186-195
[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
[McL 71] Mac Lane, S., Categories for the Working Mathematician, Springer-Verlag New York Heidelberg Berlin 1971
[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,
[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
[NRT 90] Nielsen, M., Rozenberg, G., Thiagarajan, P. S., Elementary Transition Systems, Theoretical Computer Science (1992) 3-33
[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
[WW 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,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
[Wink 09a] Winkowski, J., An Algebraic Framework for Defining Behaviours of Concurrent Systems. Part 1: The Constructive Presentation, Fundamenta Informaticae 97 (2009), 235-273
[Wink 09b] Winkowski, J., An Algebraic Framework for Defining Behaviours of Concurrent Systems. Part 2: The Axiomatic Presentation, Fundamenta Informaticae 97 (2009), 439-470
[Wink 11] Winkowski, J., Multiplicative Transition Systems, Fundamenta Informaticae 109, No 2 (2011), 201-222, 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

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-article-BUJ8-0024-0071