En matemáticas e informática , un monoide de historia es una forma de representar las historias de 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 histórico proporciona un conjunto de primitivas de sincronización (como bloqueos , mutex 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 los procesos secuenciales de comunicación , o CCS, el cálculo de los sistemas de comunicación . Los monoides históricos fueron presentados por primera vez por MW Shields. [1]
Los monoides históricos son isomorfos para trazar monoides ( monoides parcialmente conmutativos libres ) y para el monoide de las gráficas de dependencia . Como tales, son objetos libres y universales . El monoide histórico es un tipo de producto categórico semi-abeliano en la categoría de monoides.
Monoides de producto y proyección.
Dejar
denotar una n -tupla de alfabetos (no necesariamente separados por pares) . Dejar denotar 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 del. La estrella en superíndice es la estrella de Kleene .) La composición del producto monoide es por componentes, de modo que, para
y
luego
para todos en . Defina el alfabeto de la unión como
(La unión aquí es la unión de conjuntos , no la unión disjunta ). Dada cualquier cadena, podemos seleccionar solo las letras en algunos usando la proyección de cuerda correspondiente . Una distribución es el mapeo que opera en con todos los , separándolo en componentes en cada monoide libre:
Historias
Para cada , la tupla se llama la historia elemental de a . Sirve como función indicadora para la inclusión de una letra a en un alfabeto.. Es decir,
dónde
Aquí, denota la cadena vacía . El monoide de la historia es el submonoide del producto monoide generado por las historias elementales: (donde la estrella en superíndice es la estrella de Kleene aplicada con una definición de composición por componentes como se indica arriba). Los elementos dese llaman historias globales , y las proyecciones de una historia global se llaman historias individuales .
Conexión a la informática
El uso de la palabra historia en este contexto y la conexión con la computación concurrente se pueden entender de la siguiente manera. Una historia individual es un registro de la secuencia de estados de un proceso (o hilo o máquina ); el alfabeto es el conjunto de estados del proceso.
Una letra que aparece en dos o más alfabetos sirve como una primitiva de sincronización entre las diversas historias individuales. Es decir, si tal letra aparece en una historia individual, también debe aparecer en otra historia, y sirve para "unirlos" o "reunirlos".
Considere, por ejemplo, y . El alfabeto de la unión es, por supuesto. Las historias elementales son, , , y . En este ejemplo, una historia individual del primer proceso podría ser mientras que la historia individual de la segunda máquina podría ser . Ambas historias individuales están representadas por la historia global., ya que la proyección de esta cadena en los alfabetos individuales produce las historias individuales. En la historia global, las letras y se puede considerar conmutar con las letras y , en el sentido de que estos se pueden reorganizar sin cambiar las historias individuales. Tal conmutación es simplemente una declaración de que el primer y segundo proceso se ejecutan simultáneamente y no están ordenados entre sí; no han intercambiado (todavía) ningún mensaje ni realizado ninguna sincronización.
La carta sirve como un primitivo de sincronización, ya que su aparición marca un punto en la historia tanto global como individual, que no se puede conmutar. Así, mientras las letras y se puede reordenar pasado y , no se pueden reordenar más allá . Por tanto, la historia global y la historia global ambos tienen como historias individuales y , indicando que la ejecución de puede suceder antes o después . Sin embargo, la carta está sincronizando, de modo que está garantizado que sucederá después , aunque está en un proceso diferente al.
Propiedades
Un monoide histórico es isomorfo a un monoide traza y, como tal, es un tipo de producto categórico semi-abeliano en la categoría de monoides. En particular, la historia monoide es isomorfo a la traza monoide con la relación de dependencia dada por
En términos simples, esta es solo la declaración formal de la discusión informal dada anteriormente: las letras en un alfabeto se puede reordenar conmutativamente más allá de las letras en un alfabeto , a menos que sean letras que aparecen en ambos alfabetos. Por lo tanto, los rastros son exactamente historias globales y viceversa.
Por el contrario, dado cualquier rastro de monoide , se puede construir un monoide de historia isomorfo tomando una secuencia de alfabetos dónde abarca todos los pares en .
Notas
- ^ MW Shields "Máquinas concurrentes", Computer Journal , (1985) 28 págs. 449–465.
Referencias
- Antoni Mazurkiewicz, "Introducción a la teoría de las huellas ", págs. 3-41, en El libro de las huellas , V. Diekert, G. Rozenberg, eds. (1995) World Scientific, Singapur ISBN 981-02-2058-8
- Volker Diekert, Yves Métivier, " Partial Commutation and Traces ", en G. Rozenberg y A. Salomaa , editores, Handbook of Formal Languages , vol. 3 , Más allá de las palabras, páginas 457–534. Springer-Verlag, Berlín, 1997.