Un e-graph («equality graph») es una estructura de datos que mantiene una relación de congruencia sobre árboles de expresiones: una relación de equivalencia estable al formar nuevas expresiones. Lo idearon Nelson y Oppen en 1980 y ganó atención con egg, de Willsey y colaboradores, que combina e-graphs y equality saturation para razonar con ecuaciones. El autor usa ahora su sucesor, egglog, para razonar sobre categorías finitamente presentadas en CatColab.
Las presentaciones habituales se centran en las estructuras de datos y los algoritmos, como union-find. Patterson se pregunta qué ocurre realmente en un e-graph, abstraído de la implementación. Menciona dos propuestas recientes de semántica categórica, que definen un «e-hipergrafo» con una estructura extra que especifica una equivalencia. Él parte en cambio de cómo se manipulan los e-graphs, con el objetivo de dar una semántica categórica y operacional de su cómputo. En esta entrega se limita a categorías sin estructura adicional, lo que equivale a admitir solo símbolos de función unarios; en próximas entregas pasará a categorías con productos finitos para recuperar el caso estándar.
Las ecuaciones entre morfismos se representan con diagramas conmutativos, es decir, functores de una categoría pequeña (la forma del diagrama) a otra categoría. En la práctica se trabaja con diagramas libres y finitamente presentados, cuya forma está generada libremente por un grafo finito, y con una categoría de destino presentada por generadores y relaciones. El objetivo es derivar nuevas ecuaciones manipulando esos diagramas.
Para que una manipulación sea válida, es decir, que conserve exactamente las soluciones de las ecuaciones que presenta el diagrama, el functor R debe ser inicial. El artículo da tres condiciones equivalentes: la precomposición con R preserva límites; preserva límites de conjuntos; o las categorías coma R/k son no vacías y conexas para todo objeto k. En el caso libre y finitamente generado, comprobarlo se reduce a un problema combinatorio. Como el límite de un diagrama de conjuntos es el conjunto de tuplas que cumplen las ecuaciones indexadas por los morfismos de la forma, los functores iniciales son los que preservan ese conjunto de soluciones. Como las categorías finitamente presentadas rara vez tienen muchos productos o igualadores, el autor propone interpretarlas en conjuntos mediante functores a Set, lo que enlaza con las «funciones no interpretadas» de la comunidad de e-graphs.
Esta noticia la ha redactado una inteligencia artificial a partir de las fuentes citadas, con el criterio editorial de El Autómata (equilibrio, atribución y solo hechos publicados). Puede contener errores: consulta las fuentes originales. Modelo: claude-sonnet-5.5.