En informática , un rastro es un conjunto de cadenas , en el que ciertas letras de la cadena pueden conmutar , pero otras no. Generaliza el concepto de cadena, no obligando a que las letras estén siempre en un orden fijo, sino permitiendo que se produzcan ciertas reorganizaciones. Las trazas fueron introducidas por Pierre Cartier y Dominique Foata en 1969 para dar una prueba combinatoria del teorema maestro de MacMahon . Las trazas se utilizan en las teorías de computación concurrente , donde las letras que se desplazan al trabajo representan partes de un trabajo que se pueden ejecutar de forma independiente entre sí, mientras que las letras que no viajan al trabajo representan candados.puntos de sincronización o uniones de subprocesos . [1]
El monoide de trazas o monoide parcialmente conmutativo libre es un monoide de trazas. En pocas palabras, se construye de la siguiente manera: los conjuntos de letras de conmutación están dados por una relación de independencia . Estos inducen una relación de equivalencia de cadenas equivalentes; los elementos de las clases de equivalencia son los rastros. La relación de equivalencia luego divide el monoide libre (el conjunto de todas las cadenas de longitud finita) en un conjunto de clases de equivalencia; el resultado sigue siendo un monoide; es un monoide cociente y se llama monoide traza . El monoide traza es universal , en el sentido de que todos los monoides homomórficos de dependencia (ver más abajo) son de hecho isomórficos .
Los monoides de seguimiento se utilizan comúnmente para modelar el cálculo concurrente , lo que constituye la base para los cálculos de procesos . Son objeto de estudio en la teoría de las trazas . La utilidad de los monoides traza proviene del hecho de que son isomórficos al monoide de los gráficos de dependencia ; permitiendo así la aplicación de técnicas algebraicas a gráficos , y viceversa. También son isomorfos a los monoides históricos , que modelan la historia de la computación de procesos individuales en el contexto de todos los procesos programados en una o más computadoras.
Rastro
Dejar denotar el monoide libre, es decir, el conjunto de todas las cadenas escritas en el alfabeto . Aquí, el asterisco denota, como de costumbre, la estrella de Kleene . Una relación de independencia en luego induce una relación binaria en , dónde si y solo si existen y un par tal que y . Aquí, y se entienden como cadenas (elementos de ), tiempo y son letras (elementos de ).
La traza se define como el cierre simétrico, reflexivo y transitivo de. La traza es, pues, una relación de equivalencia en, y se denota por . El subíndice D sobre la equivalencia simplemente indica que la equivalencia se obtiene de la independencia I inducida por la dependencia D . Claramente, diferentes dependencias darán diferentes relaciones de equivalencia.
El cierre transitivo simplemente implica que si y solo si existe una secuencia de cadenas tal que y y para todos . La traza es estable bajo la operación monoide en( concatenación ) y, por lo tanto, es una relación de congruencia en.
El monoide traza, comúnmente denotado como , se define como el cociente monoide
El homomorfismo
se denomina comúnmente homomorfismo natural u homomorfismo canónico . El hecho de que los términos natural o canónico sean merecidos se deriva del hecho de que este morfismo encarna una propiedad universal, como se analiza en una sección posterior.
Ejemplos de
Considere el alfabeto . Una posible relación de dependencia es
La independencia correspondiente es
Por tanto, las letras viajar diariamente. Así, por ejemplo, una clase de equivalencia de rastreo para la cadena sería
La clase de equivalencia es un elemento del monoide traza.
Propiedades
La propiedad de cancelación establece que la equivalencia se mantiene bajo cancelación de derecho . Es decir, si, luego . Aquí, la notacióndenota cancelación de derecho, la eliminación de la primera aparición de la letra a de la cadena w , comenzando por el lado derecho. La equivalencia también se mantiene mediante cancelación a la izquierda. A continuación se presentan varios corolarios:
- Incrustación: si y solo si Para las cadenas x y y . Por tanto, el monoide traza es un monoide sintáctico.
- Independencia: si y , entonces a es independiente de b . Es decir,. Además, existe una cadena w tal que y .
- Regla de proyección: la equivalencia se mantiene bajo proyección de cuerda , de modo que si, luego .
Una forma fuerte del lema de Levi se aplica a los rastros. Específicamente, sipara cadenas u , v , x , y , entonces existen cadenas y tal que para todas las letras y tal que ocurre en y ocurre en , y
Propiedad universal
Un morfismo de dependencia (con respecto a una dependencia D ) es un morfismo
a algún monoide M , de modo que se mantengan las propiedades de traza "habituales", a saber:
- 1. implica que
- 2. implica que
- 3. implica que
- 4. y implica que
Los morfismos de dependencia son universales, en el sentido de que para una dependencia fija dada D , sies 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.
Formas normales
Hay dos formas normales bien conocidas para las palabras en los monoides traza. Una es la forma normal lexicográfica , debida a Anatolij V. Anisimov y Donald Knuth , y la otra es la forma normal Foata debida a Pierre Cartier y Dominique Foata, quienes estudiaron la traza monoide para su combinatoria en la década de 1960.
Idiomas de seguimiento
Así como un lenguaje formal puede considerarse como un subconjunto de el conjunto de todas las cadenas posibles, por lo que un lenguaje de seguimiento se define como un subconjunto de todos los rastros posibles.
Un idioma es un lenguaje de rastreo, o se dice que es consistente con la dependencia D si
dónde
es el cierre de traza de un conjunto de cadenas.
Ver también
Notas
Referencias
Referencias generales
- Diekert, Volker; Métivier, Yves (1997), "Partial Commutation and Traces" , en Rozenberg, G .; Salomaa, A. (eds.), Manual de lenguajes formales vol. 3; Más allá de las palabras , Springer-Verlag, Berlín, págs. 457–534, ISBN 3-540-60649-1
- Lothaire, M. (2011), Combinatoria algebraica en palabras , Enciclopedia de las matemáticas y sus aplicaciones, 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, Zbl 1221.68183
- 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, Combinatoria sobre 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, Zbl 1079.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