Inductive-deductive systems: a mathematical logic and statistical learning perspective

Nicolas Baskiotis 1 Michèle Sebag 1 Olivier Teytaud 1
1 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : This document was only presented in a conference with no copyrighted proceedings. The theorems about incompleteness of arithmetic have often been cited as an argument against automatic theorem proving and expert systems. However, these theorems rely on a worst-case analysis, which might happen to be overly pessimistic with respect to real-world domain applications. For this reason, a new framework for a probabilistic analysis of logical complexity is presented in this paper. Specifically, the rate of non-decidable clauses and the convergence of a set of axioms toward the target one when the latter exists in the language are studied, by combining results from mathematical logic and from statistical learning. Two theoretical settings are considered, where learning relies respectively on Turing oracles guessing the provability of a statement from a set of statements, and computable approximations thereof. Interestingly, both settings lead to similar results regarding the convergence rate towards completeness.
Type de document :
Communication dans un congrès
CAP, 2007, Grenoble, France. 16 p., 2007
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger
Contributeur : Olivier Teytaud <>
Soumis le : lundi 1 novembre 2010 - 14:58:24
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : vendredi 2 décembre 2016 - 07:39:39


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00173259, version 2



Nicolas Baskiotis, Michèle Sebag, Olivier Teytaud. Inductive-deductive systems: a mathematical logic and statistical learning perspective. CAP, 2007, Grenoble, France. 16 p., 2007. 〈inria-00173259v2〉



Consultations de la notice


Téléchargements de fichiers