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

Andre Platzer - One of the best experts on this subject based on the ideXlab platform.

  • a complete uniform substitution calculus for differential dynamic logic
    Journal of Automated Reasoning, 2017
    Co-Authors: Andre Platzer
    Abstract:

    This article introduces a relatively complete proof calculus for differential dynamic logic (dL) that is entirely based on uniform substitution, a proof rule that substitutes a formula for a Predicate Symbol everywhere. Uniform substitutions make it possible to use axioms instead of axiom schemata, thereby substantially simplifying implementations. Instead of subtle schema variables and soundness-critical side conditions on the occurrence patterns of logical variables to restrict infinitely many axiom schema instances to sound ones, the resulting calculus adopts only a finite number of ordinary dLformulas as axioms, which uniform substitutions instantiate soundly. The static semantics of differential dynamic logic and the soundness-critical restrictions it imposes on proof steps is captured exclusively in uniform substitutions and variable renamings as opposed to being spread in delicate ways across the prover implementation. In addition to sound uniform substitutions, this article introduces differential forms for differential dynamic logic that make it possible to internalize differential invariants, differential substitutions, and derivatives as first-class axioms to reason about differential equations axiomatically. The resulting axiomatization of differential dynamic logic is proved to be sound and relatively complete.

  • a uniform substitution calculus for differential dynamic logic
    Conference on Automated Deduction, 2015
    Co-Authors: Andre Platzer
    Abstract:

    This paper introduces a new proof calculus for differential dynamic logic (\(\mathsf {d}\mathcal {L}\)) that is entirely based on uniform substitution, a proof rule that substitutes a formula for a Predicate Symbol everywhere. Uniform substitutions make it possible to rely on axioms rather than axiom schemata, substantially simplifying implementations. Instead of subtle schema variables and soundness-critical side conditions on the occurrence patterns of variables, the resulting calculus adopts only a finite number of ordinary \(\mathsf {d}\mathcal {L}\) formulas as axioms. The static semantics of differential dynamic logic is captured exclusively in uniform substitutions and bound variable renamings as opposed to being spread in delicate ways across the prover implementation. In addition to sound uniform substitutions, this paper introduces differential forms for differential dynamic logic that make it possible to internalize differential invariants, differential substitutions, and derivations as first-class axioms in \(\mathsf {d}\mathcal {L}\).

  • a uniform substitution calculus for differential dynamic logic
    arXiv: Logic in Computer Science, 2015
    Co-Authors: Andre Platzer
    Abstract:

    This paper introduces a new proof calculus for differential dynamic logic (dL) that is entirely based on uniform substitution, a proof rule that substitutes a formula for a Predicate Symbol everywhere. Uniform substitutions make it possible to rely on axioms rather than axiom schemata, substantially simplifying implementations. Instead of nontrivial schema variables and soundness-critical side conditions on the occurrence patterns of variables, the resulting calculus adopts only a finite number of ordinary dL formulas as axioms. The static semantics of differential dynamic logic is captured exclusively in uniform substitutions and bound variable renamings as opposed to being spread in delicate ways across the prover implementation. In addition to sound uniform substitutions, this paper introduces differential forms for differential dynamic logic that make it possible to internalize differential invariants, differential substitutions, and derivations as first-class axioms in dL.

