Trace Theory | SpringerLink
Skip to main content
Springer Nature Link
Log in

Trace Theory

  • Reference work entry
Encyclopedia of Parallel Computing

Synonyms

Partial computation; Theory of Mazurkiewicz-traces

Definition

Trace Theory denotes a mathematical theory of free partially commutative monoids from the perspective of concurrent or parallel systems. Traces, or equivalently, elements in a free partially commutative monoid, are given by a sequence of letters (or atomic actions). Two sequences are assumed to be equal if they can be transformed into each other by equations of type ab=ba, where the pair (a,b) belongs to a predefined relation between letters. This relation is usually called partial commutation or independence. With an empty independence relation, that is, without independence, the setting coincides with the classical theory of words or strings.

Discussion

Introduction

The analysis of sequential programs describes a run of a program as a sequence of atomic actions. On an abstract level such a sequence is simply a string in a free monoid over some (finite) alphabet of letters. This purely abstract viewpoint embeds...

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 257400
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
JPY 228799
Price includes VAT (Japan)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Bibliography

  1. Anisimov AV, Knuth DE (1979) Inhomogeneous sorting. Int J Comput Inf Sci 8:255–260

    MATH  MathSciNet  Google Scholar 

  2. Cartier P, Foata D (1969) Problèmes combinatoires de commutation et réarrangements. Lecture notes in mathematics, vol 85. Springer, Heidelberg

    MATH  Google Scholar 

  3. Diekert V, Gastin P (2006) Pure future local temporal logics are expressively complete for Mazurkiewicz traces. Inf Comput 204:1597–1619. Conference version in LATIN 2004, LNCS 2976: 170–182, 2004

    Google Scholar 

  4. Diekert V, Horsch M, Kufleitner M (2007) On first-order fragments for Mazurkiewicz traces. Fundamenta Informaticae 80:1–29

    MATH  MathSciNet  Google Scholar 

  5. Diekert V, Rozenberg G (eds) (1995) The book of traces. World Scientific, Singapore

    Google Scholar 

  6. Gastin P, Kuske D (2007) Uniform satisfiability in pspace for local temporal logics over Mazurkiewicz traces. Fundam Inf 80(1–3): 169–197

    MATH  MathSciNet  Google Scholar 

  7. Gastin P, Petit A, Zielonka WL (2007) An extension of Kleene’s and Ochmański’s theorems to infinite traces. Theoret Comput Sci 125:167–204, x

    Google Scholar 

  8. Genest B, Gimbert H, Muscholl A, Walukiewicz I (2010) Optimal Zielonka-type construction of deterministic asynchronous automata. In: Abramsky S, Gavoille C, Kirchner C, Meyer auf der Heide F, Spirakis PG (eds) ICALP (2). Lecture notes in computer science, vol 6199. Springer, pp 52–63

    Google Scholar 

  9. Genest B, Kuske D, Muscholl A (2006) A Kleene theorem and model checking algorithms for existentially bounded communicating automata. Inf Comput 204:926–956. http://dx.doi.org/10.1016/j.ic.2006.01.005;DBLP, http://dblp.uni-trier.de

  10. Keller RM (1973) Parallel program schemata and maximal parallelism I. Fundamental results. J Assoc Comput Mach 20(3):514–537

    MATH  MathSciNet  Google Scholar 

  11. Mazurkiewicz A (1977) Concurrent program schemes and their interpretations. DAIMI Rep. PB 78, Aarhus University, Aarhus

    Google Scholar 

  12. Mazurkiewicz A (1987) Trace theory. In: Brauer W et al. (eds) Petri nets, applications and relationship to other models of concurrency. Lecture notes in computer science, vol 255. Springer, Heidelberg, pp 279–324

    Google Scholar 

  13. Ochmański E (Oct 1985) Regular behaviour of concurrent systems. Bull Eur Assoc Theor Comput Sci (EATCS) 27:56–67

    Google Scholar 

  14. Walukiewicz I (1998) Difficult configurations – on the complexity of LTrL. In: Larsen KG, et al. (eds) Proceedings of the 25th International Colloquium Automata, Languages and Programming (ICALP’98), Aalborg (Denmark). Lecture notes in computer science, vol 1443. Springer, Heidelberg, pp 140–151

    Google Scholar 

  15. Zielonka WL (1987) Notes on finite asynchronous automata. R.A.I.R.O. Informatique Théorique et Applications 21:99–135

    MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Formale Methoden der Informatik, Universität Stuttgart FMI, Universitätsstraße 38, 70569, Stuttgart, Germany

    Volker Diekert & Anca Muscholl

Authors
  1. Volker Diekert
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Anca Muscholl
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. University of Illinois at Urbana-Champaign, Urbana, IL, USA

    David Padua

Rights and permissions

Reprints and permissions

Copyright information

© 2011 Springer Science+Business Media, LLC

About this entry

Cite this entry

Diekert, V., Muscholl, A. (2011). Trace Theory. In: Padua, D. (eds) Encyclopedia of Parallel Computing. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-09766-4_491

Download citation

Publish with us

Policies and ethics

Search

Navigation