El álgebra de todo

Tabla de enlaces

Resumen y 1 Introducción

2 Definiciones y notaciones básicas

2.1 Conjuntos

2.2 Secuencias

2.3 Firmas y álgebras y 2.4 Categorías

3 Monografías y sus morfismos

4 Límites y colímites

5 Monografías de dibujo

6 Estructuras gráficas y monografías mecanografiadas

7 Submonografías y morfismos parciales

8 Transformaciones algebraicas de monografías

9 monografías mecanografiadas atribuidas

10 Conclusión y referencias

Abstracto

Las monografías son estructuras tipo grafo con aristas dirigidas de longitud ilimitada que son libremente adyacentes entre sí. Los nodos estándar se representan como aristas de longitud cero. Se pueden dibujar de forma consistente con los grafos estándar y muchos otros, como los E-grafos o los 8-grafos. La categoría de monografías comparte muchas propiedades con las categorías de estructuras de grafos (álgebras de firmas monádicas multiordenadas), excepto que no hay una monografía terminal. Es universal en el sentido de que sus categorías de corte (o categorías de monografías tipificadas) son equivalentes a las categorías de estructuras de grafos. Por lo tanto, las monografías tipo surgen como una forma natural de especificar estructuras de grafos. Se proporciona un análisis detallado de transformaciones pushout simples y dobles de monografías, y se analiza una noción de monografías tipificadas atribuidas que generalizan los E-grafos atribuidos tipo con respecto a las transformaciones que preservan los atributos.

Palabras clave : Transformación de grafos algebraicos, Estructuras de grafos, Grafos tipificados

1 Introducción

En matemáticas e informática se utilizan muchas nociones diferentes de grafos: grafos simples, grafos dirigidos, multigrafos, hipergrafos, etc. Una noción favorita en el contexto de la lógica y la reescritura es la también conocida como quivers, es decir, estructuras de la forma pN, E, s, tq donde N, E son conjuntos y s, t son funciones desde E (aristas) hasta N (nodos), que identifican las puntas de origen y destino de cada arista (o flecha). Una razón para esto es que la categoría de quivers es isomorfa a la categoría de álgebras de la firma de múltiples ordenamientos con dos ordenamientos nodos y aristas y dos nombres de operador src y tgt de aristas de tipo Ñ nodos. De conformidad con esta tradición, por grafo nos referimos a quiver en este documento.

Para representar convenientemente estructuras de datos elaboradas, a menudo es necesario enriquecer la estructura de los gráficos con atributos: los nodos o los bordes pueden etiquetarse con elementos de un conjunto fijo, o con valores tomados en alguna álgebra, o con conjuntos de valores como en [1], etc. Un ejemplo interesante se puede encontrar en [2] con la noción de E-gráficos, ya que los atributos también se consideran como nodos.

Más precisamente, un E-grafo es un álgebra cuya firma puede representarse mediante el siguiente gráfico:

Los nombres de las ordenaciones y operadores ayudan a comprender la estructura de los E-grafos: las aristas relacionan los nodos entre sí, las nv-aristas relacionan los nodos con los valores, y las ev-aristas relacionan las aristas con los valores. Por lo tanto, los valores de ordenación contienen atributos que también son nodos. Sin embargo, observamos que en los E-grafos las ev-aristas son adyacentes a las aristas. Esto no es estándar, pero aun así podemos aceptar estas estructuras como algún tipo de grafo, simplemente porque entendemos cómo se pueden dibujar.

Por lo tanto, la forma de generalizar la noción de grafos parece involucrar una generalización de la firma de grafos considerados como álgebras. Este camino ha sido seguido por Michael L¨owe en [3], donde una estructura de grafo se define como una firma monádica de múltiples ordenamientos. De hecho, en los ejemplos anteriores, y en muchos ejemplos proporcionados en [3], todos los operadores tienen aridad 1 y, por lo tanto, pueden considerarse como aristas desde su dominio hasta su ordenamiento de rango. ¿Es esta la razón por la que se llaman estructuras de grafo? Pero el ejemplo anterior muestra que los E-grafos son muy diferentes del grafo que representa su firma. Además, no es conveniente que nuestra comprensión de tales estructuras se base en la sintaxis, es decir, en los nombres particulares dados a los ordenamientos y operadores en la firma.

