|
Proof Compression
In proof theory, an area of mathematical logic, proof compression is the problem of algorithmically compressing formal proofs. The developed algorithms can be used to improve the proofs generated by automated theorem proving tools such as SAT solvers, SMT-solvers, first-order theorem provers and proof assistants. Problem Representation In propositional logic a resolution proof of a clause \kappa from a set of clauses ''C'' is a directed acyclic graph (DAG): the input nodes are axiom inferences (without premises) whose conclusions are elements of ''C'', the resolvent nodes are resolution inferences, and the proof has a node with conclusion \kappa. The DAG contains an edge from a node \eta_ to a node \eta_ if and only if a premise of \eta_ is the conclusion of \eta_. In this case, \eta_ is a child of \eta_, and \eta_ is a parent of \eta_. A node with no children is a root. A proof compression algorithm will try to create a new DAG with fewer nodes that represents a valid proof of \ ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Proof Theory
Proof theory is a major branchAccording to Wang (1981), pp. 3–4, proof theory is one of four domains mathematical logic, together with model theory, axiomatic set theory, and recursion theory. Jon Barwise, Barwise (1978) consists of four corresponding parts, with part D being about "Proof Theory and Constructive Mathematics". of mathematical logic that represents Mathematical proof, proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. Proofs are typically presented as Recursive data type, inductively-defined data structures such as list (computer science), lists, boxed lists, or Tree (data structure), trees, which are constructed according to the axioms and rule of inference, rules of inference of the logical system. Consequently, proof theory is syntax (logic), syntactic in nature, in contrast to model theory, which is Formal semantics (logic), semantic in nature. Some of the major areas of proof theory include structural proof theory, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sequent Calculus
In mathematical logic, sequent calculus is a style of formal logical argumentation in which every line of a proof is a conditional tautology (called a sequent by Gerhard Gentzen) instead of an unconditional tautology. Each conditional tautology is inferred from other conditional tautologies on earlier lines in a formal argument according to rules and procedures of inference, giving a better approximation to the natural style of deduction used by mathematicians than to David Hilbert's earlier style of formal logic, in which every line was an unconditional tautology. More subtle distinctions may exist; for example, propositions may implicitly depend upon non-logical axioms. In that case, sequents signify conditional theorems in a first-order language rather than conditional tautologies. Sequent calculus is one of several extant styles of proof calculus for expressing line-by-line logical arguments. * Hilbert style. Every line is an unconditional tautology (or theorem). * Gentzen s ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Resolution Proof Reduction Via Local Context Rewriting
In proof theory, an area of mathematical logic, resolution proof reduction via local context rewriting is a technique for resolution proof reduction via local context rewriting.Simone, S.F.; Brutomesso, R.; Sharygina, N. "An Efficient and Flexible Approach to Resolution Proof Reduction". 6th Haifa Verification Conference, 2010. This proof compression method was presented as an algorithm named ''ReduceAndReconstruct'', that operates as a post-processing of resolution Resolution(s) may refer to: Common meanings * Resolution (debate), the statement which is debated in policy debate * Resolution (law), a written motion adopted by a deliberative body * New Year's resolution, a commitment that an individual mak ... proofs. ReduceAndReconstruct is based on a set of local proof rewriting rules that transform a subproof into an equivalent or stronger one. Each rule is defined to match a specific context. A context involves two pivots (p and q) and five clauses (\alpha, \beta, \gamma, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Resolution Proof Compression By Splitting
In mathematical logic, proof compression by splitting is an algorithm that operates as a post-process on resolution Resolution(s) may refer to: Common meanings * Resolution (debate), the statement which is debated in policy debate * Resolution (law), a written motion adopted by a deliberative body * New Year's resolution, a commitment that an individual mak ... proofs. It was proposed by Scott Cotton in his paper "Two Techniques for Minimizing Resolution Proof".Cotton, Scott. "Two Techniques for Minimizing Resolution Proofs". 13th International Conference on Theory and Applications of Satisfiability Testing, 2010. The Splitting algorithm is based on the following observation: Given a proof of unsatisfiability \pi and a variable x, it is easy to re-arrange (split) the proof in a proof of x and a proof of \neg x and the recombination of these two proofs (by an additional resolution step) may result in a proof smaller than the original. Note that applying Splitting in a proo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
GitHub
GitHub, Inc. () is an Internet hosting service for software development and version control using Git. It provides the distributed version control of Git plus access control, bug tracking, software feature requests, task management, continuous integration, and wikis for every project. Headquartered in California, it has been a subsidiary of Microsoft since 2018. It is commonly used to host open source software development projects. As of June 2022, GitHub reported having over 83 million developers and more than 200 million repositories, including at least 28 million public repositories. It is the largest source code host . History GitHub.com Development of the GitHub.com platform began on October 19, 2007. The site was launched in April 2008 by Tom Preston-Werner, Chris Wanstrath, P. J. Hyett and Scott Chacon after it had been made available for a few months prior as a beta release. GitHub has an annual keynote called GitHub Universe. Organizational ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
LowerUnivalents
In proof compression In proof theory, an area of mathematical logic, proof compression is the problem of algorithmically compressing formal proofs. The developed algorithms can be used to improve the proofs generated by automated theorem proving tools such as SAT solver ..., an area of mathematical logic, LowerUnivalents is an algorithm used for the compression of propositional resolution proofs. LowerUnivalents is a generalised algorithm of the LowerUnits, and it is able to lower not only units but also subproofs of non-unit clauses, provided that they satisfy some additional conditions.Boudou, J., & Paleo, B. W. (2013). Compression of propositional resolution proofs by lowering subproofs. In Automated Reasoning with Analytic Tableaux and Related Methods (pp. 59-73). Springer Berlin Heidelberg. References {{logic-stub Mathematical logic ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
LowerUnits
In proof compression LowerUnits (LU) is an algorithm used to compress propositional logic resolution proofs. The main idea of LowerUnits is to exploit the following fact:Fontaine, Pascal; Merz, Stephan; Woltzenlogel Paleo, Bruno. ''Compression of Propositional Resolution Proofs via Partial Regularization''. 23rd International Conference on Automated Deduction, 2011. Theorem: Let \varphi be a potentially redundant proof, and \eta be the redundant proof , redundant node. If \eta’s clause In language, a clause is a constituent that comprises a semantic predicand (expressed or not) and a semantic predicate. A typical clause consists of a subject and a syntactic predicate, the latter typically a verb phrase composed of a verb with ... is a unit clause, then \varphi is redundant. The algorithm targets exactly the class of global redundancy stemming from multiple resolutions with unit clauses. The algorithm takes its name from the fact that, when this rewriting is done an ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Conference On Automated Deduction
The Conference on Automated Deduction (CADE) is the premier academic conference on automated deduction and related fields. The first CADE was organized in 1974 at the Argonne National Laboratory near Chicago. Most CADE meetings have been held in Europe and the United States. However, conferences have been held all over the world. Since 1996, CADE has been held yearly. In 2001, CADE was, for the first time, merged into the International Joint Conference on Automated Reasoning The International Joint Conference on Automated Reasoning (IJCAR) is a series of conferences on the topics of automated reasoning, automated deduction, and related fields. It is organized semi-regularly as a merger of other meetings. IJCAR replace ... (IJCAR). This has been repeated biannually since 2004. In 1996, CADE Inc. was formed as a non-profit sub-corporation of the Association for Automated Reasoning to organize the formerly individually organized conferences. External links * , CADE * , AAR Refe ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
RecycleUnits
In mathematical logic, proof compression by RecycleUnitsBar-Ilan, O.; Fuhrmann, O.; Hoory, S.; Shacham, O.; Strichman, O. ''Linear-time Reductions of Resolution Proofs''. Hardware and Software: Verification and Testing, p. 114–128, Springer, 2011. is a method for compressing propositional logic resolution proofs. Its main idea is to make use of intermediate (e.g. non input) proof results being unit clauses In language, a clause is a constituent that comprises a semantic predicand (expressed or not) and a semantic predicate. A typical clause consists of a subject and a syntactic predicate, the latter typically a verb phrase composed of a verb with ..., i.e. clauses containing only one literal. Certain proof nodes can be replaced with the nodes representing these unit clauses. After this operation the obtained graph is transformed into a valid proof. The output proof is shorter than the original while being equivalent or stronger. Algorithms The algorithms treat resolution p ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cut Elimination
The cut-elimination theorem (or Gentzen's ''Hauptsatz'') is the central result establishing the significance of the sequent calculus. It was originally proved by Gerhard Gentzen in his landmark 1934 paper "Investigations in Logical Deduction" for the systems system LJ, LJ and system LK, LK formalising intuitionistic logic, intuitionistic and classical logic respectively. The cut-elimination theorem states that any judgement that possesses a proof in the sequent calculus making use of the cut rule also possesses a cut-free proof, that is, a proof that does not make use of the cut rule. The cut rule A sequent is a logical expression relating multiple formulas, in the form , which is to be read as proves , and (as glossed by Gentzen) should be understood as equivalent to the truth-function "If (A_1 and A_2 and A_3 …) then (B_1 or B_2 or B_3 …)." Note that the left-hand side (LHS) is a conjunction (and) and the right-hand side (RHS) is a disjunction (or). The LHS may have arb ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
