Skip to Main content Skip to Navigation
Conference papers

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
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.
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/inria-00173259
Contributor : Olivier Teytaud Connect in order to contact the contributor
Submitted on : Monday, November 1, 2010 - 2:58:24 PM
Last modification on : Friday, February 4, 2022 - 3:23:42 AM
Long-term archiving on: : Friday, December 2, 2016 - 7:39:39 AM

File

12530ds.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00173259, version 2

Collections

Citation

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

Share

Metrics

Record views

233

Files downloads

1247