Además, es difícil ver cómo las álgebras de algunas firmas monádicas muy simples pueden interpretarse como grafos de cualquier forma. Tomemos, por ejemplo, la firma de grafos e invertimos la función objetivo a tgt: nodos Ñ aristas. Entonces existe una simetría entre los nodos y las aristas de los tipos, lo que significa que, en un álgebra con esta firma, los nodos y las aristas serían objetos de la misma naturaleza. ¿Sigue siendo esto un grafo? ¿Podemos dibujarlo? Peor aún, si los dos tipos se colapsan en uno, ¿significa que un nodo/arista puede ser adyacente a sí mismo?

Podemos abordar estos problemas restringiendo las estructuras de grafos a alguna clase de firmas monádicas cuyas álgebras garanticen un comportamiento ortodoxo, por ejemplo, presentando aristas y nodos claramente separados. Sin embargo, esto podría ser proclive a la arbitrariedad y presentaría otra desventaja: la noción de estructura de grafo no da lugar fácilmente a una categoría. De hecho, es difícil definir morfismos entre álgebras de diferentes firmas, aunque solo sea porque pueden tener cualquier número de conjuntos de portadores.

El enfoque adoptado aquí es más bien rechazar cualquier distinción estructural entre nodos y aristas, adoptando así una visión unificada de los nodos como aristas de longitud 0, y las aristas estándar como aristas de longitud 2 puesto que son adyacentes a dos nodos. Esta visión unificada permite lógicamente que las aristas sean adyacentes a cualquier arista y no solo a los nodos, generalizando así las ev-aristas de los E-grafos, e incluso a las aristas que son adyacentes a sí mismas. Finalmente, no hay razón para restringir la longitud de las aristas a 0 o 2, y encontraremos buenas razones (en la Sección 6) para permitir aristas de longitud ordinal infinita. Las nociones y notaciones necesarias se introducen en la Sección 2. La estructura de monografía (junto con los morfismos) se define en la Sección 3, produciendo un bestiario de categorías de monografías según algunas de sus características. Las propiedades de estas categorías respecto a la existencia de límites y co-límites se analizan en la Sección 4.

En la Sección 5, veremos cómo las monografías pueden representarse con precisión mediante dibujos, siempre que tengan un número finito de aristas y una longitud finita. En particular, estos dibujos corresponden a la forma estándar de dibujar un grafo para aquellas monografías que pueden identificarse con grafos estándar, y de forma similar para los E-grafos.

La Sección 6 se dedica a la comparación entre monografías y estructuras de grafos, y las álgebras correspondientes (que podríamos llamar álgebras grafoestructuradas). Demostramos una propiedad de universalidad de las monografías, en el sentido de que todas las álgebras grafoestructuradas pueden representarse (aunque generalmente no de forma canónica) como monografías tipificadas, es decir, como morfismos de monografías.

El concepto de estructura de grafos se introdujo en [3] para obtener categorías de homomorfismos parciales en los que se pudieran aplicar técnicas de reescritura algebraica de grafos. La correspondencia con las monografías establecida en la Sección 6 exige un desarrollo similar de morfismos parciales de monografías en la Sección 7. Los métodos de reescritura de monografías, con desplazamiento simple y doble, se pueden definir, analizar y comparar en la Sección 8.

El concepto de E-grafo se introdujo en [2] para obtener categorías de buen comportamiento (refiriéndose a la reescritura de grafos) de grafos atribuidos y, por lo tanto, proponer representaciones adecuadas de estructuras de datos reales. Esto se logra enriqueciendo los E-grafos con un álgebra de tipos de datos e identificando nodos de valor de ordenación con los elementos de esta álgebra. En la Sección 9, aplicamos un enfoque similar con el concepto de monografía tipificada atribuida, identificando elementos de un álgebra con aristas, y obteniendo categorías de buen comportamiento similar. Debido a la universalidad de las monografías, observamos que cualquier Σ-álgebra puede representarse como una monografía tipificada atribuida.

Concluimos en la Sección 10. Nótese que partes de las Secciones 4 a 6 han sido publicadas en [4].