The Experts below are selected from a list of 21588 Experts worldwide ranked by ideXlab platform

Brigitte Pientka - One of the best experts on this subject based on the ideXlab platform.

  • Tabled Higher-Order Logic programming
    2003
    Co-Authors: Frank Pfenning, Brigitte Pientka
    Abstract:

    A Logical framework is a general meta-language for specifying and implementing deductive systems, given by axioms and inference rules. Based on a Higher-Order Logic programming interpretation, it supports executing Logical systems and reasoning with and about them, thereby reducing the effort required for each particular Logical system. In this thesis, we describe different techniques to improve the overall performance and the expressive power of Higher-Order Logic programming. First, we introduce tabled Higher-Order Logic programming, a novel execution model where some redundant information is eliminated using selective memorization. This extends tabled computation to the Higher-Order setting and forms the basis of the tabled Higher-Order Logic programming interpreter. Second, we present efficient data-structures and algorithms for Higher-Order proof search. In particular, we describe a Higher-Order assignment algorithm which eliminates many unnecessary occurs checks and develop Higher-Order term indexing. These optimizations are crucial to make tabled Higher-Order Logic programming successful in practice. Finally, we use tabled proof search in the meta-theorem prover to reason efficiently with and about deductive systems. It takes full advantage of Higher-Order assignment and Higher-Order term indexing. As experimental results demonstrate, these optimizations taken together constitute a significant step toward exploring the full potential of Logical frameworks in practice.

  • ICLP - A Proof-Theoretic Foundation for Tabled Higher-Order Logic Programming
    Logic Programming, 2002
    Co-Authors: Brigitte Pientka
    Abstract:

    Higher-Order Logic programming languages such as Elf extend first-Order Logic programming in two ways: first-Order terms are replaced with (dependently) typed ?-terms and the body of clauses may contain implication and universal quantification. In this paper, we describe tabled Higher-Order Logic programming where some redundant computation is eliminated by memoizing sub-computation and re-using its result later. This work extends Tamaki and Sato's search strategy based on memoization to the Higher-Order setting. We give a proof-theoretic characterization of tabling based on uniform proofs and prove soundness of the resulting interpreter. Based on it, we have implemented a prototype of a tabled Logic programming interpreter for Elf.

  • A proof-theoretic foundation for tabled Higher-Order Logic programming
    Lecture Notes in Computer Science, 2002
    Co-Authors: Brigitte Pientka
    Abstract:

    Higher-Order Logic programming languages such as Elf extend first-Order Logic programming in two ways: first-Order terms are replaced with (dependently) typed A-terms and the body of clauses may contain implication and universal quantification. In this paper, we describe tabled Higher-Order Logic programming where some redundant computation is eliminated by memoizing sub-computation and re-using its result later. This work extends Tamaki and Sato's search strategy based on memoization to the Higher-Order setting. We give a proof-theoretic characterization of tabling based on uniform proofs and prove soundness of the resulting interpreter. Based on it, we have implemented a prototype of a tabled Logic programming interpreter for Elf.

