The Experts below are selected from a list of 10212 Experts worldwide ranked by ideXlab platform
Alan Bundy - One of the best experts on this subject based on the ideXlab platform.
-
case analysis for rippling and Inductive Proof
Interactive Theorem Proving, 2010Co-Authors: Moa Johansson, Lucas Dixon, Alan BundyAbstract:Rippling is a heuristic used to guide rewriting and is typically used for Inductive theorem proving. We introduce a method to support case-analysis within rippling. Like earlier work, this allows goals containing if-statements to be proved automatically. The new contribution is that our method also supports case-analysis on datatypes. By locating the case-analysis as a step within rippling we also maintain the termination. The work has been implemented in IsaPlanner and used to extend the existing Inductive Proof method. We evaluate this extended prover on a large set of examples from Isabelle's theory library and from the Inductive theorem proving literature. We find that this leads to a significant improvement in the coverage of Inductive theorem proving. The main limitations of the extended prover are identified, highlight the need for advances in the treatment of assumptions during rippling and when conjecturing lemmas.
-
ITP - Case-Analysis for rippling and Inductive Proof
Interactive Theorem Proving, 2010Co-Authors: Moa Johansson, Lucas Dixon, Alan BundyAbstract:Rippling is a heuristic used to guide rewriting and is typically used for Inductive theorem proving. We introduce a method to support case-analysis within rippling. Like earlier work, this allows goals containing if-statements to be proved automatically. The new contribution is that our method also supports case-analysis on datatypes. By locating the case-analysis as a step within rippling we also maintain the termination. The work has been implemented in IsaPlanner and used to extend the existing Inductive Proof method. We evaluate this extended prover on a large set of examples from Isabelle's theory library and from the Inductive theorem proving literature. We find that this leads to a significant improvement in the coverage of Inductive theorem proving. The main limitations of the extended prover are identified, highlight the need for advances in the treatment of assumptions during rippling and when conjecturing lemmas.
-
experiments in automating hardware verification using Inductive Proof planning
Formal Methods in Computer-Aided Design, 1996Co-Authors: Francisco J Cantu, Alan Smaill, Alan Bundy, David BasinAbstract:We present a new approach to automating the verification of hardware designs based on planning techniques. A database of methods is developed that combines tactics, which construct Proofs, using specifications of their behaviour. Given a verification problem, a planner uses the method database to build automatically a specialised tactic to solve the given problem. User interaction is limited to specifying circuits and their properties and, in some cases, suggesting lemmas. We have implemented our work in an extension of the Clam Proof planning system. We report on this and its application to verifying a variety of combinational and synchronous sequential circuits including a parameterised multiplier design and a simple computer microprocessor.
-
extensions to a generalization critic for Inductive Proof
Conference on Automated Deduction, 1996Co-Authors: Andrew Ireland, Alan BundyAbstract:In earlier papers a critic for automatically generalizing conjectures in the context of failed Inductive Proofs was presented. The critic exploits the partial success of the search control heuristic known as rippling. Through empirical testing a natural generalization and extension of the basic critic emerged. Here we describe our extended generalization critic together with some promising experimental results.
-
Productive Use of Failure in Inductive Proof
Journal of Automated Reasoning, 1996Co-Authors: Andrew Ireland, Alan BundyAbstract:Proof by mathematical induction gives rise to various kinds of eureka steps, e.g., missing lemmata and generalization. Most Inductive theorem provers rely upon user intervention in supplying the required eureka steps. In contrast, we present a novel theorem-proving architecture for supporting the automatic discovery of eureka steps. We build upon rippling, a search control heuristic designed for Inductive reasoning. We show how the failure if rippling can be used in bridging gaps in the search for Inductive Proofs.
Hélène Kirchner - One of the best experts on this subject based on the ideXlab platform.
-
Programming Logics - Narrowing Based Inductive Proof Search
Programming Logics, 2013Co-Authors: Claude Kirchner, Hélène Kirchner, Fabrice NahonAbstract:We present in this paper a narrowing-based Proof search method for Inductive theorems. It has the specificity to be grounded on deduction modulo and to yield a direct translation from a successful Proof search derivation to a Proof in the sequent calculus. The method is shown to be sound and refutationally correct in a Proof theoretical way.
-
Narrowing Based Inductive Proof Search
2011Co-Authors: Claude Kirchner, Hélène Kirchner, Fabrice NahonAbstract:We present in this paper a narrowing-based Proof search method for Inductive theorems. It has the specificity to be grounded on deduction modulo and to yield a direct translation from a successful Proof search derivation to a Proof in the sequent calculus. The method is shown to be sound and refutationally correct in a Proof theoretical way.
-
Inductive Proof search modulo
Annals of Mathematics and Artificial Intelligence, 2009Co-Authors: Fabrice Nahon, Claude Kirchner, Hélène Kirchner, Paul BraunerAbstract:We present an original narrowing-based Proof search method for Inductive theorems in equational rewrite theories given by a rewrite system $\mathcal{R}$ and a set E of equalities. It has the specificity to be grounded on deduction modulo and to rely on narrowing to provide both induction variables and instantiation schemas. Whenever the equational rewrite system $(\mathcal{R},E)$ has good properties of termination, sufficient completeness, and when E is constructor and variable preserving, narrowing at defined-innermost positions leads to consider only unifiers which are constructor substitutions. This is especially interesting for associative and associative-commutative theories for which the general Proof search system is refined. The method is shown to be sound and refutationally correct and complete. A major feature of our approach is to provide a constructive Proof in deduction modulo for each successful instance of the Proof search procedure.
-
Inductive Proof search modulo
Annals of Mathematics and Artificial Intelligence, 2009Co-Authors: Fabrice Nahon, Claude Kirchner, Hélène Kirchner, Paul BraunerAbstract:International audienceWe present an original narrowing-based Proof search method for Inductive theorems in equational rewrite theories given by a rewrite system R and a set E of equalities. It has the specificity to be grounded on deduction modulo and to rely on narrowing to provide both induction variables and instantiation schemas. Whenever the equational rewrite system (R, E) has good properties of termination, sufficient completeness, and when E is constructor and variable preserving, narrowing at defined- innermost positions leads to consider only unifiers which are constructor substitutions. This is especially interesting for associative and associative-commutative theories for which the general Proof search system is refined. The method is shown to be sound and refutationaly correct and complete. A major feature of our approach is to provide a constructive Proof in deduction modulo for each successful instance of the Proof search procedure
-
Inductive Proof Search Modulo
2007Co-Authors: Fabrice Nahon, Claude Kirchner, Hélène KirchnerAbstract:We present an original narrowing-based Proof search method for Inductive theorems in equational rewrite theories given by a rewrite system R and a set E of equalities. It has the specificity to be grounded on deduction modulo and to rely on narrowing to provide both induction variables and instantiation schemas. Whenever the equational rewrite system R,E has good properties of termination, sufficient completeness, and when E is constructor and variable preserving, narrowing at defined-innermost positions leads to consider only unifiers which are constructor substitutions. This is especially interesting for associative and associative-commutative theories for which the general Proof search system is refined. The method is shown to be sound and refutationaly complete.
Soonho Kong - One of the best experts on this subject based on the ideXlab platform.
-
numerically robust Inductive Proof rules for continuous dynamical systems
Computer Aided Verification, 2019Co-Authors: Sicun Gao, James Kapinski, Jyotirmoy V Deshmukh, Nima Roohi, Armando Solarlezama, Nikos Arechiga, Soonho KongAbstract:We formulate numerically-robust Inductive Proof rules for unbounded stability and safety properties of continuous dynamical systems. These induction rules robustify standard notions of Lyapunov functions and barrier certificates so that they can tolerate small numerical errors. In this way, numerically-driven decision procedures can establish a sound and relative-complete Proof system for unbounded properties of very general nonlinear systems. We demonstrate the effectiveness of the proposed rules for rigorously verifying unbounded properties of various nonlinear systems, including a challenging powertrain control model.
-
CAV (2) - Numerically-Robust Inductive Proof Rules for Continuous Dynamical Systems
Computer Aided Verification, 2019Co-Authors: Sicun Gao, James Kapinski, Jyotirmoy V Deshmukh, Nima Roohi, Nikos Arechiga, Armando Solar-lezama, Soonho KongAbstract:We formulate numerically-robust Inductive Proof rules for unbounded stability and safety properties of continuous dynamical systems. These induction rules robustify standard notions of Lyapunov functions and barrier certificates so that they can tolerate small numerical errors. In this way, numerically-driven decision procedures can establish a sound and relative-complete Proof system for unbounded properties of very general nonlinear systems. We demonstrate the effectiveness of the proposed rules for rigorously verifying unbounded properties of various nonlinear systems, including a challenging powertrain control model.
Alan Smaill - One of the best experts on this subject based on the ideXlab platform.
-
Inductive Proof Automation for Coq
2010Co-Authors: Sean Wilson, Jacques Fleuriot, Alan SmaillAbstract:We introduce Inductive Proof automation for Coq that supports reasoning about Inductively defined data types and recursively defined functions. This includes support for Proofs involving case splits and multiple Inductive hypotheses. The automation makes use of the rippling heuristic to guide step case Proofs as well as heuristics for generalising goals. We include features for caching lemmas that are found during Proof search, where these lemmas can be reused in future Proof attempts. We show that the techniques we present provide a high-level of automation for Inductive Proofs which improves upon what is already available in Coq. We also discuss an algorithm that, by inspecting finished Proofs, can identify and then remove irrelevant subformulae from cached lemmas, making the latter more reusable. Finally, we compare our work to related research in the field.
-
experiments in automating hardware verification using Inductive Proof planning
Formal Methods in Computer-Aided Design, 1996Co-Authors: Francisco J Cantu, Alan Smaill, Alan Bundy, David BasinAbstract:We present a new approach to automating the verification of hardware designs based on planning techniques. A database of methods is developed that combines tactics, which construct Proofs, using specifications of their behaviour. Given a verification problem, a planner uses the method database to build automatically a specialised tactic to solve the given problem. User interaction is limited to specifying circuits and their properties and, in some cases, suggesting lemmas. We have implemented our work in an extension of the Clam Proof planning system. We report on this and its application to verifying a variety of combinational and synchronous sequential circuits including a parameterised multiplier design and a simple computer microprocessor.
-
Rippling: a heuristic for guiding Inductive Proofs
Artificial Intelligence, 1993Co-Authors: Alan Bundy, Andrew Ireland, Andrew Stevens, Frank Van Harmelen, Alan SmaillAbstract:Abstract We describe rippling: a tactic for the heuristic control of the key part of Proofs by mathematical induction. This tactic significantly reduces the search for a Proof of a wide variety of Inductive theorems. We first present a basic version of rippling, followed by various extensions which are necessary to capture larger classes of Inductive Proofs. Finally, we present a generalised form of rippling which embodies these extensions as special cases. We prove that generalised rippling always terminates, and we discuss the implementation of the tactic and its relation with other Inductive Proof search heuristics.
Katalin Bimbó - One of the best experts on this subject based on the ideXlab platform.
-
LE^{t}_{ \to } , LR^{ \circ }_{{\widehat{ \sim }}}, LK and Cutfree Proofs
Journal of Philosophical Logic, 2007Co-Authors: Katalin BimbóAbstract:Two consecution calculi are introduced: one for the implicational fragment of the logic of entailment with truth and another one for the disjunction free logic of nondistributive relevant implication. The Proof technique—attributable to Gentzen—that uses a double induction on the degree and on the rank of the cut formula is shown to be insufficient to prove admissible various forms of cut and mix in these calculi. The elimination theorem is proven, however, by augmenting the earlier double Inductive Proof with additional inductions. We also give a new purely Inductive Proof of the cut theorem for the original single cut rule in Gentzen’s sequent calculus \( LK \) without any use of mix.
