💻 computer science

Completeness of Synthesis under Realizability Assumptions using Superposition

Cet article présente un calcul raffiné basé sur la superposition pour synthétiser des programmes sans récursivité, qui est prouvé être correct et complet, garantissant la découverte d'une solution calculable chaque fois qu'une telle solution existe.

Auteurs originaux : Márton Hajdu, Petra Hozzová, Laura Kovács, Eva Maria Wagner

Publié 2026-05-20

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Márton Hajdu, Petra Hozzová, Laura Kovács, Eva Maria Wagner

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous êtes un architecte maître (l'ordinateur) essayant de construire une maison (un programme informatique) à partir d'un ensemble très spécifique de plans (les exigences de l'utilisateur). La partie délicate est que les plans mentionnent certains matériaux magiques et invisibles (symboles non calculables) qu'il vous est strictement interdit d'utiliser dans la construction réelle. Votre tâche consiste à construire une maison en utilisant uniquement des briques standard et réelles (symboles calculables) qui correspondent parfaitement à la description des plans.

Ce papier traite d'une nouvelle méthode plus intelligente pour que l'architecte puisse déterminer comment construire cette maison sans rester bloqué.

Le Problème : Se coincer dans la Zone « Magique »

Par le passé, les architectes utilisaient une méthode appelée Superposition (une façon élégante de dire « tester systématiquement des combinaisons de règles »). Ils tentaient de prouver que la maison pouvait être construite en mélangeant et en associant des règles.

Cependant, l'ancienne méthode présentait un défaut. Parfois, le plan disait : « Le toit doit être fait de Poussière Magique (non calculable), mais les murs doivent être faits de Briques (calculables). » L'ancien architecte se retrouvait confus. Il essayait de mélanger la Poussière Magique avec les Briques, réalisait qu'il ne pouvait pas utiliser la Poussière Magique, puis abandonnait, même si une solution utilisant uniquement des Briques existait réellement. Il restait bloqué car il ne savait pas ignorer la « Poussière Magique » assez longtemps pour trouver la solution à base de briques uniquement.

La Solution : Le Cadre « SUPRA »

Les auteurs introduisent un nouveau cadre appelé SUPRA (Superposition avec Hypothèses de Réalisabilité). Considérez cela comme un nouvel ensemble de règles pour l'architecte qui garantit qu'il trouvera une solution si une telle solution existe.

Voici comment SUPRA fonctionne, en utilisant trois métaphores simples :

1. La Règle du « Sac Lourd » (Ordre)

Imaginez que le plan contient deux types d'instructions :

Instructions Lourdes : « Utilisez de la Poussière Magique. »
Instructions Légères : « Utilisez des Briques. »

Dans l'ancienne méthode, l'architecte pouvait essayer de résoudre les instructions « Légères » en premier, se retrouver confus par les instructions « Lourdes », et abandonner.
Dans SUPRA, l'architecte est contraint de traiter les instructions « Lourdes » comme si elles pesaient une tonne. Il doit gérer les matériaux lourds et interdits en premier. En s'attaquant immédiatement aux règles de la « Poussière Magique », l'architecte dégage le chemin pour voir comment construire le reste de la maison en utilisant uniquement les « Briques » autorisées.

2. L'Astuce de « l'Abstraction » (La Règle Abs)

Parfois, le plan dit : « La poignée de porte doit être faite de Verre Magique », mais la poignée est fixée à une Porte en Bois (qui est autorisée).
L'ancien architecte aurait essayé de construire la poignée en Verre Magique et aurait échoué.
Le nouvel architecte SUPRA utilise une astuce appelée Abstraction. Il dit : « D'accord, je ne peux pas utiliser de Verre Magique, alors faisons semblant que la poignée est juste un 'Objet Mystère' pour l'instant. » Il sépare la partie « Magique » de la partie « Bois ». Cela lui permet de résoudre l'énigme pour la Porte en Bois en premier. Une fois la porte construite, il peut déterminer comment remplacer l'« Objet Mystère » par un matériau réel et autorisé qui s'adapte au même emplacement.

3. La « Corrigé » (Clauses de Réponse)

Au fur et à mesure que l'architecte construit, il maintient une liste en cours de « Corrigés ». Chaque fois qu'il effectue une étape logique, il note : « Si je fais X, la réponse est Y. »
Par le passé, ces clés pouvaient devenir désordonnées et contradictoires. SUPRA maintient ces clés très organisées. Si l'architecte atteint un point où il possède une maison complète et valide faite uniquement de matériaux autorisés, le « Corrigé » s'illumine d'une coche verte, montrant le programme final.

La Grande Revendication : « Complétude »

La chose la plus importante que ce papier revendique est la Complétude.

Dans le monde des mathématiques et de la logique, la « complétude » signifie : « Si une solution existe, nous la trouverons définitivement. »

Les auteurs prouvent que s'il existe une façon possible de construire la maison en utilisant uniquement des matériaux autorisés, leur nouvelle méthode SUPRA finira par la trouver. Ils ne disent pas simplement « cela fonctionne généralement » ; ils fournissent une garantie mathématique. Si le plan est soluble, l'architecte ne restera pas bloqué ; il terminera le travail.

Résumé

L'Objectif : Écrire automatiquement des programmes informatiques garantis corrects, même lorsque les exigences mentionnent des choses que le programme ne peut pas réellement utiliser.
L'Ancienne Façon : Se retrouvait parfois confus par les parties « magiques » interdites et abandonnait, même lorsqu'une solution était possible.
La Nouvelle Façon (SUPRA) :
1. Force le système à traiter les parties interdites en premier (afin qu'elles ne fassent pas obstacle).
2. Utilise une astuce de « simulation » pour séparer les parties interdites des parties autorisées.
3. Garantit que si une solution existe, le système la trouvera.

Ce papier est une percée théorique dans le raisonnement automatisé, assurant que nos architectes numériques ne manquent jamais une conception valide simplement parce qu'ils étaient distraits par la « magie » dans les instructions.

Résumé technique : Complétude de la synthèse sous hypothèses de réalisabilité utilisant la superposition

Énoncé du problème
L'article aborde le problème de la synthèse automatique de programmes, spécifiquement la tâche de dériver un programme sans récursion à partir d'une spécification logique du premier ordre. Le défi central réside dans la présence de « symboles non calculables » au sein de la spécification. Ces symboles, qui peuvent inclure des prédicats annotés par l'utilisateur ou des fonctions de Skolem introduites lors de la recherche de preuve, ne peuvent pas apparaître dans le programme synthétisé final. Le programme synthétisé doit être construit uniquement à partir de « symboles calculables » (par exemple, l'arithmétique standard, des fonctions définies par l'utilisateur) tout en satisfaisant une spécification qui peut mélanger à la fois des symboles calculables et non calculables.

Des travaux antérieurs de Hozzová et al. [14] ont introduit un cadre basé sur la saturation utilisant le calcul de superposition pour résoudre ce problème. Bien que cette approche ait été prouvée correcte (tout programme dérivé est correct), sa complétude restait une question ouverte. Plus précisément, il était incertain de savoir si le calcul pouvait garantir la découverte d'une solution si une telle solution existait (hypothèse de réalisabilité). L'article identifie des scénarios spécifiques où le calcul de [14] échoue à dériver une solution même lorsqu'un programme calculable existe, principalement en raison de limitations dans la manière dont il gère les ordres de termes, les fonctions de sélection et l'interaction entre les littéraux calculables et non calculables.

Méthodologie : Le calcul SUPRA
Les auteurs proposent un calcul raffiné nommé SUPRA (Superposition with Realizability Assumptions / Superposition avec hypothèses de réalisabilité) pour remédier à l'incomplétude du cadre précédent. La méthodologie implique trois ajustements techniques principaux à l'approche de synthèse basée sur la superposition standard :

Ordonnancements et sélection partitionnés :
L'article introduit un ordre de simplification « partitionné ». Dans cet ordre, tout terme non calculable ground est strictement supérieur à tout terme calculable ground. Par conséquent, la fonction de sélection est contrainte de toujours sélectionner tous les littéraux maximaux dans une clause. Cela garantit que les inférences impliquant des littéraux non calculables (qui sont plus grands) sont prioritaires par rapport à celles impliquant uniquement des littéraux calculables. Cela empêche le calcul de rester bloqué dans des dérivations où des contraintes non calculables empêchent la résolution des branches calculables.
Règle d'abstraction (Abs) :
Pour gérer les cas où des équations non calculables contiennent des sous-termes calculables qui doivent être résolus avant que le littéral non calculable puisse être traité, les auteurs introduisent une règle d'inférence auxiliaire appelée Abs. Cette règle abstrait les sous-termes calculables au sein des littéraux non calculables en les remplaçant par des variables fraîches et en ajoutant des contraintes de diségalité (par exemple, transformer $s[k] \approx t$ en $s[x] \approx t \land x \neq k$ ). Ce mécanisme sépare le raisonnement sur les symboles non calculables de celui sur les symboles calculables, permettant au calcul de résoudre les littéraux non calculables sans violer la contrainte de calculabilité du terme de réponse.
Règles d'inférence raffinées :
Le calcul utilise deux variantes de la règle de superposition :
- SupC : Introduit un constructeur ite (si-alors-sinon) dans le terme de réponse lors du basculement sur un littéral d'égalité.
- SupU : Unifie directement les termes de réponse des prémisses, évitant l'ajout de contraintes qui pourraient conduire à des conditions non calculables.
  Le calcul remplace également les « unificateurs calculables » utilisés dans [14] par des unificateurs les plus généraux (MGU) standards, s'appuyant sur l'ordonnancement partitionné et la règle Abs pour garantir que les termes de réponse résultants restent calculables.

Contributions clés

Identification de l'incomplétude : L'article démontre, via des contre-exemples (par exemple, un scénario de planification d'ateliers et un scénario de manipulation de constantes), que le calcul de [14] n'est pas complet sous les hypothèses de réalisabilité. Il échoue à trouver des solutions lorsque la sélection des littéraux ou l'ordonnancement des termes empêche les inférences nécessaires sur les symboles non calculables.
Le cadre SUPRA : Les auteurs définissent le calcul SUPRA, intégrant l'ordonnancement partitionné, la règle Abs et des contraintes de sélection spécifiques.
Preuve de correction : L'article prouve que SUPRA est correct par rapport à la sémantique des clauses de réponse, garantissant que tout programme dérivé est une solution valide à la spécification de synthèse.
Preuve de complétude : La contribution théorique principale est la preuve que SUPRA est complet sous l'hypothèse de réalisabilité. Les auteurs montrent que si un programme calculable satisfaisant la spécification existe, le calcul SUPRA (lorsqu'il est utilisé de manière exhaustive avec la règle Abs) est garanti de dériver une solution. La preuve construit un modèle pour l'ensemble saturé de clauses et démontre que si aucune solution n'était dérivée, une contradiction surgirait concernant la satisfiabilité de la spécification niée.

Résultats et importance
L'article établit que la synthèse de programmes via la preuve de théorèmes basée sur la saturation peut être rendue complète sous les hypothèses de réalisabilité en gérant soigneusement l'interaction entre les symboles calculables et non calculables. L'importance de ce travail réside dans la fermeture de l'écart théorique laissé par les recherches précédentes [14], fournissant une garantie formelle que le processus de synthèse réussira si une solution existe au sein de la signature calculable.

Les auteurs notent que leur notion de réalisabilité s'applique aux programmes sans récursion ; la construction de programmes récursifs nécessite des mécanismes (comme l'induction) non couverts par le calcul actuel. De plus, le résultat de complétude est conditionnel : il garantit de trouver une solution si une telle solution existe, plutôt que de prouver l'existence d'une solution pour toutes les spécifications. Le travail repose sur la logique du premier ordre standard avec égalité et ne prétend pas résoudre les problèmes de synthèse impliquant des théories nécessitant une élimination des quantificateurs (comme l'arithmétique linéaire) sauf si ces théories sont gérées par les capacités de raisonnement théorique du prouveur sous-jacent.

En résumé, l'article affine le calcul de superposition pour la synthèse en introduisant un ordonnancement partitionné et un mécanisme d'abstraction, prouvant que ces modifications sont suffisantes pour assurer la complétude de la synthèse de programmes sans récursion en présence de symboles non calculables.