Monoide de historia
En matemáticas e informática , un monoide de historia es una forma de representar las historias de los procesos informáticos que se ejecutan simultáneamente como una colección de cadenas , cada cadena representa la historia individual de un proceso. El monoide de historial proporciona un conjunto de primitivas de sincronización (como bloqueos , mutexes o uniones de subprocesos ) para proporcionar puntos de encuentro entre un conjunto de procesos o subprocesos que se ejecutan de forma independiente .
Los monoides históricos ocurren en la teoría de la computación concurrente y proporcionan una base matemática de bajo nivel para los cálculos de procesos , como CSP, el lenguaje de comunicación de procesos secuenciales , o CCS, el cálculo de comunicación de sistemas . Los monoides históricos fueron presentados por primera vez por MW Shields. [1]
Los monoides de historia son isomorfos a los monoides de traza (monoides parcialmente conmutativos libres ) y al monoide de los gráficos de dependencia . Como tales, son objetos libres y universales . El monoide de historia es un tipo de producto categórico semi-abeliano en la categoría de monoides.
denota una n -tupla de alfabetos (no necesariamente separados por pares) . Denote todas las combinaciones posibles de una cadena de longitud finita de cada alfabeto:
(En un lenguaje más formal, es el producto cartesiano de los monoides libres de . La estrella en superíndice es la estrella de Kleene ). La composición en el producto monoide es por componentes, de modo que, para
para todo en . Defina el alfabeto de unión como