Tobias Nipkow - One of the best experts on this subject based on the ideXlab platform.

  • proving pointer programs in Higher Order Logic
    Conference on Automated Deduction, 2005
    Co-Authors: Farhad Mehta, Tobias Nipkow
    Abstract:

    Building on the work of Burstall, this paper develops sound modelling and reasoning methods for imperative programs with pointers: heaps are modelled as mappings from addresses to values, and pointer structures are mapped to Higher-level data types for verification. The programming language is embedded in Higher-Order Logic. Its Hoare Logic is derived. The whole development is purely definitional and thus sound. Apart from some smaller examples, the viability of this approach is demonstrated with a non-trivial case study. We show the correctness of the Schorr-Waite graph marking algorithm and present part of its readable proof in Isabelle/HOL.

  • Proving pointer programs in Higher-Order Logic
    Lecture Notes in Computer Science, 2003
    Co-Authors: Farhad Mehta, Tobias Nipkow
    Abstract:

    This paper develops sound modelling and reasoning methods for imperative programs with pointers: heaps are modelled as mappings from addresses to values, and pointer structures are mapped to Higher-level data types for verification. The programming language is embedded in Higher-Order Logic, its Hoare Logic is derived. The whole development is purely definitional and thus sound. The viability of this approach is demonstrated with a non-trivial case study. We show the correctness of the Schorr-Waite graph marking algorithm and present part of the readable proof in Isabelle/HOL.

  • proof terms for simply typed Higher Order Logic
    Theorem Proving in Higher Order Logics, 2000
    Co-Authors: Stefan Berghofer, Tobias Nipkow
    Abstract:

    This paper presents proof terms for simply typed, intuitionistic Higher Order Logic, a popular Logical framework. Unification-based algorithms for the compression and reconstruction of proof terms are described and have been implemented in the theorem prover Isabelle. Experimental results confirm the effectiveness of the compression scheme.

  • TPHOLs - Proof Terms for Simply Typed Higher Order Logic
    Lecture Notes in Computer Science, 2000
    Co-Authors: Stefan Berghofer, Tobias Nipkow
    Abstract:

    This paper presents proof terms for simply typed, intuitionistic Higher Order Logic, a popular Logical framework. Unification-based algorithms for the compression and reconstruction of proof terms are described and have been implemented in the theorem prover Isabelle. Experimental results confirm the effectiveness of the compression scheme.

Christoph Benzmüller - One of the best experts on this subject based on the ideXlab platform.

  • KI - Positive Free Higher-Order Logic and Its Automation via a Semantical Embedding
    Lecture Notes in Computer Science, 2020
    Co-Authors: Irina Makarenko, Christoph Benzmüller
    Abstract:

    Free Logics are a family of Logics that are free of any existential assumptions. Unlike traditional classical and non-classical Logics, they support an elegant modeling of nonexistent objects and partial functions as relevant for a wide range of applications in computer science, philosophy, mathematics, and natural language semantics. While free first-Order Logic has been addressed in the literature, free Higher-Order Logic has not been studied thoroughly so far. The contribution of this paper includes (i) the development of a notion and definition of free Higher-Order Logic in terms of a positive semantics (partly inspired by Farmer’s partial functions version of Church’s simple type theory), (ii) the provision of a faithful shallow semantical embedding of positive free Higher-Order Logic into classical Higher-Order Logic, (iii) the implementation of this embedding in the Isabelle/HOL proof-assistant, and (iv) the exemplary application of our novel reasoning framework for an automated assessment of Prior’s paradox in positive free quantified propositional Logics, i.e., a fragment of positive free Higher-Order Logic.

  • Sweet SIXTEEN: Automation via Embedding into Classical Higher-Order Logic
    Logic and Logical Philosophy, 2016
    Co-Authors: Alexander Steen, Christoph Benzmüller
    Abstract:

    An embedding of many-valued Logics based on SIXTEEN in classical Higher-Order Logic is presented. SIXTEEN generalizes the four-valued set of truth degrees of Dunn/Belnap’s system to a lattice of sixteen truth degrees with multiple distinct Ordering relations between them. The theoretical motivation is to demonstrate that many-valued Logics, like other non-classical Logics, can be elegantly modeled (and even combined) as fragments of classical Higher-Order Logic. Equally relevant are the pragmatic aspects of the presented approach: interactive and automated reasoning in many-valued Logics, which have broad applications in computer science, artificial intelligence, linguistics, philosophy and mathematics, become readily enabled with state of the art reasoning tools for classical Higher-Order Logic.

  • Automation of Higher-Order Logic
    Computational Logic, 2014
    Co-Authors: Christoph Benzmüller, Dale Miller
    Abstract:

    3 Church’s simple theory of types (classical Higher-Order Logic) 8 3.1 The λ-calculus as computation (middle and late 1930s) . . . . . . 8 3.2 Mixing λ-calculus and Logic . . . . . . . . . . . . . . . . . . . . . 9 3.3 Simple types and typed λ-terms . . . . . . . . . . . . . . . . . . . 9 3.4 Formulas as terms of type o . . . . . . . . . . . . . . . . . . . . . 11 3.5 Elementary type theory . . . . . . . . . . . . . . . . . . . . . . . 12 3.6 Simple type theory . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.7 Variants of elementary and simple type theory . . . . . . . . . . 14 3.8 An example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.9 Church used different syntax not adopted here . . . . . . . . . . 15

  • Automated Reasoning in Higher-Order Logic using the TPTP THF Infrastructure
    Journal of Formalized Reasoning, 2010
    Co-Authors: Geoff Sutcliffe, Christoph Benzmüller
    Abstract:

    The Thousands of Problems for Theorem Provers (TPTP) problem library is the basis of a well known and well established infrastructure that supports research, development, and deployment of Automated Theorem Proving (ATP) systems. The extension of the TPTP from first-Order form (FOF) Logic to typed Higher-Order form (THF) Logic has provided a basis for new development and application of ATP systems for Higher-Order Logic. Key developments have been the specification of the THF language, the addition of Higher-Order problems to the TPTP, the development of the TPTP THF infrastructure, several ATP systems for Higher-Order Logic, and the use of Higher-Order ATP in a range of domains. This paper describes these developments.

  • LPAR-05 Workshop: Empirically Successfull Automated Reasoning in Higher-Order Logic (ESHOL)
    arXiv: Artificial Intelligence, 2006
    Co-Authors: Christoph Benzmüller, John Harrison, Carsten Schürmann
    Abstract:

    This workshop brings together practioners and researchers who are involved in the everyday aspects of Logical systems based on Higher-Order Logic. We hope to create a friendly and highly interactive setting for discussions around the following four topics. Implementation and development of proof assistants based on any notion of impredicativity, automated theorem proving tools for Higher-Order Logic reasoning systems, Logical framework technology for the representation of proofs in Higher-Order Logic, formal digital libraries for storing, maintaining and querying databases of proofs. We envision attendees that are interested in fostering the development and visibility of reasoning systems for Higher-Order Logics. We are particularly interested in a discusssion on the development of a Higher-Order version of the TPTP and in comparisons of the practical strengths of automated Higher-Order reasoning systems. Additionally, the workshop includes system demonstrations. ESHOL is the successor of the ESCAR and ESFOR workshops held at CADE 2005 and IJCAR 2004.

