iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/BFb0013025
Basic notions of trace theory | SpringerLink
Skip to main content
Springer Nature Link
Log in

Basic notions of trace theory

  • Tutorials
  • Conference paper
  • First Online:
Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency (REX 1988)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 354))

Abstract

The concept of traces has been introduced for describing non-sequential behaviour of concurrent systems via its sequential observations. Traces represent concurrent processes in the same way as strings represent sequential ones. The theory of traces can be used as a tool for reasoning about nets and it is hoped that applying this theory one can get a calculus of the concurrent processes analogous to that available for sequential systems. The following topics will be discussed: algebraic properties of traces, trace models of some concurrency phenomena, fixed-point calculus for finding the behaviour of nets, modularity, and some applications of the presented theory.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

7. References

  1. AALBERSBERG IJ. J., ROZENBERG, G.: "Traces, dependency graphs and DNLC grammars”, Discrete Applied Mathematics 11 (1985) 299–306

    Article  Google Scholar 

  2. AALBERSBERG, IJ. J., ROZENBERG, G.: "Trace languages defined by context-free languages", manuscript, (1985)

    Google Scholar 

  3. AALBERSBERG, IJ. J., WELZL, E.: "Trace languages defined by regular string languages", to appear (1985)

    Google Scholar 

  4. BERTONI, A., BRAMBILLA, M., MAURI, G., SABADINI, N.: "An application of the theory of free partially commutative monoids: asymptotic densities of trace languages", Lecture Notes in Computer Science 118 (1981) 205–215

    Google Scholar 

  5. BERTONI, A. and GOLDWURM, M.: "Average analysis of an algorithm for a membership problem of trace languages", manuscript, (1986)

    Google Scholar 

  6. BERTONI, A., MAURI, G., SABADINI, N.: "A hierarchy of regular trace languages and some combinatorial applications", Proc. 2nd World Conf. on Math. at the Serv. of Men, Las Palmas (1982) 146–153

    Google Scholar 

  7. BERTONI, A., MAURI, G., SABADINI, N.: "Equivalence and membership problems for regular trace languages", Lecture Notes in Computer Science 140 (1982) 61–71

    Google Scholar 

  8. BERTONI, A., MAURI, G., SABADINI, N.: "Context — free trace languages", Proc. 7th CAAP, Lille (1982) 32–42

    Google Scholar 

  9. BERTONI, A., MAURI, G., SABADINI, N.: "Equivalence and membership problems for regular and context — free trace languages", manuscript (1982)

    Google Scholar 

  10. BERTONI, A., MAURI, G., SABADINI, N.: "Concurrency and commutativity", manuscript (1982)

    Google Scholar 

  11. BERTONI, A., MAURI, G., SABADINI, N.: "Unambiguous regular trace languages", Proc. Colloq. on Algebra, Combinat. and Comp. Science, Gyor (1983)

    Google Scholar 

  12. BERTONI, A., MAURI, G., SABADINI, N.: "Representation of prefixes of a trace and membership problem for context — free trace languages", manuscript (1985)

    Google Scholar 

  13. BEST, E., FERNANDEZ, C. and PLUNNECKE, H.: "Concurrent systems and processes", manuscript (1985)

    Google Scholar 

  14. CARPI, A. and LUCA, A. de: "Square — free words on partially commutative free monoids", Information Processing Letters 22 (1986) 125–132

    Article  Google Scholar 

  15. CARTIER, P. and FOATA, D.: "Problemes combinatoires de commutation et rearrangements", Lecture Notes in Mathematics 85 (1969)

    Google Scholar 

  16. CLERBOUT, M. and LATTEUX, M.: "Partial commutations and faithful rational transductions", Theoretical Computer Science 34 (1984) 241–254

    Article  Google Scholar 

  17. CLERBOUT, M. and LATTEUX, M.: "Semi — commutations", Techn. Rep. IT-63-84, Equipe Lilloise d'Inform. Theor., Univers. de Lille 1, Villeneuve d'Ascq. (1984)

    Google Scholar 

  18. CORI, R. and METIVIER, Y.: "Recognizable subsets of some partially abelian monoids", Theoretical Computer Science 35 (1984) 179–189

    Article  Google Scholar 

  19. CORI, R. and PERRIN, D.: "Automates and commutations partielles", RAIRO Informatique Theorique 19 (1985) 21–32

    Google Scholar 

  20. DUBOC, C.: "Some properties of commutation in free partially commutative monoids", Information Processing Letters 20 (1985) 1–4

    Article  Google Scholar 

  21. DUBOC, C.: "Equations in free partially commutative monoids", Lecture Notes in Computer Science 210 (1986) 192–202

    Google Scholar 

  22. EHRENFEUCHT, A., ROZENBERG, G.: "On the Structure of Dependence Graphs", Rapport 87-02, Dept. of Computer Science, University of Leiden (1987)

    Google Scholar 

  23. FLE, M. P. and ROUCAIROL, G.: "On serializability of iterated transactions", Proc. ACM SIGACT-SIGOPS Symp. on Princ. of Distrib. Comp., Ottawa (1982) 194–200

    Google Scholar 

  24. FLE, M. P. and ROUCAIROL, G.: "Fair serializability of iterated transactions using FIFO — nets", Lecture Notes in Computer Science 188 (1985) 154–168

    Google Scholar 

  25. FLE, M. P. and ROUCAIROL, G.: "Maximal serializability of iterated transactions", Theoretical Computer Science 38 (1985) 1–16

    Article  Google Scholar 

  26. FOATA, D.: "Rearrangements of words", in M. Lothaire: Combinatorics on words, Addison-Wesley, Reading, (1983) Chapter 10

    Google Scholar 

  27. GRABOWSKI, J.: "On partial languages", Fundamenta Informaticae 4 (1981) 427–498

    Google Scholar 

  28. GYORY, G., KNUTH, E., RONYAI, L.: "Grammatical projections 1. Elementary constructions", Working Paper II/3, MTA SZTAKI, Budapest (1979)

    Google Scholar 

  29. JANICKI, R.: "Synthesis of concurrent schemes", Lecture Notes in Computer Science 64 (1978) 298–307

    Google Scholar 

  30. JANICKI, R.: "On the design of concurrent systems", Proc. 2nd Intern. Conf. on Distrib. Comp. Systems, Paris (1981) 455–466

    Google Scholar 

  31. JANICKI, R.: "Mazurkiewicz traces semantics for communicating sequential processes", Proc. 5th European Workshop on Appl. and Theory of Petri Nets, Aarhus (1984) 50–70

    Google Scholar 

  32. JANICKI, R.: "Trace semantics for communicating sequential processes", Techn. Rep. R-85-12, Inst. for Elektr. Syst., Alaborg Univ., Aalborg (1985)

    Google Scholar 

  33. KELLER, R. M.: "A solvable program-schema equivalence problem", Proc. 5th Ann. Princeton Conf. on Inf. Sciences and Systems, Princeton (1971) 301–306

    Google Scholar 

  34. KNUTH, E.: "Petri nets and regular trace languages", manuscript (1978)

    Google Scholar 

  35. KNUTH, E.: "Petri nets and trace languages", Proc. 1st Europ. Conf. on Parallel and Distr. Processing, Toulouse (1979) 51–56

    Google Scholar 

  36. KNUTH, E. and GYORY, G.: "Paths and traces", Computational Linguistics and Computer Languages 13 (1979) 31–42

    Google Scholar 

  37. LAUER, P.E., SHIELDS, M.W., BEST, E.: "Formal Theory of the Basic COSY Notation", Technical Report 143, Computing Laboratory, University of Newcastle upon Tyne (1979)

    Google Scholar 

  38. LEVI F. W.: "On semigroups", Bull. of the Calcutta Math. Soc. 36 (1944) 141–146

    Google Scholar 

  39. MAZURKIEWICZ, A.: "Concurrent program schemes and their interpretations", DAIMI Rep. PB-78, Aarhus Univ., Aarhus (1977)

    Google Scholar 

  40. MAZURKIEWICZ, A.: "Equational semantics of concurrent systems", Proc. 8th Spring School on Comp. Sci., Colleville sur mer (1980)

    Google Scholar 

  41. MAZURKIEWICZ, A.: "A calculus of execution traces for concurrent systems", manuscript (1983)

    Google Scholar 

  42. MAZURKIEWICZ, A.: "Traces, histories, graphs: instances of a process monoid", Lecture Notes in Computer Science 176 (1984) 115–133

    Google Scholar 

  43. MAZURKIEWICZ, A.: "Semantics of concurrent systems: a modular fixed-point trace approach", Lecture Notes in Computer Science 188 (1985) 353–375

    Google Scholar 

  44. MAZURKIEWICZ, A.: "Trace Theory", Advances in Petri Nets 1986, Part II, Proceedings of an Advanced Course Lecture Notes in Computer Science 255 (1987) 279–324

    Google Scholar 

  45. METIVIER, Y.: "Une condition suffisante de reconaissabilite dans un monoide partiellement commutatif", Techn. Rep. 8417, U.E.R. de Math. et d'Inform., Univ. de Bordeaux, Bordeaux (1984)

    Google Scholar 

  46. METIVIER, Y.: "Sous-ensemble reconnaisable d'un monoide partiellment commutatif libre", manuscript (1985)

    Google Scholar 

  47. NIELSEN, M., PLOTKIN, G., WINSKEL, G.: "Petri nets, event structures and domains, Part 1", Theoretical Computer Science 13 (1981) 85–108

    Article  Google Scholar 

  48. OCHMANSKI, E.: "Regular trace languages", Ph. D. Thesis (1985) (summary in Bull. of EATCS 27, 1985)

    Google Scholar 

  49. Perrin, D.: "Words over a partially commutative alphabet", NATO ASI Series F12 (1985) 329–340

    Google Scholar 

  50. PETRI, C.A.: "Concepts of Net Theory", Proceedings of the Symposium and Summer School on MFCS'73, High Tatras (1973)

    Google Scholar 

  51. PETRI, C.A.: "Non-Sequential Processes", GMD-ISF Report 77.05, Gesellschaft fuer Mathematik und Datenverarbeitung mbH Bonn (1977)

    Google Scholar 

  52. REISIG, W.: "Petri nets — an introduction", EATCS Monographs on Theoretical Computer Science, Springer Verlag (1985)

    Google Scholar 

  53. REM, M.: "Concurrent Computations and VLSI Circuits", Control Flow and Data Flow: Concepts of Distributed Programming (M. Broy, editor), Springer (1985) 399–437

    Google Scholar 

  54. ROZENBERG, G.: "Behaviour of elementary net systems", Advances in Petri Nets 1986, Part I, Proceedings of an Advanced Course Lecture Notes in Computer Science 254 (1987) 60–94

    Google Scholar 

  55. ROZENBERG, G., THIAGARAJAN, P.S.: "Petri Nets: Basic Notions, Structure and Behaviour", Lecture Notes in Computer Science 224, (1986) 585–668

    Google Scholar 

  56. RYTTER, W.: "Some properties of trace languages", Fundamenta Informaticae 7 (1984) 117–127

    Google Scholar 

  57. SAKAROVITCH, J.: "On regular trace languages", to appear (1986)

    Google Scholar 

  58. SHIELDS, M.W.: "Adequate Path Expressions", Lecture Notes in Computer Science 70, (1979) 249–265

    Google Scholar 

  59. SHIELDS, M.W.: "Non-Sequential Behaviour", Part 1, Int. Report CSR-120-82, Dept. of Computer Science, University of Edinburgh (1982)

    Google Scholar 

  60. SHIELDS, M.W.: "Concurrent Machines", The Computer Journal 28, Nr. 5 (1988) 449–466

    Article  Google Scholar 

  61. STARKE, P. H.: "Processes in Petri Nets", Elektron. Inf. und Kyb. 17 (1981)

    Google Scholar 

  62. STARKE, P. H.: "Traces and semiwords", Lecture Notes in Computer Science 208 (1985) 332–349

    Google Scholar 

  63. SZIJARTO, M.: "A classification and closure properties of languages for describing concurrent system behaviours", Fundamenta Informaticae 4 (1981) 531–549

    Google Scholar 

  64. TARLECKI, A.: "Notes on the implementability of formal languages by concurrent systems", ICS PAS Report 481, Inst. of Comp. Science, Polish Academy of Sciences, Warszawa (1982)

    Google Scholar 

  65. THIAGARAJAN, P.S.: "Elementary net systems", Advances in Petri Nets 1986, Part I, Proceedings of an Advanced Course Lecture Notes in Computer Science 254 (1987) 26–59

    Google Scholar 

  66. ZIELONKA, W.: "Proving assertions about parallel programs by means of traces", ICS PAS Report 424, Inst. of Comp. Science, Polish Academy of Sciences, Warszawa (1980)

    Google Scholar 

  67. ZIELONKA, W.: "The notes on finite state asynchronous automata and trace languages", manuscript (1982)

    Google Scholar 

  68. ZIELONKA, W.: "Notes on Finite Asynchronous Automata", Informatique Theorique et Applications 21, Nr. 2, (1987) 99–135

    Google Scholar 

  69. ZUIDWEG, H.: "Trace approach to synchronic distances" (manuscript), University of Leiden, Leiden (1986)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Polish Academy of Sciences, Institute of Computer Science, P.O.Box 22, PL-00-901, Warsaw

    Antoni Mazurkiewicz

Authors
  1. Antoni Mazurkiewicz
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

J. W. de Bakker W. -P. de Roever G. Rozenberg

Rights and permissions

Reprints and permissions

Copyright information

© 1989 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Mazurkiewicz, A. (1989). Basic notions of trace theory. In: de Bakker, J.W., de Roever, W.P., Rozenberg, G. (eds) Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency. REX 1988. Lecture Notes in Computer Science, vol 354. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0013025

Download citation

  • DOI: https://doi.org/10.1007/BFb0013025

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-51080-2

  • Online ISBN: 978-3-540-46147-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation