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

Seán Matthews - One of the best experts on this subject based on the ideXlab platform.

Marc Denecker - One of the best experts on this subject based on the ideXlab platform.

  • A Logical Study of Some Common Principles of Inductive Definition and its Implications for Knowledge Representation.
    arXiv: Logic in Computer Science, 2017
    Co-Authors: Marc Denecker, Bart Bogaerts, Joost Vennekens
    Abstract:

    The Definition is a common form of human expert knowledge, a building block of formal science and mathematics, a foundation for database theory and is supported in various forms in many knowledge representation and formal specification languages and systems. This paper is a formal study of some of the most common forms of Inductive Definitions found in scientific text: monotone Inductive Definition, Definition by induction over a well-founded order and iterated Inductive Definitions. We define a logic of Definitions offering a uniform formal syntax to express Definitions of the different sorts, and we define its semantics by a faithful formalization of the induction process. Several fundamental properties of Definition by induction emerge: the non-determinism of the induction process, the confluence of induction processes, the role of the induction order and its relation to the Inductive rules, how the induction order constrains the induction process and, ultimately, that the induction order is irrelevant: the defined set does not depend on the induction order. We propose an Inductive construction capable of constructing the defined set without using the induction order. We investigate borderline Definitions of the sort that appears in Definitional paradoxes.

  • KR - The well-founded semantics is the principle of Inductive Definition, revisited
    2014
    Co-Authors: Marc Denecker, Joost Vennekens
    Abstract:

    In the past, there have been several attempts to explain logic programming under the well-founded semantics as a logic of Inductive Definitions. A weakness in all is the absence of an obvious connection between how we understand various types of informal Inductive Definitions in mathematical text and the complex mathematics of the well-founded semantics. In this paper, we close this gap. We formalize the induction process in the most common principles and prove that the well-founded model construction generalizes them all.

  • Computational Logic - Extending Classical Logic with Inductive Definitions
    Computational Logic — CL 2000, 2000
    Co-Authors: Marc Denecker
    Abstract:

    The goal of this paper is to extend classical logic with a generalized notion of Inductive Definition supporting positive and negative induction, to investigate the properties of this logic, its relationships to other logics in the area of non-monotonic reasoning, logic programming and deductive databases, and to show its application for knowledge representation by giving a typology of Definitional knowledge.

  • Extending Classical Logic with Inductive Definitions
    arXiv: Logic in Computer Science, 2000
    Co-Authors: Marc Denecker
    Abstract:

    The goal of this paper is to extend classical logic with a generalized notion of Inductive Definition supporting positive and negative induction, to investigate the properties of this logic, its relationships to other logics in the area of non-monotonic reasoning, logic programming and deductive databases, and to show its application for knowledge representation by giving a typology of Definitional knowledge.

  • the well founded semantics is the principle of Inductive Definition
    Lecture Notes in Computer Science, 1998
    Co-Authors: Marc Denecker
    Abstract:

    Existing formalisations of (transfinite) Inductive Definitions in constructive mathematics are reviewed and strong correspondences with LP under least model and perfect model semantics become apparent. I point to fundamental restrictions of these existing formalisations and argue that the well-founded semantics (wfs) overcomes these problems and hence, provides a superior formalisation of the principle of Inductive Definition. The contribution of this study for LP is that it (re-) introduces the knowledge theoretic interpretation of LP as a logic for representing Definitional knowledge. I point to fundamental differences between this knowledge theoretic interpretation of LP and the more commonly known interpretations of LP as default theories or autoepistemic theories. The relevance is that differences in knowledge theoretic interpretation have strong impact on knowledge representation methodology and on extensions of the LP formalism, for example for representing uncertainty.