Gilles Dowek - One of the best experts on this subject based on the ideXlab platform.

  • HOL-λσ: an intentional first-Order expression of Higher-Order Logic
    Mathematical Structures in Computer Science, 2001
    Co-Authors: Gilles Dowek, Thérèse Hardin, Claude Kirchner
    Abstract:

    We give a first-Order presentation of Higher-Order Logic based on explicit substitutions. This presentation is intentionally equivalent to the usual presentation of Higher-Order Logic based on λ-calculus, that is, a proposition can be proved without the extensionality axioms in one theory if and only if it can be in the other. We show that the Extended Narrowing and Resolution first-Order proof-search method can be applied to this theory. In this way we get a step-by-step simulation of Higher-Order resolution. Hence, expressing Higher-Order Logic as a first-Order theory and applying a first-Order proof search method is a relevant alternative to a direct implementation. In particular, the well-studied improvements of proof search for first-Order Logic could be reused at no cost for Higher-Order automated deduction. Moreover, as we stay in a first-Order setting, extensions, such as equational Higher-Order resolution, may be easier to handle.

  • HOL-lambda-sigma: an intentional first-Order expression of Higher-Order Logic
    Mathematical Structures in Computer Science, 2001
    Co-Authors: Gilles Dowek, Thérèse Hardin, Claude Kirchner
    Abstract:

    We give a first-Order presentation of Higher-Order Logic based on explicit substitutions. This presentation is intentionally equivalent to the usual presentation of Higher-Order Logic based on λ-calculus, that is, a proposition can be proved without the extensionality axioms in one theory if and only if it can be in the other. We show that the Extended Narrowing and Resolution first-Order proof-search method can be applied to this theory. In this way we get a step-by-step simulation of Higher-Order resolution. Hence, expressing Higher-Order Logic as a first-Order theory and applying a first-Order proof search method is a relevant alternative to a direct implementation. In particular, the well-studied improvements of proof search for first-Order Logic could be reused at no cost for Higher-Order automated deduction. Moreover, as we stay in a first-Order setting, extensions, such as equational Higher-Order resolution, may be easier to handle.

  • HOL-λσ: An Intentional First-Order Expression of Higher-Order Logic
    Rewriting Techniques and Applications, 1999
    Co-Authors: Gilles Dowek, Thérèse Hardin, Claude Kirchner
    Abstract:

    We propose a first-Order presentation of Higher-Order Logic based on explicit substitutions. It is intentionally equivalent to the usual presentation of Higher-Order Logic based on λ-calculus, i.e. a proposition can be proved without the extensionality axioms in one theory if and only if it can in the other. The tiExtended Narrowing and Resolution first-Order proof-search method can be applied to this theory. This allows to simulate Higher-Order resolution step by step and furthermore leaves room for further optimizations and extensions.

  • RTA - HOL-lambdasigma: An Intentional First-Order Expression of Higher-Order Logic
    1999
    Co-Authors: Gilles Dowek, Thérèse Hardin, Claude Kirchner
    Abstract:

    We propose a first-Order presentation of Higher-Order Logic based on explicit substitutions. It is intentionally equivalent to the usual presentation of Higher-Order Logic based on λ-calculus, i.e. a proposition can be proved without the extensionality axioms in one theory if and only if it can in the other. The Extended Narrowing and Resolution firstOrder proof-search method can be applied to this theory. This allows to simulate Higher-Order resolution step by step and furthermore leaves room for further optimizations and extensions.

  • HOL-$\lambda \sigma$ an intentional first-Order expression of Higher-Order Logic
    1999
    Co-Authors: Gilles Dowek, Thérèse Hardin, Claude Kirchner
    Abstract:

    We propose a first-Order presentation of Higher-Order Logic based on explicit substitutions. It is intentionally equivalent to the usual presentation of Higher-Order Logic based on $\lambda$-calculus, i.e. a proposition can be proved without the extensionality axioms in one theory if and only if it can in the other. The {\em Extended Narrowing and Resolution} first-Order proof-search method can be applied to this theory. This allows to simulate Higher-Order resolution step by step and furthermore leaves room for further optimizations and extensions.

