Trees in Coalgebra from Generalized Reachability

Planteamiento del Problema
El artículo aborda las propiedades estructurales fundamentales de los sistemas basados en estados modelados como coclebras. Mientras que el concepto de alcanzabilidad (donde cada estado es accesible desde un estado inicial) ha sido bien caracterizado coclebraicamente mediante propiedades universales (ausencia de cocleubas propias) y construcciones iterativas (unión de estados sucesores), una caracterización coclebraica correspondiente de la estructura de árbol carecía de desarrollo. Específicamente, los autores buscan definir cuándo una coclebra es un "árbol" de una manera que generalice la noción intuitiva de la teoría de grafos: un sistema donde cada estado es alcanzable mediante un camino único desde el estado inicial. El desafío radica en manejar sistemas donde las transiciones pueden ser parciales, no deterministas o involucrar compartición, y en proporcionar una caracterización que funcione para una amplia clase de functores, incluyendo aquellos que no preservan monomorfismos (como el functor de bolsas o bag functor).

Metodología
Los autores emplean un enfoque categórico basado en sistemas de factorización y la teoría de coclebras. Su metodología procede a través de tres etapas principales:

1. Generalización de la Minimalidad: Primero generalizan la noción de "minimalidad" en una categoría. Más allá de la definición clásica donde un objeto minimal tiene no más subobjetos propios (requiriendo que los morfismos sean isomorfismos), introducen la $M$-minimalidad (Definición 4.1). Un objeto es $M$-minimal si todo morfismo de una clase $M$ hacia él es un epimorfismo partido (split epimorphism). Esta generalización permite que $M$ sea la clase de todos los morfismos, no solo los monomorfismos.
2. Conexión entre Proyectividad y Alcanzabilidad: Establecen un vínculo entre esta minimalidad generalizada y la $M$-proyectividad (Teorema 4.7). Luego, instancian esta teoría en la categoría de coclebras apuntadas para definir la alcanzabilidad generalizada (Definición 5.1). Una coclebra es $M$-alcanzable si toda coclebra apuntada $M$ es un epimorfismo partido.
3. Construcción Iterativa mediante Mapas Precisos: Para construir la versión alcanzable o el desenrollado de árbol de una coclebra, los autores utilizan morfismos precisos (Definición 3.1). A diferencia de los "límites ínfimos" (least bounds o bases) que dependen de monomorfismos para evitar la compartición, los mapas precisos aseguran que los elementos en el codominio se utilicen exactamente una vez en la definición del mapa. Demuestran que para functores analíticos, las factorizaciones precisas existen y coinciden con los límites ínfimos cuando se restringen a monomorfismos (Proposición 3.27, Corolario 3.22).

Contribuciones Clave
El artículo proporciona dos caracterizaciones equivalentes para determinar cuándo una coclebra es un árbol, reflejando las caracterizaciones duales de la alcanzabilidad:

• Propiedad Universal (Definición de Árbol): Una coclebra apuntada es un árbol si no tiene desenrollamientos (unravelings) propios. Formalmente, una coclebra es un árbol si cada desenrollamiento (un homomorfismo de coclebra apuntada hacia ella) es un epimorfismo partido (Definición 6.1). Esto generaliza la condición de alcanzabilidad al permitir que la clase de morfismos $M$ sea la clase de todos los morfismos, en lugar de solo los monomorfismos.
• Construcción Iterativa (Desenrollado de Árbol): Los autores presentan una construcción iterativa (Construcción 6.23) que transforma una coclebra apuntada arbitraria en un árbol. Esta construcción implica tomar el coproducto de niveles, donde cada nivel se computa mediante factorizaciones precisas del mapa de transición. La coclebra resultante es el "desenrollado de árbol" de la coclebra original.
• Unificación: El artículo demuestra que tanto la alcanzabilidad como la propiedad de ser un árbol son instancias de la misma noción generalizada de $M$-minimalidad. La alcanzabilidad corresponde a que $M$ sea una clase de monomorfismos, mientras que la propiedad de árbol corresponde a que $M$ sea la clase de todos los morfismos.

Resultados
Los autores validan su teoría recuperando las nociones esperadas de árboles para diversos ejemplos estándar:

• Autómatas Deterministas Parciales: El desenrollado de árbol corresponde a la "coclebra de entradas definidas", donde los estados se identifican con las palabras únicas que conducen a ellos (Lema 6.11, Corolario 6.12).
• Multigrafos (Functor de Bolsas/Bag Functor): Para las coclebras sobre el functor de bolsas (que modelan multigrafos), el desenrollado de árbol es la "coclebra de caminos enraizados". Una coclebra de bolsas es un árbol si y solo si existe un camino único desde la raíz hasta cada vértice (Teorema 6.18).
• Functor de Conjunto Potencia (Powerset Functor): El artículo destaca una limitación: para el functor de conjunto potencia (que modela grafos simples), la caracterización implica que casi ninguna coclebra es un árbol. Esto se debe a que el functor de conjunto potencia permite la "copia" (por ejemplo, $\{x\} = \{x, x\}$), lo que impide la existencia de mapas precisos para conjuntos no vacíos (Proposición 3.3). En consecuencia, los árboles en este entorno son triviales (un solo vértice, sin aristas).

Significancia
El artículo reclama su significancia al proporcionar un marco teórico unificado que extiende la teoría de las coclebras alcanzables hacia las estructuras de árbol.

• Generalización: Generaliza con éxito el concepto de alcanzabilidad desde sistemas de factorización propios (monos) hacia sistemas de factorización arbitrarios, permitiendo el tratamiento de estructuras de árbol donde los morfismos no necesitan ser inyectivos.
• Functores Analíticos: Se demuestra que la construcción iterativa funciona para todos los functores de conjuntos analíticos (Corolario 3.22), una clase amplia que incluye los functores polinomiales y el functor de bolsas, los cuales son centrales para modelar diversos sistemas computacionales.
• Claridad Conceptual: Al vincular la minimalidad con la proyectividad y proporcionar tanto caracterizaciones universales como iterativas, el trabajo ofrece una base categórica robusta para comprender el comportamiento de tipo árbol en sistemas basados en estados, distinguiéndolo claramente del comportamiento de los sistemas modelados por el functor de conjunto potencia.

Los autores señalan que este trabajo es una versión extendida de un artículo de conferencia, añadiendo pruebas completas y mayores generalizaciones, particularmente la conexión entre minimalidad y proyectividad y el análisis detallado de las factorizaciones precisas.