Endpoint Sufficiency Behavioral Quotients

Résumé Technique : Quand l'oubli de la provenance est-il licite ?

Énoncé du problème
Les systèmes génératifs produisent souvent des objets qui peuvent être représentés à plusieurs niveaux d'abstraction. Une représentation capture uniquement le « point final visible » (l'objet final), tandis qu'une autre conserve la « provenance » complète (ascendance, événements de fusion, structures de dépendance). Bien que les représentations de points finaux soient plus petites, elles risquent d'être des descriptions d'état fausses si les lois d'admissibilité du système dépendent de la lignée. Le problème central abordé est de déterminer exactement quand les informations de provenance peuvent être oubliées en toute sécurité sans altérer le comportement futur licite du système. Plus précisément, l'article demande : quand une projection de point final conserve-t-elle suffisamment d'informations pour déterminer des transitions licites, et quelle est la quantité maximale de provenance qui peut être écartée ?

L'article remet en question l'hypothèse informelle selon laquelle la « suffisance du point final » est un concept unique et uniforme. Il démontète que cette notion varie selon le niveau d'observation : que l'on s'intéresse uniquement aux règles immédiatement activées, aux séquences finies d'étiquettes de règles (traces), ou à la structure de branchement complète des possibilités futures.

Méthodologie
L'auteur formalise le problème en utilisant des Systèmes de Transition Génératifs Licites (LGTS - Lawful Generative Transition Systems). Un LGTS est défini par un tuple $T = (S, \Sigma, \to, U, X, \cong_X)$, où :

• $S$ est un ensemble d'occurrences décorées de provenance.
• $\Sigma$ est un ensemble d'étiquettes de règles.
• $\to$ est la relation de transition étiquetée licite.
• $U: S \to X$ est une projection de point final reliant les occurrences aux objets visibles.
• $\cong_X$ est une relation d'équivalence sur les objets visibles.

L'étude analyse la relation entre la relation d'équivalence du point final ($\equiv_U$, où $s \equiv_U t \iff U(s) \cong_X U(t)$) et diverses équivalences comportementales. L'analyse procède à travers trois niveaux d'observation distincts :

1. Suffisance d'activation (Enabled Sufficiency) : Préserver l'ensemble des étiquettes de règles immédiatement disponibles.
2. Suffisance de trace (Trace Sufficiency) : Préserver l'ensemble de toutes les traces finies d'étiquettes de règles.
3. Suffisance de quotient (Branching/Quotient Sufficiency) : Préserver la structure de transition de branchement modulo l'équivalence du point final.

L'article emploie des outils de sémantique de processus standards, incluant l'équivalence de trace, la bisimulation forte, la coinduction et le raffinement de partition, appliqués spécif এটি spécifiquement à la frontière entre le point final et la provenance.

Contributions clés et résultats

