×

Sheaf-semantics for concurrent interacting objects. (English) Zbl 0763.18005

Much work in the semantics of concurrent systems has been based on notions of observations of system behaviours. A fundamental property of concurrency theory is the great variety of possible observations. The large variety of possible observations depends on the fact that at present there is no widely accepted metalanguage to describe concurrent systems and their behaviours in an abstract setting, and that different aspects of system behaviour are important in different applications.
The definition of a uniform metalanguage to describe concurrent systems and their behaviours is the main concern of this paper. The basic idea is that the observation of the possible behaviours of an independent component of a system (called object) can be formalized as a function to some set of observable attributes. This key idea leads to the notion of sheaf: a sheaf is a collection of the possible behaviours of an object. The main feature of concurrent systems is that they consist of independent components (objects) interacting with each other along their computations. Using concepts of sheaf theory, the author shows that interacting concurrent systems can be described as diagrams of sheaves (connections among conponents are obtained by elegant categorical constructions), and that computations of a concurrent system are described, categorically, by taking the limit of the diagram. The main features and the insights which could be gained by using the sheaf approach are illustrated with several interesting examples.

MSC:

18F20 Presheaves and sheaves, stacks, descent conditions (category-theoretic aspects)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
18A35 Categories admitting limits (complete categories), functors preserving limits, completions
Full Text: DOI

References:

[1] Monteiro, A sheaf-theoretic model of concurrency (1986)
[2] Goguen, Global systems Dynamics pp 112– (1971)
[3] Barwise, Situationsm and Attitudes (1983)
[4] Milner, A Calculus of Communicating Systems 92 (1980) · doi:10.1007/3-540-10235-3
[5] Barr, Category Theroy for Computing Science (1990) · Zbl 0714.18001
[6] Meseguer, Proceedings, Symposium on Logic in Computer Science (1988)
[7] Barr, Toposes, Triples and Theories 278 (1984)
[8] Lilus, Sheaf semantics for Petri nets (1991)
[9] Agha, Actors: A Model of Concurrent Computation in distributed Systems (1986)
[10] DOI: 10.1007/BFb0061291 · doi:10.1007/BFb0061291
[11] Mac Lane, Categories for the Working Mathematician (1971) · doi:10.1007/978-1-4612-9839-7
[12] Jocob, Proceedings, 1988 Computer Security Foundations Workshop pp 98– (1988)
[13] Hoare, Communicating sequential Processes (1985) · Zbl 0637.68007
[14] Grothendieck, Revětements étales et gruope fondamental, Séminaire de Géométrie Algébraique du Bois-Marie 1960/61, Exposé VI (1963)
[15] DOI: 10.1016/0040-9383(65)90066-2 · Zbl 0132.17605 · doi:10.1016/0040-9383(65)90066-2
[16] Gordon, Formal Aspects of VLSI Design (1986)
[17] Goldblatt, Topoi the Categorial Analysis of Logic (1979)
[18] Goguen, Proceedings, IFIP TC2 Conference on Object Oriented Databases (1991)
[19] Goguen, current Trends in Programming Methodology, IV pp 80– (1976)
[20] Goguen, Technical Report SRI-CSL-89-10, SRI International, Computer Science Lab (1983)
[21] Goguen, Research Directions in Object-Oriented Programming pp 417–477– (1987)
[22] Goguen, Proceedings, 1982 Symposium on Security and Privacy pp 75– (1984)
[23] Stavridou, Proceedings, Advanced Research Workshop on Correct Hardware Design Methodologies pp 117– (1991)
[24] Ehrich, Journal of Information Processing and Cyberntics 261 pp 33–48– (1990)
[25] Star, Distributed Artificial Intelligence 3 (1988)
[26] Reisig, Petri Nets: An Introduction (1986)
[27] Ehrich, Categorical Methods in Computer Science with Aspects from Topology 393 pp 142– (1989) · doi:10.1007/3-540-51722-7_9
[28] Ehrich, Proceedings, REX Workshop on Stepwise Refinement of Distributed Systems: Models, Formalisms, correctness 430 pp 239– (1990) · doi:10.1007/3-540-52559-9_67
[29] Pierce, A taste of category theory for computer scientists (1990)
[30] DOI: 10.1007/BFb0019445 · doi:10.1007/BFb0019445
[31] O’Halloran, A callculus of information flow (1990)
[32] Dretske, Knowledge and the Flow of Information (1981)
[33] Goguen, Proceedings, 1982 Symposium on Security and Privacy pp 11– (1982)
[34] Goguen, The Rewrite Rule Machine, 1988 (1989)
[35] Goguen, Applied General Systems Research pp 257– (1978)
[36] Goguen, Concurrency: Theory, Language and Architecturm 491 pp 216– (1991)
[37] Goguen, Mathematical Structures in Computer science 1 pp 49– (1991)
[38] DOI: 10.1080/03081077408960783 · Zbl 0336.18001 · doi:10.1080/03081077408960783
[39] Yosida, Functional Analysis (1968) · doi:10.1007/978-3-662-11791-0
[40] Goguen, Advances in Cybernetics and systems Research pp 121– (1973)
[41] DOI: 10.1016/0890-5401(90)90058-P · Zbl 0719.68010 · doi:10.1016/0890-5401(90)90058-P
[42] Tennison, Sheaf Theory pp 20– (1975) · doi:10.1017/CBO9780511661761
[43] DOI: 10.1016/0304-3975(86)90018-6 · Zbl 0618.68062 · doi:10.1016/0304-3975(86)90018-6
[44] Tarlecki, Theoretical Computer Science 91 pp 239– (1991) · Zbl 0753.00030
[45] DOI: 10.1016/S0019-9958(84)80025-X · Zbl 0597.68027 · doi:10.1016/S0019-9958(84)80025-X
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.