En matemáticas y ciencias de la computación , la teoría de trazas tiene como objetivo proporcionar una base matemática concreta para el estudio de la computación concurrente y los cálculos de procesos . La base la proporciona una definición algebraica del monoide parcialmente conmutativo libre o monoide de trazas , o equivalentemente, el monoide histórico , que proporciona una base algebraica concreta, análoga a la forma en que el monoide libre proporciona la base para los lenguajes formales .
El poder de la teoría de trazas surge del hecho de que el álgebra de gráficos de dependencia (como las redes de Petri ) es isomorfa a la de los monoides de trazas y, por lo tanto, se pueden aplicar tanto herramientas del lenguaje formal algebraico como herramientas de la teoría de grafos .
Si bien el monoide de traza había sido estudiado por Pierre Cartier y Dominique Foata por su combinatoria en la década de 1960, la teoría de trazas fue formulada por primera vez por Antoni Mazurkiewicz en la década de 1970, en un intento de evadir algunos de los problemas de la teoría de la computación concurrente, incluidos los problemas de entrelazado y elección no determinista con respecto al refinamiento en los cálculos de procesos.