Est-il possible de traduire une formule booléenne B en une conjonction équivalente de clauses Horn? L'article de Wikipédia sur HornSAT semble impliquer que c'est le cas, mais je n'ai pu chasser aucune référence. Notez que je ne veux pas dire "en temps polynomial", mais plutôt "du...
Cette question a été migrée à partir de Stack Overflow car il est possible d'y répondre sur Théorical Computer Science Stack Exchange. Migré il y a 8 ans . Étant donné que la correspondance Curry-Howard est si largement diffusée / étendue, y a-t-il une différence entre les preuves et les...
On dirait que George Gonthier et ses collaborateurs ont fini de formaliser le théorème des ordres impairs . Dans ses travaux antérieurs sur le théorème des quatre couleurs, Gonthier a inventé un tas de nouveaux algorithmes (principalement des variantes de BDD et d'algorithmes graphiques) qui se...
J'ai beaucoup lu sur les systèmes de types et autres et je comprends à peu près pourquoi ils ont été introduits (afin de résoudre le paradoxe de Russel). Je comprends également à peu près leur pertinence pratique dans les langages de programmation et les systèmes de preuve. Cependant, je ne suis...
ACSL (Ansi C Specification Language), est une spécification pour le code C, annotée de commentaires spéciaux, qui permet de vérifier formellement le code C. Je ne l'ai pas étudié, mais j'imagine que les méthodes formelles utilisées dans ACSL vérificateurs seraient similaires à Hoare Logic. Pour les...
Considérez cette question comme résolue. Je ne choisirai pas la meilleure réponse car elles ont toutes contribué à ma compréhension du sujet. Je ne sais pas quel avantage nous avons en définissant formellement la sémantique de la logique des prédicats. Mais je vois la valeur d'avoir un calcul de...
Je veux faire un premier solveur SAT. Je connais le concours SAT et la conférence SAT, et il y a tellement de papiers sur ce sujet. Je suis un démarreur, un démarreur débordé. Par où dois-je commencer? Finalement, je veux pousser l'état de l'art. Je veux des conseils d'experts sur la façon de...
Dans sa réponse à cette question , Stéphane Gimenez m'a signalé un algorithme de normalisation polynomiale en temps pour les preuves en logique linéaire. La preuve dans l'article de Girard utilise des réseaux de preuve, qui sont un aspect de la logique linéaire que je ne connais pas vraiment....
Les types et langages de programmation se concentrent un peu sur le sous-typage, mais pour autant que je sache, le sous-typage ne semble pas particulièrement fondamental. Le sous-typage vous donne-t-il plus que les types dépendants? Travailler avec des types dépendants est forcément plus de...
D'après ce que je comprends (ce qui est très peu, corrigez-moi donc là où je me trompe!), La théorie des langages de programmation s'intéresse souvent aux preuves "intuitionnistes". Dans ma propre interprétation, l'approche nous oblige à prendre au sérieux les conséquences du calcul sur la logique...
Récemment, j'ai vu plusieurs articles sur arxiv qui se réfèrent à un système de preuve appelé somme des carrés. Quelqu'un peut-il expliquer ce qu'est une preuve de somme des carrés et pourquoi ces preuves sont importantes / intéressantes? Comment sont-ils liés à d'autres systèmes de preuve...
Quelqu'un connaît-il des références qui définissent précisément le lien entre l' algorithme d'unification et l'élimination gaussienne? Je suis particulièrement intéressé par la relation entre les substitutions triangulaires et les décompositions LU. Wayne Snyder et Jean Gallier mentionnent cette...
Actuellement, j'enseigne un petit cours (quatre conférences de deux heures au niveau Master) sur les méthodes logiques en sécurité , bien que le titre Méthodes formelles en sécurité soit peut-être plus approprié. Il couvre brièvement les sujets suivants (avec les méthodes logiques associées):...
J'ai lu qu'au départ, Church proposait le -calculus dans le cadre de ses postulats de logiqueλλ\lambda (qui est une lecture dense). Mais Kleene a prouvé son "système" incohérent après quoi, Church a extrait des éléments pertinents pour son travail sur la "calculabilité effective" et a abandonné ses...
Quelqu'un pourrait-il expliquer la différence entre: Types de données algébriques (que je connais assez bien) Types de données algébriques généralisés (qu'est-ce qui les rend généralisés?) Types inductifs (par exemple Coq) (Types particulièrement inductifs.)
J'ai vu (et entendu) qu'il a affirmé qu'il est sûr d'ajouter l'axiome classique du milieu exclu à Coq, mais je n'arrive pas à trouver un document soutenant cette affirmation. Les articles que je vois répertoriés sur le wiki Coq sur le milieu exclu montrent une incohérence avec l'ensemble...
Considérez le raisonnement suivant: Soit la complexité de Kolmogorov de la chaîne . Le théorème d'incomplétude de Chaitin dit quexK( x )K(x)K(x)Xxx pour tout cohérent et système formel suffisamment solide , il existe une constante (ne dépendant que du système formel et sa langue) de telle sorte que...
L'auto-référentialité du problème P / NP a parfois été mise en évidence comme un obstacle à sa résolution, voir, par exemple, l'article de Scott Aaronson, P vs NP est-il formellement indépendant ? L'une des nombreuses résolutions envisageables pour P / NP serait une démonstration que le problème...
Un objectif important des méthodes formelles est de prouver l'exactitude des systèmes, par des moyens automatisés ou dirigés par l'homme. Cependant, il semble que même si vous pouvez fournir une preuve d'exactitude, vous ne pourrez PAS garantir que le système n'échouera pas. Par exemple: La...
Il est bien connu que les combinateurs S et K sont Turing Complete. Existe-t-il des combinateurs suffisants pour produire (uniquement) les fonctions récursives