James Brotherston - One of the best experts on this subject based on the ideXlab platform.

  • formalised Inductive reasoning in the logic of bunched implications
    Static Analysis Symposium, 2007
    Co-Authors: James Brotherston
    Abstract:

    We present a framework for Inductive Definitions in the logic of bunched implications, BI, and formulate two sequent calculus proof systems for Inductive reasoning in this framework. The first proof system adopts a traditional approach to Inductive proof, extending the usual sequent calculus for predicate BI with explicit induction rules for the Inductively defined predicates. The second system allows an alternative mode of reasoning with Inductive Definitions by cyclic proof. In this system, the induction rules are replaced by simple case-split rules, and the proof structures are cyclic graphs formed by identifying some sequent occurrences in a derivation tree. Because such proof structures are not sound in general, we demand that cyclic proofs must additionally satisfy a global trace condition that ensures soundness. We illustrate our Inductive Definition framework and proof systems with simple examples which indicate that, in our setting, cyclic proof may enjoy certain advantages over the traditional induction approach.

  • sequent calculus proof systems for Inductive Definitions
    2006
    Co-Authors: James Brotherston
    Abstract:

    Inductive Definitions are the most natural means by which to represent many families of structures occurring in mathematics and computer science, and their corresponding induction / recursion principles provide the fundamental proof techniques by which to reason about such families. This thesis studies formal proof systems for Inductive Definitions, as needed, e.g., for Inductive proof support in automated theorem proving tools. The systems are formulated as sequent calculi for classical first-order logic extended with a framework for (mutual) Inductive Definitions. The default approach to reasoning with Inductive Definitions is to formulate the induction principles of the Inductively defined relations as suitable inference rules or axioms, which are incorporated into the reasoning framework of choice. Our first system LKID adopts this direct approach to Inductive proof, with the induction rules formulated as rules for introducing atomic formulas involving Inductively defined predicates on the left of sequents. We show this system to be sound and cut-free complete with respect to a natural class of Henkin models. As a corollary, we obtain cut-admissibility for LKID. The well-known method of infinite descent a la Fermat, which exploits the fact that there are no infinite descending chains of elements of well-ordered sets, provides an alternative approach to reasoning with Inductively defined relations. Our second proof system LKIDω formalises this approach. In this system, the left-introduction rules for formulas involving Inductively defined predicates are not induction rules but simple case distinction rules, and an infinitary, global soundness condition on proof trees — formulated in terms of “traces” on infinite paths in the tree — is required to ensure soundness. This condition essentially ensures that, for every infinite branch in the proof, there is an Inductive Definition that is unfolded infinitely often along the branch. By an infinite descent argument based upon the well-foundedness of Inductive Definitions, the infinite branches of the proof can thus be disregarded, whence the remaining portion of proof is well-founded and hence sound. We show this system to be cutfree complete with respect to standard models, and again infer the admissibility of cut. The infinitary system LKIDω is unsuitable for formal reasoning. However, it has a natural restriction to proofs given by regular trees, i.e. to those proofs representable by finite graphs. This restricted “cyclic” proof system, CLKIDω, is suitable for formal reasoning since proofs have finite representations and the soundness condition on proofs is thus decidable. We show how the formulation of our systems LKIDω and CLKIDω can be generalised to obtain soundness conditions for a general class of infinite proof systems and their corresponding cyclic restrictions. We provide machinery for manipulating and analysing the structure of proofs in these essentially arbitrary cyclic systems, based primarily on viewing them as generating regular infinite trees, and we show that any proof can be converted into an equivalent proof with a restricted cycle structure. For proofs in this “cycle normal form”, a finitary, lo-

Kaustuv Chaudhuri - One of the best experts on this subject based on the ideXlab platform.

  • A Proof-theoretic Characterization of Independence in Type Theory
    2015
    Co-Authors: Yuting Wang, Kaustuv Chaudhuri
    Abstract:

    For λ-terms constructed freely from a type signature in a type theory such as LF, there is a simple Inductive subordination relation that is used to control type-formation. There is a related—but not precisely complementary—notion of independence that asserts that the inhabitants of the function space τ 1 → τ 2 depend vacuously on their arguments. Independence has many practical reasoning applications in logical frameworks, such as pruning variable dependencies or transporting theorems and proofs between type signatures. However, independence is usually not given a formal interpretation. Instead, it is generally implemented in an ad hoc and uncertified fashion. We propose a formal Definition of independence and give a proof-theoretic characterization of it by: (1) representing the inference rules of a given type theory and a closed type signature as a theory of intuitionistic predicate logic, (2) showing that typing derivations in this signature are adequately represented by a focused sequent calculus for this logic, and (3) defining independence in terms of strengthening for intuitionistic sequents. This scheme is then formalized in a meta-logic, called G, that can represent the sequent calculus as an Inductive Definition, so the relevant strengthening lemmas can be given explicit Inductive proofs. We present an algorithm for automatically deriving the strengthening lemmas and their proofs in G.

  • A Two-Level Logic Approach to Reasoning about Typed Specification Languages
    2014
    Co-Authors: Mary Southern, Kaustuv Chaudhuri
    Abstract:

    The two-level logic approach (2LL) to reasoning about computational specifications, as implemented by the Abella theorem prover, represents derivations of a specification language as an Inductive Definition in a reasoning logic. This approach has traditionally been formulated with the specification and reasoning logics having the same type system, and only the formulas being translated. However, requiring identical type systems limits the approach in two important ways: (1) every change in the specification language's type system requires a corresponding change in that of the reasoning logic, and (2) the same reasoning logic cannot be used with two specification languages at once if they have incompatible type systems. We propose a technique based on adequate encodings of the types and judgements of a typed specification language in terms of a simply typed higher-order logic program, which is then used for reasoning about the specification language in the usual 2LL. Moreover, a single specification logic implementation can be used as a basis for a number of other specification languages just by varying the encoding. We illustrate our technique with an implementation of the LF dependent type theory as a new specification language for Abella, co-existing with its current simply typed higher-order hereditary Harrop specification logic, without modifying the type system of its reasoning logic.

Jan Schwinghammer - One of the best experts on this subject based on the ideXlab platform.