Войти
В математике и информатике, теория трассировки призвана предоставить конкретную математическую основу для изучения параллельных вычислений и вычислений процесса. Основа обеспечивается алгебраическим определением свободного частично коммутативного моноида или моноида трассировки, или, что эквивалентно, исторического моноида, которое обеспечивает конкретную алгебраическую основу, аналогично тому, как свободный моноид обеспечивает основу для формальных языков.
Сила теории следов проистекает из того факта, что алгебра графов зависимостей (например, сети Петри ) изоморфен моноидам трассировки, и, таким образом, можно применять как инструменты алгебраического формального языка, так и инструменты из теории графов.
В то время как моноид следов изучался Пьером Картье и Домиником Фоата для их комбинаторики в 1960-х годах, теория следов была впервые сформулирована в 1970-х годах в попытке обойти некоторые проблемы теории параллельных вычислений, включая проблемы перемежения и недетерминированного выбора в отношении уточнения в вычислениях процессов.
