Spårteori

Inom matematik och datavetenskap syftar spårteori till att ge ett konkret matematiskt underlag för studiet av samtidiga beräkningar och processkalkyler . Underlaget tillhandahålls av en algebraisk definition av den fria partiellt kommutativa monoiden eller spårmonoiden , eller ekvivalent, historiemonoiden , som ger en konkret algebraisk grund, analogt med det sätt som den fria monoiden tillhandahåller underbyggnaden för formella språk .

Kraften i spårteorin härrör från det faktum att algebra för beroendegrafer (som Petrinets ) är isomorf till den för spårmonoider, och därför kan man tillämpa både algebraiska formella språkverktyg, såväl som verktyg från grafteorin .

Medan spårmonoiden hade studerats av Pierre Cartier och Dominique Foata för dess kombinatorik på 1960-talet, formulerades spårteorin först av Antoni Mazurkiewicz på 1970-talet, i ett försök att undvika några av problemen i teorin om samtidig beräkning, inklusive problem med interfoliering och icke-deterministiskt val med avseende på förfining i processkalkyler.

Volker Diekert, Grzegorz Rozenberg , red. The Book of Traces , (1995) World Scientific, Singapore ISBN 981-02-2058-8
Volker Diekert, Yves Metivier, " Partial Commutation and Traces ", I G. Rozenberg och A. Salomaa , redaktörer, Handbook of Formal Languages , Vol. 3 , Beyond Words . Springer-Verlag, Berlin, 1997.
Volker Diekert, Combinatorics on traces , LNCS 454, Springer, 1990, ISBN 3-540-53031-2