Kouichi Hirata - One of the best experts on this subject based on the ideXlab platform.

  • of Acyclic Conjunctive Queries 1
    2015
    Co-Authors: Kouichi Hirata
    Abstract:

    A conjunctive query problem is a problem to determine whether or not a tuple be-longs to the answer of a conjunctive query over a database. In this paper, a tuple, a conjunctive query and a database in relational database theory are regarded as a ground atom, a nonrecursive function-free definite clause and a finite set of ground atoms, respectively, in inductive logic programming terminology. An acyclic con-junctive query problem is a conjunctive query problem with acyclicity. Concerned with the acyclic conjunctive query problem, in this paper, we present the hardness results of predicting acyclic conjunctive queries from an instance with a j-database of which Predicate Symbol is at most j-ary. Also we deal with two kinds of in-stances, a simple instance as a set of ground atoms and an extended instance as a set of pairs of a ground atom and a description. We mainly show that, from both a simple and an extended instances, acyclic conjunctive queries are not polynomial-time predictable with j-databases (j ≥ 3) under the cryptographic assumptions, and predicting acyclic conjunctive queries with 2-databases is as hard as predicting DNF formulas. Hence, the acyclic conjunctive queries become a natural example that the equivalence between subsumption-efficiency and efficient pac-learnability from both a simple and an extended instances collapses. Key words: acyclic conjunctive query, inductive logic programming, prediction, prediction-preserving reduction, subsumptio

  • Prediction-Hardness of Acyclic Conjunctive Queries
    2008
    Co-Authors: Kouichi Hirata
    Abstract:

    A conjunctive query problem is a problem to determine whether or not a tuple belongs to the answer of a conjunctive query over a database. Here, a tuple, a conjunctive query and a database in relational database theory are regarded as a ground atom, a nonrecursive function-free definite clause and a finite set of ground atoms, respectively, in inductive logic programming terminology. An acyclic conjunctive query problem is a conjunctive query problem with acyclicity. Concerned with the acyclic conjunctive query problem, in this paper, we present the hardness results of predicting acyclic conjunctive queries from an instance with a j-database of which Predicate Symbol is at most j-ary. Also we deal with two kinds of instances, a simple instance as a set of ground atoms and an extended instance as a set of pairs of a ground atom and a description. We mainly show that, from both a simple and an extended instances, acyclic conjunctive queries are not polynomialtime predictable with j-databases (j ≥ 3) under the cryptographic assumptions, and if acyclic conjunctive queries are polynomial-time predictable with 2-databases, then so are DNF formulas. Hence, the acyclic conjunctive queries become a natural example that collapses the equivalence between subsumption-efficiency and efficient pac-learnability from both a simple and an extended instances

  • Prediction-hardness of acyclic conjunctive queries
    Theoretical Computer Science, 2005
    Co-Authors: Kouichi Hirata
    Abstract:

    A conjunctive query problem is a problem to determine whether or not a tuple belongs to the answer of a conjunctive query over a database. In this paper, a tuple, a conjunctive query and a database in relational database theory are regarded as a ground atom, a nonrecursive function-free definite clause and a finite set of ground atoms, respectively, in inductive logic programming terminology. An acyclic conjunctive query problem is a conjunctive query problem with acyclicity. Concerned with the acyclic conjunctive query problem, in this paper, we present the hardness results of predicting acyclic conjunctive queries from an instance with a j-database of which Predicate Symbol is at most j-ary. Also we deal with two kinds of instances, a simple instance as a set of ground atoms and an extended instance as a set of pairs of a ground atom and a description. We mainly show that, from both a simple and an extended instances, acyclic conjunctive queries are not polynomial-time predictable with j-databases (j ≥ 3) under the cryptographic assumptions, and predicting acyclic conjunctive queries with 2-databases is as hard as predicting DNF formulas. Hence, the acyclic conjunctive queries become a natural example that the equivalence between subsumption-efficiency and efficient pac-learnability from both a simple and an extended instances collapses.

Ian Hodkinson - One of the best experts on this subject based on the ideXlab platform.

  • sahlqvist theorem for modal fixed point logic
    Theoretical Computer Science, 2012
    Co-Authors: Nick Bezhanishvili, Ian Hodkinson
    Abstract:

    We define Sahlqvist fixed point formulas. By extending the technique of Sambin and Vaccaro we show that (1) for each Sahlqvist fixed point formula @f there exists an LFP-formula @g(@f), with no free first-order variable or Predicate Symbol, such that a descriptive @m-frame (an order-topological structure that admits topological interpretations of least fixed point operators as intersections of clopen pre-fixed points) validates @f iff @g(@f) is true in this structure, and (2) every modal fixed point logic axiomatized by a set @F of Sahlqvist fixed point formulas is sound and complete with respect to the class of descriptive @m-frames satisfying {@g(@f):@[email protected][email protected]}. We also give some concrete examples of Sahlqvist fixed point logics and classes of descriptive @m-frames for which these logics are sound and complete.

  • I.: Sahlqvist theorem for modal fixed point logic. Theoretical Computer Science 424
    2012
    Co-Authors: Nick Bezhanishvili, Ian Hodkinson
    Abstract:

    We define Sahlqvist fixed point formulas. By extending the technique of Sambin and Vaccaro we show that (1) for each Sahlqvist fixed point formula ϕ there exists an LFP-formula χ(ϕ), with no free first-order variable or Predicate Symbol, such that a descriptive µ-frame (an order-topological structure that admits topological interpretations of least fixed point operators as intersections of clopen pre-fixed points) validates ϕ iff χ(ϕ) is true in this structure, and (2) every modal fixed point logic axiomatized by a set Φ of Sahlqvist fixed point formulas is sound and complete with respect to the class of descriptive µ-frames satisfying {χ(ϕ) : ϕ ∈ Φ}. We also give some concrete examples of Sahlqvist fixed point logics and classes of descriptive µ-frames for which these logics are sound and complete

  • SAHLQVIST THEOREM FOR MODAL FIXED POINT LOGIC
    2011
    Co-Authors: Nick Bezhanishvili, Ian Hodkinson
    Abstract:

    Abstract. We define Sahlqvist fixed point formulas. By extending the technique of Sambin and Vaccaro we show that (1) for each Sahlqvist fixed point formula ϕ there exists an LFPformula χ(ϕ), with no free first-order variable or Predicate Symbol, such that a descriptive µ-frame (an order-topological structure that admits topological interpretations of least fixed point operators as intersections of clopen pre-fixed points) validates ϕ iff χ(ϕ) is true in this structure, and (2) every modal fixed point logic axiomatized by a set Φ of Sahlqvist fixed point formulas is sound and complete with respect to the class of descriptive µ-frames satisfying {χ(ϕ) : ϕ ∈ Φ}. We also give some concrete examples of Sahlqvist fixed point logics and classes of descriptive µ-frames for which these logics are sound and complete. 1

