Multitraces, hypertraces and partial order semantics
Tóm tắt
In this paper, we consider a generalisation of a result due to the author which describes the way in which Mazurkiewicz trace languages serve to represent systems of labelled partial orders, as used in non-interleaving semantics of parallelism. The generalisation extends the class of partial order systems to exclude only a form of non-determinism. Their representation is in terms ofa generalisation of traces, also due to Mazurkiewicz, called multi traces.
Tài liệu tham khảo
[MiI89] Hennessy, M. C.:Algebraic Theory of Processes, MIT Press, 1988.
[Hoa85] Hoare, R.:Communicating Sequential Processes, Prentice Hall International Series in Computer Science, 1985.
[Kwi89] Kwiatkowska, M. Z.: Fairness for Non-Interleaving Concurrency, Ph.D. Thesis, Department of Computer Studies, University of Leicester, 1989.
[Maz77] Mazurkiewicz, A.: Concurrent Program Schema and their Interpretation. In:Proc. Aarhus Workshop on Verification of Parallel Programs, 1977.
[Maz90] Mazurkiewicz, A.: Multitraces: an Alternative Model of Non-Sequential Behaviour, 1990.
[Mil89] Milner, R.:Communication and Concurrency, Prentice Hall International Series in Computer Science, 1989.
[NPW79] Neilsen, M., Plotkin, G. and Winskel, G.: Petri Nets, Event Structures and Domains. In:Proc. Symp. on the Semantics of Concurrent Computation. Lecture Notes in Computer Science 70, Springer Verlag, 1979, pp. 266–283.
[Shi85] Shields, M. W.: Concurrent Machines.Computer Journal,28, 449–465 (1985).
[Shi88] Shields, M. W.: Behavioural Presentations. In:Proc. Workshop on Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency. Lecture Notes in Computer Science 354, Springer Verlag, 1988, pp. 671–689.
[Shi91a] Shields, M. W.: Infinite Multitraces, Infinite Hypertraces and Event Structures. Tech. Rep. CS-91-3, Department of Mathematical and Computing Sciences, University of Surrey, 1991.
[Shi91b] Shields, M. W.: Cube Complexes as Automata. Tech. Rep. CS-91-4, Department of Mathematical and Computing Sciences, University of Surrey, 1991.
[Shi93] Shields, M.W.:Elements of a Theory of Parallelism. MIT Press, to appear.
[Win83] Winskel, G.: Event Structure Semantics for CCS and Related Languages. Tech. Rep. DAIMIPB, Computer Science Department, University of Aarhus, April, 1983.