Monoide de traza

Generalización de cadenas en informática

En informática , una traza es una clase de equivalencia de cadenas , en la que se permite que ciertas letras de la cadena conmuten , pero otras no. Las trazas generalizan el concepto de cadenas al relajar el requisito de que todas las letras tengan un orden definido, permitiendo en cambio ordenaciones indefinidas en las que podrían tener lugar ciertas reorganizaciones. De manera opuesta, las trazas generalizan el concepto de conjuntos con multiplicidades al permitir especificar algún orden incompleto de las letras en lugar de requerir una equivalencia completa bajo todas las reorganizaciones. El monoide de traza o monoide parcialmente conmutativo libre es un monoide de trazas.

Pierre Cartier y Dominique Foata introdujeron las trazas en 1969 para proporcionar una prueba combinatoria del teorema maestro de MacMahon . Las trazas se utilizan en teorías de computación concurrente , donde las letras conmutativas representan partes de un trabajo que pueden ejecutarse independientemente unas de otras, mientras que las letras no conmutativas representan bloqueos, puntos de sincronización o uniones de subprocesos . ^[1]

El monoide de traza se construye a partir del monoide libre (el conjunto de todas las cadenas de longitud finita) de la siguiente manera. Primero, los conjuntos de letras conmutativas se dan mediante una relación de independencia . Estas inducen una relación de equivalencia de cadenas equivalentes; los elementos de las clases de equivalencia son las trazas. La relación de equivalencia luego divide los elementos del monoide libre en un conjunto de clases de equivalencia; el resultado sigue siendo un monoide; es un monoide cociente ahora llamado monoide de traza . El monoide de traza es universal , en el sentido de que todos los monoides homomórficos de dependencia (ver más abajo) son de hecho isomorfos .

Los monoides de traza se utilizan comúnmente para modelar el cálculo concurrente , formando la base para los cálculos de procesos . Son el objeto de estudio en la teoría de trazas . La utilidad de los monoides de traza proviene del hecho de que son isomorfos al monoide de los gráficos de dependencia ; lo que permite aplicar técnicas algebraicas a los gráficos , y viceversa. También son isomorfos a los monoides históricos , que modelan el historial de cálculo de procesos individuales en el contexto de todos los procesos programados en una o más computadoras.

Rastro

Sea α el monoide libre de un conjunto de generadores , es decir, el conjunto de todas las cadenas escritas en el alfabeto . El asterisco es una notación estándar para la estrella de Kleene . Una relación de independencia en el alfabeto induce entonces una relación binaria simétrica en el conjunto de cadenas : dos cadenas están relacionadas, si y solo si existen , y un par tal que y . Aquí, y se entiende que son cadenas (elementos de ), mientras que y son letras (elementos de ). ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma }$ ${\displaystyle I}$ ${\displaystyle \Sigma }$ ${\displaystyle \sim }$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle u,v}$ ${\displaystyle u\sim v,}$ ${\displaystyle x,y\in \Sigma ^{*}}$ ${\displaystyle (a,b)\in I}$ ${\displaystyle u=xaby}$ ${\displaystyle v=xbay}$ ${\displaystyle u,v,x}$ ${\displaystyle y}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle \Sigma }$

La traza se define como el cierre transitivo reflexivo de . La traza es, por tanto, una relación de equivalencia en y se denota por , donde es la relación de dependencia correspondiente a y Diferentes independencias o dependencias darán diferentes relaciones de equivalencia. ${\displaystyle \sim }$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \equiv _{D}}$ ${\displaystyle D}$ ${\displaystyle I.}$ ${\displaystyle D=(\Sigma \times \Sigma )\setminus I}$ ${\displaystyle I=(\Sigma \times \Sigma )\setminus D.}$

El cierre transitivo implica que si y solo si existe una secuencia de cadenas tal que y para todo . La traza es estable bajo la operación monoide en , es decir, la concatenación , y por lo tanto es una relación de congruencia en ${\displaystyle u\equiv _{D}v}$ ${\displaystyle (w_{0},w_{1},\cdots ,w_{n})}$ ${\displaystyle u\sim w_{0},}$ ${\displaystyle v\sim w_{n},}$ ${\displaystyle w_{i}\sim w_{i+1}}$ ${\displaystyle 0\leq i<n}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \equiv _{D}}$ ${\displaystyle \Sigma ^{*}.}$

