Endpoint Sufficiency Behavioral Quotients

Resumen Técnico: ¿Cuándo es lícita la pérdida de la procedencia?

Planteamiento del problema
Los sistemas generativos suelen producir objetos que pueden representarse en múltiples niveles de abstracción. Una representación captura únicamente el "punto final visible" (el objeto final), mientras que otra retiene la "procedencia" completa (ascendencia, eventos de fusión, estructuras de dependencia). Aunque las representaciones de puntos finales son más pequeñas, corren el riesgo de ser descripciones de estado falsas si las leyes de admisibilidad del sistema dependen del linaje. El problema central abordado es determinar exactamente cuándo la información de procedencia puede olvidarse de forma segura sin alterar el comportamiento futuro lícito del sistema. Específicamente, el artículo pregunta: ¿Cuándo una proyección de punto final retiene suficiente información para determinar transiciones lícitas, y cuál es la cantidad máxima de procedencia que se puede descartar?

El artículo desafía la suposición informal de que la "suficiencia del punto final" es un concepto único y uniforme. Demuestra que esta noción varía dependiendo del nivel de observación: ya sea que solo importen las reglas inmediatamente habilitadas, las secuencias finitas de etiquetas de reglas (trazas), o la estructura de ramificación completa de las posibilidades futuras.

Metodología
El autor formaliza el problema utilizando Sistemas de Transición Generativa Lícitos (LGTS, por sus siglas en inglés). Un LGTS se define como una tupla $T = (S, \Sigma, \to, U, X, \cong_X)$, donde:

• $S$ es un conjunto de ocurrencias decoradas con procedencia.
• $\Sigma$ es un conjunto de etiquetas de reglas.
• $\to$ es la relación de transición etiquetada lícita.
• $U: S \to X$ es una proyección de punto final que mapea las ocurrencias a objetos visibles.
• $\cong_X$ es una relación de equivalencia sobre los objetos visibles.

El estudio analiza la relación entre la relación de equivalencia de punto final ($\equiv_U$, donde $s \equiv_U t \iff U(s) \cong_X U(t)$) y diversas equivalencias de comportamiento. El análisis procede a través de tres niveles distintos de observación:

1. Suficiencia de habilitación: Preservar el conjunto de etiquetas de reglas inmediatamente disponibles.
2. Suficiencia de traza: Preservar el conjunto de todas las trazas finitas de etiquetas de reglas.
3. Suficiencia de cociente (ramificación): Preservar la estructura de transición de ramificación modulo la equivalencia de punto final.

El artículo emplea herramientas estándar de semántica de procesos, incluyendo equivalencia de traza, bisimulación fuerte, coinducción y refinamiento de particiones, aplicadas específicamente al límite entre el punto final y la procedencia.

Contribuciones clave y resultados

1. Una jerarquía estricta de tres niveles
El artículo establece que los tres niveles de suficiencia son distintos y forman una jerarquía estricta:
$$\text{Suficiencia de Cociente} \implies \text{Suficiencia de Traza} \implies \text{Suficiencia de Habilitación}$$

• La Suficiencia de Habilitación es la más débil; solo requiere que los puntos finales equivalentes tengan el mismo conjunto de movimientos próximos habilitados.
• La Sufencia de Traza requiere que los puntos finales equivalentes generen el mismo conjunto de secuencias finitas de etiquetas de reglas.
• La Suficiencia de Cociente es la más fuerte; requiere que el conjunto de clases de puntos finales alcanzables para cualquier etiqueta dependa solo de la clase de punto final actual, no de la historia específica de la procedencia.

2. Criterios exactos de suficiencia
El artículo proporciona criterios matemáticos precisos para cuando una proyección de punto final es suficiente en cada nivel:

• Nivel de Traza: La proyección es suficiente para la traza si y solo si la equivalencia de punto final es un subconjunto de la equivalencia de traza ($\equiv_U \subseteq \equiv_{tr}$).
• Nivel de Ramificación: La proyección es suficiente para el cociente si y solo si la equivalencia de punto final es una equivalencia de bisimulación fuerte. Esto significa que para cualquier par de estados equivalentes en su punto final, cada transición desde uno puede ser igualada por una transición desde el otro hacia un estado que también es equivalente en su punto final.

