Teoria śladu

Aby zapoznać się z teorią śladu w składni języka naturalnego, zobacz Trace (lingwistyka) .

W matematyce i informatyce teoria śladów ma na celu zapewnienie konkretnych podstaw matematycznych do badania współbieżnych obliczeń i rachunków procesowych . Podstawą jest algebraiczna definicja wolnego częściowo przemiennego monoida lub monoida śladowego lub równoważnie monoid historii , która zapewnia konkretną podstawę algebraiczną, analogicznie do sposobu, w jaki wolny monoid zapewnia podstawę dla języki formalne .

Siła teorii śladów wynika z faktu, że algebra grafów zależności (takich jak sieci Petriego ) jest izomorficzna z algebrą monoidów śladowych, a zatem można zastosować zarówno narzędzia algebraicznego języka formalnego , jak i narzędzia teorii grafów .

Podczas gdy monoid śladowy był badany przez Pierre'a Cartiera i Dominique Foata pod kątem jego kombinatoryki w latach sześćdziesiątych XX wieku, teoria śladu została po raz pierwszy sformułowana przez Antoniego Mazurkiewicza w latach siedemdziesiątych XX wieku, próbując uniknąć niektórych problemów w teorii obliczeń współbieżnych, w tym problemy przeplatania i niedeterministycznego wyboru w odniesieniu do udokładniania w rachunku procesowym.

•   Volker Diekert, Grzegorz Rozenberg , wyd. Księga śladów , (1995) World Scientific, Singapur ISBN 981-02-2058-8
• Volker Diekert, Yves Metivier, „ Partial Commutation and Traces ”, w G. Rozenberg i A. Salomaa , redaktorzy, Handbook of Formal Languages , tom. 3 , Poza słowami . Springer-Verlag, Berlin, 1997.
•   Volker Diekert, Kombinatoryka na śladach , LNCS 454, Springer, 1990, ISBN 3-540-53031-2