Michael J. C. Gordon - One of the best experts on this subject based on the ideXlab platform.

  • Automatic Formal Synthesis of Hardware from Higher Order Logic
    Electronic Notes in Theoretical Computer Science, 2006
    Co-Authors: Michael J. C. Gordon, Juliano Iyoda, Scott Owens, Konrad Slind
    Abstract:

    A compiler that automatically translates recursive function definitions in Higher Order Logic to clocked synchronous hardware is described. Compilation is by mechanised proof in the HOL4 system, and generates a correctness theorem for each function that is compiled. Logic formulas representing circuits are synthesised in a form suitable for direct translation to Verilog HDL for simulation and input to standard design automation tools. The compilation scripts are open and can be safely modified: synthesised circuits are correct-by-construction. The synthesisable subset of Higher Order Logic can be extended using additional proof-based tools that transform definitions into the subset.

  • TPHOLs - Set Theory, Higher Order Logic or Both?
    Lecture Notes in Computer Science, 1996
    Co-Authors: Michael J. C. Gordon
    Abstract:

    The majority of general purpose mechanised proof assistants support versions of typed Higher Order Logic, even though set theory is the standard foundation for mathematics. For many applications Higher Order Logic works well and provides, for specification, the benefits of type-checking that are well-known in programming. However, there are areas where types get in the way or seem unmotivated. Furthermore, most people with a scientific or engineering background already know set theory, but not Higher Order Logic. This paper discusses some approaches to getting the best of both worlds: the expressiveness and standardness of set theory with the efficient treatment of functions provided by typed Higher Order Logic.