Теория следов
В математике и информатике теория следов призвана обеспечить конкретную математическую основу для изучения параллельных вычислений и исчисления процессов . Основа обеспечивается алгебраическим определением свободного частично коммутативного моноида или моноида следа , или, что эквивалентно, моноида истории , который обеспечивает конкретную алгебраическую основу, аналогично тому, как свободный моноид обеспечивает основу для формальных языков .
Сила теории следов проистекает из того факта, что алгебра графов зависимостей (таких как сети Петри ) изоморфна алгебре моноидов следов, и, таким образом, можно применять как инструменты алгебраического формального языка , так и инструменты из теории графов .
В то время как моноид следов изучался Пьером Картье и Домиником Фоата на предмет его комбинаторики в 1960-х годах, теория следов была впервые сформулирована Антони Мазуркевичем в 1970-х годах в попытке обойти некоторые проблемы теории параллельных вычислений, включая проблему проблемы чередования и недетерминированного выбора в отношении уточнения в расчетах процессов.
Ссылки [ править ]
- Фолькер Дикерт , Гжегож Розенберг , ред. Книга следов , (1995) World Scientific, Сингапур. ISBN 981-02-2058-8
- Фолькер Дикерт , Ив Метивье, « Частичная коммутация и следы », Г. Розенберг и А. Саломаа , редакторы, Справочник по формальным языкам , Vol. 3. За пределами слов . Шпрингер-Верлаг, Берлин, 1997 г.
- Фолькер Дикерт , Комбинаторика на следах , LNCS 454, Springer, 1990, ISBN 3-540-53031-2