Related papers: Investigations into Proof Structures

Investigations into Proof Structures

URL: http://arxiv.org/abs/2304.12827v3
Date: Wed, 30 Oct 2024 09:55:46 GMT
Title: Investigations into Proof Structures
Authors: Christoph Wernhard, Wolfgang Bibel,
Abstract summary: We introduce and elaborate a novel formalism for the manipulation and analysis of proofs as objects in a global manner. It is applied in an exemplary manner to a coherent and comprehensive formal reconstruction and analysis of historical proofs of a widely-studied problem due to Lukasiewicz.
Score: 0.8287206589886879
License:
Abstract: We introduce and elaborate a novel formalism for the manipulation and analysis of proofs as objects in a global manner. In this first approach the formalism is restricted to first-order problems characterized by condensed detachment. It is applied in an exemplary manner to a coherent and comprehensive formal reconstruction and analysis of historical proofs of a widely-studied problem due to {\L}ukasiewicz. The underlying approach opens the door towards new systematic ways of generating lemmas in the course of proof search to the effects of reducing the search effort and finding shorter proofs. Among the numerous reported experiments along this line, a proof of {\L}ukasiewicz's problem was automatically discovered that is much shorter than any proof found before by man or machine.

Related papers

Lean-STaR: Learning to Interleave Thinking and Proving [53.923617816215774]
We present Lean-STaR, a framework for training language models to produce informal thoughts prior to each step of a proof. Lean-STaR achieves state-of-the-art results on the miniF2F-test benchmark within the Lean theorem proving environment.
arXiv Detail & Related papers (2024-07-14T01:43:07Z)
Proving Theorems Recursively [80.42431358105482]
We propose POETRY, which proves theorems in a level-by-level manner. Unlike previous step-by-step methods, POETRY searches for a sketch of the proof at each level. We observe a substantial increase in the maximum proof length found by POETRY, from 10 to 26.
arXiv Detail & Related papers (2024-05-23T10:35:08Z)
A Survey on Deep Learning for Theorem Proving [16.28502772608166]
Theorem proving is a fundamental aspect of mathematics, spanning from informal reasoning in natural language to rigorous derivations in formal systems. Deep learning, especially the emergence of large language models, has sparked a notable surge of research exploring these techniques to enhance the process of theorem proving.
arXiv Detail & Related papers (2024-04-15T17:07:55Z)
Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors [58.340159346749964]
We propose a new neural-symbolic method to support end-to-end learning using complex queries with provable reasoning capability. We develop a new dataset containing ten new types of queries with features that have never been considered. Our method outperforms previous methods significantly in the new dataset and also surpasses previous methods in the existing dataset at the same time.
arXiv Detail & Related papers (2023-04-14T11:35:35Z)
Generating Natural Language Proofs with Verifier-Guided Search [74.9614610172561]
We present a novel stepwise method NLProofS (Natural Language Proof Search) NLProofS learns to generate relevant steps conditioning on the hypothesis. It achieves state-of-the-art performance on EntailmentBank and RuleTaker.
arXiv Detail & Related papers (2022-05-25T02:22:30Z)
The Familiarity Hypothesis: Explaining the Behavior of Deep Open Set Methods [86.39044549664189]
Anomaly detection algorithms for feature-vector data identify anomalies as outliers, but outlier detection has not worked well in deep learning. This paper proposes the Familiarity Hypothesis that these methods succeed because they are detecting the absence of familiar learned features rather than the presence of novelty. The paper concludes with a discussion of whether familiarity detection is an inevitable consequence of representation learning.
arXiv Detail & Related papers (2022-03-04T18:32:58Z)
Formal Mathematics Statement Curriculum Learning [64.45821687940946]
We show that at same compute budget, expert iteration, by which we mean proof search interleaved with learning, dramatically outperforms proof search only. We also observe that when applied to a collection of formal statements of sufficiently varied difficulty, expert iteration is capable of finding and solving a curriculum of increasingly difficult problems.
arXiv Detail & Related papers (2022-02-03T00:17:00Z)
Structural Causal Models Reveal Confounder Bias in Linear Program Modelling [26.173103098250678]
We investigate the question of whether the phenomenon might be more general in nature, that is, adversarial-style attacks outside classical classification tasks. Specifically, we consider the base class of Linear Programs (LPs) We show the direct influence of the Structural Causal Model (SCM) onto the subsequent LP optimization, which ultimately exposes a notion of confounding in LPs.
arXiv Detail & Related papers (2021-05-26T17:19:22Z)
Learning from {\L}ukasiewicz and Meredith: Investigations into Proof Structures (Extended Version) [4.111899441919164]
This paper studies global features in selected problems and their proofs. The studied problems are of the wide-spread form of "axiom(s) and rule(s) imply goal(s)"
arXiv Detail & Related papers (2021-04-28T09:09:20Z)
Understanding the QuickXPlain Algorithm: Simple Explanation and Formal Proof [0.0]
This paper presents a proof of correctness of Ulrich Junker's QuickXPlain algorithm. It can be used as a guidance for proving other algorithms. It also provides the possibility of providing "gapless" correctness of systems that rely on results computed by QuickXPlain.
arXiv Detail & Related papers (2020-01-07T01:37:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.