Makoto Tatsuta - One of the best experts on this subject based on the ideXlab platform.

  • Classical System of Martin-Lof's Inductive Definitions is not Equivalent to Cyclic Proofs.
    Logical Methods in Computer Science, 2019
    Co-Authors: Makoto Tatsuta, Stefano Berardi
    Abstract:

    A cyclic proof system, called CLKID-omega, gives us another way of representing inductive definitions and efficient proof search. The 2005 paper by Brotherston showed that the provability of CLKID-omega includes the provability of LKID, first order classical logic with inductive definitions in Martin-L\"of's style, and conjectured the equivalence. The equivalence has been left an open question since 2011. This paper shows that CLKID-omega and LKID are indeed not equivalent. This paper considers a statement called 2-Hydra in these two systems with the first-order language formed by 0, the successor, the natural number Predicate, and a binary Predicate Symbol used to express 2-Hydra. This paper shows that the 2-Hydra statement is provable in CLKID-omega, but the statement is not provable in LKID, by constructing some Henkin model where the statement is false.

  • classical system of martin lof s inductive definitions is not equivalent to cyclic proof system
    Foundations of Software Science and Computation Structure, 2017
    Co-Authors: Stefano Berardi, Makoto Tatsuta
    Abstract:

    A cyclic proof system, called $$ \mathtt{CLKID}^\omega $$, gives us another way of representing inductive definitions and efficient proof search. The 2011 paper by Brotherston and Simpson showed that the provability of $$ \mathtt{CLKID}^\omega $$ includes the provability of Martin-Lof's system of inductive definitions, called $$ \mathtt{LKID} $$, and conjectured the equivalence. Since then, the equivalence has been left an open question. This paper shows that $$ \mathtt{CLKID}^\omega $$ and $$ \mathtt{LKID} $$ are indeed not equivalent. This paper considers a statement called 2-Hydra in these two systems with the first-order language formed by 0, the successor, the natural number Predicate, and a binary Predicate Symbol used to express 2-Hydra. This paper shows that the 2-Hydra statement is provable in $$ \mathtt{CLKID}^\omega $$, but the statement is not provable in $$ \mathtt{LKID} $$, by constructing some Henkin model where the statement is false.

Nick Bezhanishvili - One of the best experts on this subject based on the ideXlab platform.

  • sahlqvist theorem for modal fixed point logic
    Theoretical Computer Science, 2012
    Co-Authors: Nick Bezhanishvili, Ian Hodkinson
    Abstract:

    We define Sahlqvist fixed point formulas. By extending the technique of Sambin and Vaccaro we show that (1) for each Sahlqvist fixed point formula @f there exists an LFP-formula @g(@f), with no free first-order variable or Predicate Symbol, such that a descriptive @m-frame (an order-topological structure that admits topological interpretations of least fixed point operators as intersections of clopen pre-fixed points) validates @f iff @g(@f) is true in this structure, and (2) every modal fixed point logic axiomatized by a set @F of Sahlqvist fixed point formulas is sound and complete with respect to the class of descriptive @m-frames satisfying {@g(@f):@[email protected][email protected]}. We also give some concrete examples of Sahlqvist fixed point logics and classes of descriptive @m-frames for which these logics are sound and complete.

  • I.: Sahlqvist theorem for modal fixed point logic. Theoretical Computer Science 424
    2012
    Co-Authors: Nick Bezhanishvili, Ian Hodkinson
    Abstract:

    We define Sahlqvist fixed point formulas. By extending the technique of Sambin and Vaccaro we show that (1) for each Sahlqvist fixed point formula ϕ there exists an LFP-formula χ(ϕ), with no free first-order variable or Predicate Symbol, such that a descriptive µ-frame (an order-topological structure that admits topological interpretations of least fixed point operators as intersections of clopen pre-fixed points) validates ϕ iff χ(ϕ) is true in this structure, and (2) every modal fixed point logic axiomatized by a set Φ of Sahlqvist fixed point formulas is sound and complete with respect to the class of descriptive µ-frames satisfying {χ(ϕ) : ϕ ∈ Φ}. We also give some concrete examples of Sahlqvist fixed point logics and classes of descriptive µ-frames for which these logics are sound and complete

  • SAHLQVIST THEOREM FOR MODAL FIXED POINT LOGIC
    2011
    Co-Authors: Nick Bezhanishvili, Ian Hodkinson
    Abstract:

    Abstract. We define Sahlqvist fixed point formulas. By extending the technique of Sambin and Vaccaro we show that (1) for each Sahlqvist fixed point formula ϕ there exists an LFPformula χ(ϕ), with no free first-order variable or Predicate Symbol, such that a descriptive µ-frame (an order-topological structure that admits topological interpretations of least fixed point operators as intersections of clopen pre-fixed points) validates ϕ iff χ(ϕ) is true in this structure, and (2) every modal fixed point logic axiomatized by a set Φ of Sahlqvist fixed point formulas is sound and complete with respect to the class of descriptive µ-frames satisfying {χ(ϕ) : ϕ ∈ Φ}. We also give some concrete examples of Sahlqvist fixed point logics and classes of descriptive µ-frames for which these logics are sound and complete. 1