3. Reparaciones canónicas y olvido máximo
Cuando la equivalencia de punto final bruta no es suficiente, el artículo propone dos "reparaciones canónicas" que identifican la clase de refinamiento más gruesa posible de los estados que preserva el comportamiento deseado respetando los puntos finales visibles:

• Para Tiempo Lineal (Trazas): La relación $E^U_{tr} = \equiv_U \cap \equiv_{tr}$ es la relación de equivalencia más grande que respeta los puntos finales y preserva las trazas finitas. Identifica exactamente aquellas ocurrencias de punto final equivalentes cuyas funciones futuras son indistinguibles como trazas de etiquetas de reglas.
• Para Tiempo de Ramificación (Cocientes exactos): La relación $\approx_U$, definida como la unión de todas las bisimulaciones fuertes que respetan el punto final, es la mayor bisimulación fuerte que respeta el punto final. El sistema cociente $T / \approx_U$ es el cociente de ramificación exacta máximamente grueso.
  • Propiedad Universal: Cualquier otro cociente de punto final exacto refina este cociente canónico. Por lo tanto, $\approx_U$ representa la cantidad máxima de procedencia que se puede olvidar manteniendo una semántica de ramificación exacta.

4. Computación algorítmica
Para sistemas finitos, el artículo describe un procedimiento de refinamiento de partición terminante para computar $\approx_U$. El algoritmo inicializa con la partición de las clases de equivalencia de punto final y la refina iterativamente basándose en las "firmas" de los bloques sucesores (los conjuntos de bloques alcanzables para cada etiqueta). El procedimiento se estabiliza en la partición correspondiente a $\approx_U$.

5. Aplicación a la Generación Recursiva-Recombinante Anidada (NRRG)
El artículo aplica estos resultados a un marco específico de NRRG decorado con procedencia. Presenta un testigo donde dos ocurrencias ($e_G$ y $e_H$) comparten el mismo punto final de grafo visible ($I \to A \to B$) pero difieren en su ascendencia recombinante.

• En $e_G$, la ascendencia permite una regla de reescritura que toca el límite ($R_B$).
• En $e_H$, la ascendencia prohíbe $R_B$.
• Resultado: El algoritmo de refinamiento de partición separa $e_G$ y $e_H$ en la primera ronda porque sus conjuntos de sucesores habilitados difieren. Esto demuestra que el isomorfismo de punto final no implica equivalencia de comportamiento, incluso al nivel de habilitación, y que el procedimiento de refinamiento propuesto identifica correctamente la distinción necesaria.

Significado y Reivindicaciones
El artículo afirma reemplazar la demanda de "todo o nada" de retener toda la procedencia o descartarla por completo con un criterio exacto para el olvido lícito.

• Residuo Operacional: La diferencia entre las clases de punto final bruto y las clases refinadas ($\approx_U$ o $E^U_{tr}$) constituye el "residuo operacional" de la procedencia: información histórica que permanece activa en el espacio de transición futuro.
• Exactitud de la Abstracción: El trabajo redefine el problema de la abstracción no solo como una cuestión de corrección (sobreaproximación), sino de exactitud para una semántica elegida. Un cociente bruto que fusiona estados sin verificar la bisimulación puede crear comportamientos (inflación) que no son lícitos para ocurrencias específicas.
• Agnosticismo de Dominio: Los resultados se presentan como criterios formales aplicables a cualquier sistema donde la admisibilidad dependa del linaje (por ejemplo, estados de software, instrumentos legales, afirmaciones científicas), siempre que el sistema pueda modelarse como un sistema de transición etiquetado con una proyección de punto final.

El artículo concluye que la procedencia puede borrarse exactamente a través de aquellas distinciones de ocurrencia que no alteran la semántica de comportamiento futuro elegida. Lo que queda tras el borrado máximo seguro no es la decoración histórica, sino el verdadero estado generativo.