トレース理論

数学とコンピュータサイエンスにおいて、トレース理論は並行計算とプロセス計算の研究のための具体的な数学的基礎を提供することを目指しています。この基礎は、自由部分可換モノイドまたはトレースモノイド、または同等の履歴モノイドの代数的定義によって提供され、自由モノイドが形式言語の基礎を提供するのと同様に、具体的な代数的基礎を提供します。

トレース理論の威力は、依存グラフ(ペトリ ネットなど)の代数がトレース モノイドの代数と同型であるという事実に由来しており、そのため、代数形式言語ツールとグラフ理論のツールの両方を適用できます。

トレースモノイドは 1960 年代にピエール カルティエとドミニク フォアタによってその組合せ論について研究されていましたが、トレース理論は 1970 年代にアントニ マズルキエヴィッチによって初めて定式化され、プロセス計算における改良に関するインターリーブや非決定論的選択の問題など、並行計算の理論におけるいくつかの問題を回避する試みでした。

• Volker Diekert、Grzegorz Rozenberg編『The Book of Traces』(1995) World Scientific、シンガポールISBN  981-02-2058-8
• Volker Diekert、Yves Metivier、「Partial Commutation and Traces」、G. Rozenberg およびA. Salomaa編、『Handbook of Formal Languages 』、第3巻、『Beyond Words』。Springer-Verlag、ベルリン、1997 年。
• Volker Diekert,トレースの組合せ論、LNCS 454、Springer、1990、ISBN 3-540-53031-2