En matemáticas e informática , 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 . El fundamento lo proporciona una definición algebraica del monoide libre parcialmente conmutativo o monoide de traza , o equivalentemente, el monoide histórico , que proporciona una base algebraica concreta, análoga a la forma en que el monoide libre proporciona el fundamento para los lenguajes formales .
El poder de la teoría de trazas surge del hecho de que el álgebra de los gráficos de dependencia (como las redes de Petri ) es isomorfa a la de los monoides de traza y, por lo tanto, se pueden aplicar tanto herramientas del lenguaje formal algebraico como herramientas de la teoría de grafos .
Si bien Pierre Cartier y Dominique Foata habían estudiado la traza monoide por su combinatoria en la década de 1960, la teoría de la traza 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, incluida la Problemas de entrelazado y elección no determinista con respecto al refinamiento en los cálculos de procesos.