L'IA face aux grands problèmes du monde · Informatique théorique · arXiv · 2026-10-19
Résolution de CHC bi-approximative assistée par LLM
Titre original: LLM-Assisted Bi-Approximate CHC Solving
Les solveurs de clauses de Horn contraintes échouent souvent à trouver des contre-exemples profonds nécessitant de longues chaînes de dépliage de règles. Les auteurs font proposer par un LLM des sous-approximations de puissance de dérivation (Derivation Power Under-approximations), c'est-à-dire des sous-approximations de dérivations en plusieurs étapes vérifiées par le solveur, et les combinent avec la génération d'invariants dans le cadre HornCraft. Sur 260 benchmarks non résolus par une exécution de Spacer de 30 minutes, HornCraft a certifié des verdicts pour 228 d'entre eux, dont 42 instances non sûres contre 22 lorsque les DPU sont désactivées.