A generalization of traces. (English) Zbl 0731.68083

Summary: Traces describe the behaviour of distributed systems as labelled partial orders under the assumption that actions accessing the same object cannot occur simultaneously. We drop this assumption and show that for the resulting generalized traces will still have some results that intuitively justify the use of traces, namely: Traces corresponds to equivalence classes of global observations, and they correspond to tuples of local observations.


68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
Full Text: DOI EuDML


[1] 1. I. J. AALBERSBERG and G. ROZENBERG, Theory of Traces, Theor. Comp. Sci., 1988, 60, pp. 1-82. Zbl0652.68017 MR947532 · Zbl 0652.68017
[2] 2. E. BEST and C. LENGAUER, Semantic Independence, Sci. Comput. Prog., 1989, 13, pp. 23-50. Zbl0697.68021 MR1049349 · Zbl 0697.68021
[3] 3. P. CARTIER and D. FOATA, Problèmes Combinatoires de Commutation et Réarrengements, Lect. Notes in Math., No. 85, Springer, 1969. Zbl0186.30101 MR239978 · Zbl 0186.30101
[4] 4. M. CLERBOUT and M. LATTEUX, Partial Commutations and Faithful rational Transductions, Theor. Comp. Sci., 1985, 35, pp. 241-254. Zbl0548.68073 MR773455 · Zbl 0548.68073
[5] 5. R. CORI and D. PERRIN, Automates et Commutations partielles, R.A.I.R.O. - Informatique théoriqueet Application, 1985, 19, pp. 21-32. Zbl0601.68055 MR795769 · Zbl 0601.68055
[6] 6. G. LALLEMENT, Semigroups and Combinatorial Applications, John Wiley and Sons, New York, 1979. Zbl0421.20025 MR530552 · Zbl 0421.20025
[7] 7. A. MAZURKIEWICZ, Traces, Histories, Graphs: Instances of a Process Monoid, in M. P. CHYTIL et. al. Ed., Proceeding of the 11th Symposium on Mathematical Foundations of Computer Science (MFCS); Lect. Notes Comp. Sci., 1984, 176, pp. 115-133. Zbl0577.68061 MR783441 · Zbl 0577.68061
[8] 8. A. MAZURKIEWICZ, Trace Theory, in W. BRAUER et. al. Ed., Petri Nets: Applications and Relationships to other Models of Concurrency; Lect. Notes Comp. Sci., 1987, 255, pp. 279-324. Zbl0633.68051 MR902669 · Zbl 0633.68051
[9] 9. W. VOGLER, Executions of Petri Nets, in Proc. of 8th European Workshop on Application and Theory of Petri Nets, Zaragoza, 1987, pp. 551-564. Also in: Tech. report TUM-I8806, Techn. Univ. München, 1988.
[10] 10. J. WINKOWSKI, An Equivalence of Communicating Processes in Distributed Environments, Fundamenta Informaticae, 1989, XII, pp. 97-128. Zbl0674.68017 MR998423 · Zbl 0674.68017
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.