El monoide traza, comúnmente denotado como , se define como el monoide cociente ${\displaystyle \mathbb {M} (D)}$

${\displaystyle \mathbb {M} (D)=\Sigma ^{*}/\equiv _{D}.}$

El homomorfismo

${\displaystyle \phi _{D}:\Sigma ^{*}\to \mathbb {M} (D)}$

Se denomina comúnmente homomorfismo natural u homomorfismo canónico . El hecho de que los términos natural o canónico sean merecidos se desprende del hecho de que este morfismo incorpora una propiedad universal, como se analiza en una sección posterior.

También se encontrará el monoide de traza denotado como donde es la relación de independencia. También se puede encontrar la relación de conmutación utilizada en lugar de la relación de independencia; se diferencia de la relación de independencia al incluir también todos los elementos diagonales de ya que las letras "conmutan consigo mismas" en un monoide libre de cadenas de esas letras. ${\displaystyle M(\Sigma ,I)}$ ${\displaystyle I}$ ${\textstyle \Sigma \times \Sigma }$

Ejemplos

Consideremos el alfabeto . Una posible relación de dependencia es ${\displaystyle \Sigma =\{a,b,c\}}$

${\displaystyle {\begin{matrix}D&=&\{a,b\}\times \{a,b\}\quad \cup \quad \{a,c\}\times \{a,c\}\\&=&\{a,b\}^{2}\cup \{a,c\}^{2}\\&=&\{(a,b),(b,a),(a,c),(c,a),(a,a),(b,b),(c,c)\}.\end{matrix}}}$

La independencia correspondiente es

${\displaystyle I_{D}=\{(b,c)\,,\,(c,b)\}.}$

Por lo tanto, las letras se conmutan. Así, por ejemplo, una clase de equivalencia de traza para la cadena sería ${\displaystyle b,c}$ ${\displaystyle abababbca}$

${\displaystyle [abababbca]_{D}=\{abababbca\,,\;abababcba\,,\;ababacbba\}}$

y la clase de equivalencia sería un elemento del monoide traza. ${\displaystyle [abababbca]_{D}}$

Propiedades

La propiedad de cancelación establece que la equivalencia se mantiene bajo la cancelación derecha . Es decir, si , entonces . Aquí, la notación denota cancelación derecha, la eliminación de la primera ocurrencia de la letra a de la cadena w , comenzando desde el lado derecho. La equivalencia también se mantiene mediante la cancelación izquierda. Se deducen varios corolarios: ${\displaystyle w\equiv v}$ ${\displaystyle (w\div a)\equiv (v\div a)}$ ${\displaystyle w\div a}$