1. Une hiérarchie stricte à trois niveaux
L'article établit que les trois niveaux de suffisance sont distincts et forment une hiérarchie stricte :
$$\text{Suffisance de Quotient} \implies \text{Suffisance de Trace} \implies \text{Suffisance d'Activation}$$

• La Suffisance d'Activation est la plus faible ; elle exige seulement que les points finaux équivalents aient le même ensemble de mouvements suivants activés.
• La Suffisance de Trace exige que les points finaux équivalents génèrent le même ensemble de séquences finies d'étiquettes de règles.
• La Suffisance de Quotient est la plus forte ; elle exige que l'ensemble des classes de points finaux atteignables pour une étiquette donnée dépende uniquement de la classe de point final actuelle, et non de l'historique spécifique de la provenance.

2. Critères exacts de suffisance
L'article fournit des critères mathématiques précis pour déterminer quand une projection de point final est suffisante à chaque niveau :

• Niveau Trace : La projection est suffisante pour les traces si et seulement si l'équivalence de point final est un sous-ensemble de l'équivalence de trace ($\equiv_U \subseteq \equiv_{tr}$).
• Niveau Branchement : La projection est suffisante pour le quotient si et seulement si l'équivalence de point final est une équivalence de bisimulation forte. Cela signifie que pour deux états équivalents par point final, toute transition de l'un peut être correspondue par une transition de l'autre vers un état qui est également équivalent par point final.

3. Réparations canoniques et oubli maximal
Lorsque l'équivalence brute du point final ne parvient pas à être suffisante, l'article propose deux « réparations canoniques » qui identifient le raffinement le plus grossier possible des états tout en respectant les points finaux visibles :

• Pour le temps linéaire (Traces) : La relation $E^U_{tr} = \equiv_U \cap \equiv_{tr}$ est la plus grande relation d'équivalence qui respecte les points finaux et préserve les traces finies. Elle identifie précisément les occurrences équivalentes par point final dont les futurs sont indiscernables en tant que traces d'étiquettes de règles.
• Pour le temps de branchement (Quotients exacts) : La relation $\approx_U$, définie comme l'union de toutes les bisimulations fortes respectant le point final, est la plus grande bisimulation forte respectant le point final. Le système quotient $T / \approx_U$ est le quotient de branchement exact maximal.
  • Propriété universelle : Tout autre quotient de point final respectant l'exactitude affine ce quotient canonique. Ainsi, $\approx_U$ représente la quantité maximale de provenance qui peut être oubliée tout en maintenant une sémantique de branchement exacte.

4. Calcul algorithmique
Pour les systèmes finis, l'article décrit une procédure de raffinement de partition terminante pour calculer $\approx_U$. L'algorithme initialise avec la partition des classes d'équivalence de point final et la raffine de manière itérative en se basant sur les « signatures » des blocs successeurs (les ensembles de blocs atteignables pour chaque étiquette). La procédure se stabilise à la partition correspondant à $\approx_U$.

5. Application à la génération récursive-recombinante imbriquée (NRRG)
L'article applique ces résultats à un cadre spécifique de NRRG décoré de provenance. Il présente un témoin où deux occurrences ($e_G$ et $e_H$) partagent le même point final de graphe visible ($I \to A \to B$) mais diffèrent par leur ascendance recombinante.

• Dans $e_G$, l'ascendance permet une règle de réécriture touchant une bordure ($R_B$).
• Dans $e_H$, l'ascendance interdit $R_B$.
• Résultat : L'algorithme de raffinement de partition sépare $e_G$ et $e_H$ dès le premier tour car leurs ensembles de successeurs activés diffèrent. Cela démontre que l'isomorphisme de point final n'implique pas l'équivalence comportementale, même au niveau de l'activation, et que la procédure de raffinement proposée identifie correctement la distinction nécessaire.

Signification et revendications
L'article prétend remplacer l'exigence « tout ou rien » consistant à soit conserver toute la provenance, soit la rejeter entièrement, par un critère exact pour un oubli licite.

• Résidu opérationnel : La différence entre les classes brutes de points finaux et les classes raffinées ($\approx_U$ ou $E^U_{tr}$) constitue le « résidu opérationnel » de la provenance — l'information historique qui reste active dans l'espace de transition futur.
• Exactitude de l'abstraction : Ce travail recadre le problème de l'abstraction non pas simplement comme une question de validité (sur-approximation), mais comme une question d'exactitude pour une sémantique choisie. Un quotient brut qui fusionne des états sans vérifier la bisimulation peut créer des comportements (inflation) qui ne sont pas licites pour des occurrences spécifiques.
• Indépendance du domaine : Les résultats sont présentés sous forme de critères formels applicables à tout système où l'admissibilité dépend de la lignée (ex: états de logiciels, instruments juridiques, affirmations scientifiques), à condition que le système puisse être modélisé comme un système de transition étiqueté avec une projection de point final.

L'article conclut que la provenance peut être effacée exactement à travers les distinctions d'occurrences qui ne modifient pas la sémantique de branchement choisie. Ce qui reste après l'effacement maximal sûr n'est pas une décoration historique, mais le véritable état génératif.