• Incrustar: si y solo si para las cadenas x e y . Por lo tanto, el monoide de traza es un monoide sintáctico. ^{[ non sequitur Ver Discusión:Monoide de traza#Como Monoides Sintácticos ]} ${\displaystyle w\equiv v}$ ${\displaystyle xwy\equiv xvy}$
• Independencia: si y , entonces a es independiente de b . Es decir, . Además, existe una cadena w tal que y . ${\displaystyle ua\equiv vb}$ ${\displaystyle a\neq b}$ ${\displaystyle (a,b)\in I_{D}}$ ${\displaystyle u\equiv wb}$ ${\displaystyle v\equiv wa}$
• Regla de proyección: la equivalencia se mantiene bajo la proyección de cuerdas , de modo que si , entonces . ${\displaystyle w\equiv v}$ ${\displaystyle \pi _{\Sigma }(w)\equiv \pi _{\Sigma }(v)}$

Una forma fuerte del lema de Levi se aplica a las trazas. En concreto, si para las cadenas u , v , x , y , entonces existen cadenas y tales que para todas las letras y tales que aparecen en y aparecen en , y ${\displaystyle uv\equiv xy}$ ${\displaystyle z_{1},z_{2},z_{3}}$ ${\displaystyle z_{4}}$ ${\displaystyle (w_{2},w_{3})\in I_{D}}$ ${\displaystyle w_{2}\in \Sigma }$ ${\displaystyle w_{3}\in \Sigma }$ ${\displaystyle w_{2}}$ ${\displaystyle z_{2}}$ ${\displaystyle w_{3}}$ ${\displaystyle z_{3}}$

${\displaystyle u\equiv z_{1}z_{2},\qquad v\equiv z_{3}z_{4},}$

${\displaystyle x\equiv z_{1}z_{3},\qquad y\equiv z_{2}z_{4}.}$^[2]

Propiedad universal

Un morfismo de dependencia (con respecto a una dependencia D ) es un morfismo

${\displaystyle \psi :\Sigma ^{*}\to M}$

a algún monoide M , tal que se mantienen las propiedades de traza "usuales", a saber:

1. implica que ${\displaystyle \psi (w)=\psi (\varepsilon )}$ ${\displaystyle w=\varepsilon }$

2. implica que ${\displaystyle (a,b)\in I_{D}}$ ${\displaystyle \psi (ab)=\psi (ba)}$

3. implica que ${\displaystyle \psi (ua)=\psi (v)}$ ${\displaystyle \psi (u)=\psi (v\div a)}$

4. y dar a entender que ${\displaystyle \psi (ua)=\psi (vb)}$ ${\displaystyle a\neq b}$ ${\displaystyle (a,b)\in I_{D}}$

Los morfismos de dependencia son universales, en el sentido de que para una dependencia fija dada D , si es un morfismo de dependencia a un monoide M , entonces M es isomorfo al monoide traza . En particular, el homomorfismo natural es un morfismo de dependencia. ${\displaystyle \psi :\Sigma ^{*}\to M}$ ${\displaystyle \mathbb {M} (D)}$

Formas normales

Existen dos formas normales bien conocidas para las palabras en los monoides de trazas. Una es la forma normal lexicográfica , debida a Anatolij V. Anisimov y Donald Knuth , y la otra es la forma normal de Foata, debida a Pierre Cartier y Dominique Foata, quienes estudiaron el monoide de trazas por su combinatoria en la década de 1960. ^[3]

La descomposición canónica de la forma de normalización (NFD) de Unicode es un ejemplo de una forma normal lexicográfica: el orden consiste en ordenar caracteres consecutivos con una clase de combinación canónica distinta de cero por esa clase.

Rastrear idiomas

Así como un lenguaje formal puede considerarse como un subconjunto de , el conjunto de todas las cadenas posibles, un lenguaje de trazas se define como un subconjunto de todas las trazas posibles. ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \mathbb {M} (D)}$

De manera alternativa, pero equivalente, un lenguaje es un lenguaje de traza, o se dice que es consistente con la dependencia D si ${\displaystyle L\subseteq \Sigma ^{*}}$

${\displaystyle L=[L]_{D}}$

dónde

${\displaystyle [L]_{D}=\bigcup _{w\in L}[w]_{D}}$

es el cierre de traza de un conjunto de cadenas.

Véase también

• Caché de seguimiento

Notas

1. Sándor y Crstici (2004) p.161
2. Proposición 2.2, Diekert y Métivier 1997.
3. Sección 2.3, Diekert y Métivier 1997.

Referencias

Referencias generales

• Diekert, Volker; Métivier, Yves (1997), "Conmutación parcial y rastros", en Rozenberg, G.; Salomaa, A. (eds.), Handbook of Formal Languages ​​Vol. 3; Beyond Words , Springer-Verlag, Berlín, págs. 457–534, ISBN 3-540-60649-1
• Lothaire, M. (2011), Combinatoria algebraica sobre palabras , Enciclopedia de matemáticas y sus aplicaciones, vol. 90, con prefacio de Jean Berstel y Dominique Perrin (reimpresión de la edición de tapa dura de 2002), Cambridge University Press, ISBN 978-0-521-18071-9, Zbl1221.68183 ​
• Antoni Mazurkiewicz, "Introducción a la teoría de las trazas", págs. 3-41, en El libro de las trazas , V. Diekert, G. Rozenberg, eds. (1995) World Scientific, Singapur ISBN 981-02-2058-8 
• Volker Diekert, Combinatoria en trazas , LNCS 454, Springer, 1990, ISBN 3-540-53031-2 , págs. 9-29 
• Sándor, Jozsef; Crstici, Borislav (2004), Manual de teoría de números II , Dordrecht: Kluwer Academic, págs. 32–36, ISBN 1-4020-2546-7, Zbl1079.11001 ​

Publicaciones seminales

• Pierre Cartier y Dominique Foata, Problèmes combinatoires de commutation et réarrangements , Lecture Notes in Mathematics 85, Springer-Verlag, Berlín, 1969, reimpresión gratuita de 2006 con nuevos apéndices
• Antoni Mazurkiewicz, Esquemas de programas concurrentes y sus interpretaciones , Informe DAIMI PB 78, Universidad de Aarhus, 1977