While certification has been successful in the context of satisfiablity solving, with most state-of-the-art solvers now able to provide proofs of unsatisfiability, in maximum satisfiability, such techniques are not ye...
详细信息
ISBN:
(纸本)9783031157073;9783031157066
While certification has been successful in the context of satisfiablity solving, with most state-of-the-art solvers now able to provide proofs of unsatisfiability, in maximum satisfiability, such techniques are not yet widespread. In this paper, we present QMaxSATpb, an extension of QMaxSAT that can produce proofs of optimality in the VeriPB proof format, which itself builds on the well-known cutting planes proof system. Our experiments demonstrate that proof logging is possible without much overhead.
We present a system for the visualization of proofs originating from Automated theorem Provers for first-order logic. the system can hide uninteresting proof parts of proofs, such as type annotations, translate first-...
详细信息
ISBN:
(纸本)9783031427527;9783031427534
We present a system for the visualization of proofs originating from Automated theorem Provers for first-order logic. the system can hide uninteresting proof parts of proofs, such as type annotations, translate first-order terms to standard math syntax, and compactly display complex formulas. We demonstrate the system on several non-trivial automated proofs of statements from Mizar Mathematical Library translated to first-order logic, and we provide a web interface where curious users can browse and investigate the proofs.
SHACL is a W3C-proposed language for expressing structural constraints on RDF graphs. In recent years, SHACL's popularity has risen quickly. this rise in popularity comes with questions related to its place in the...
详细信息
ISBN:
(纸本)9783031157073;9783031157066
SHACL is a W3C-proposed language for expressing structural constraints on RDF graphs. In recent years, SHACL's popularity has risen quickly. this rise in popularity comes with questions related to its place in the semantic web, particularly about its relation to OWL (the de facto standard for expressing ontological information on the web) and description logics (which form the formal foundations of OWL). We answer these questions by arguing that SHACL is in fact a description logic. On the one hand, our answer is surprisingly simple, some might even say obvious. But, on the other hand, our answer is also controversial. By resolving this issue once and for all, we establish the field of description logics as the solid formal foundations of SHACL.
Model-based Diagnosis (MBD) is an approach to diagnosis, where an (objective) model of a system is diagnosed to find a set of explanations revealing root causes for issues. Temporal behavioral models are prominent app...
详细信息
ISBN:
(纸本)9783031157073;9783031157066
Model-based Diagnosis (MBD) is an approach to diagnosis, where an (objective) model of a system is diagnosed to find a set of explanations revealing root causes for issues. Temporal behavioral models are prominent approach for temporal MBD, where their associated temporal formulas (TBFs) by Brusoni et al. (artificialintelligence, 102:39-79, 1998) can be used to relate explanations to observations under temporal constraints based on Allen's Interval Algebra (IA). Due to expressive limitations of the constructs, we envision an extended language of TBFs that allows for complex formulas and nesting of formulas in temporal constraints. To this end, we present a language that extends propositional resp. FO logic with IA relations and provide semantics for it based on here-and-there (HT) logic as well as on Equilibrium logic. Furthermore, we lift a well-known tableau calculus for propositional HT logic to the temporal setting and report about an experimental prototype implementation. Based on these results, rich notions of diagnostic explanations from temporal behavior models may be developed.
Pearl and Verma developed d-separation as a widely used graphical criterion to reason about the conditional independencies that are implied by the causal structure of a Bayesian network. As acyclic ground probabilisti...
详细信息
Pearl and Verma developed d-separation as a widely used graphical criterion to reason about the conditional independencies that are implied by the causal structure of a Bayesian network. As acyclic ground probabilistic logic programs correspond to Bayesian networks on their dependency graph, we can compute conditional independencies from d-separation in the latter. In the present paper, we generalize the reasoning above to the non-ground case. First, we abstract the notion of a probabilistic logic program away from external databases and probabilities to obtain so-called program structures. We then present a correct meta-interpreter that decides whether a certain conditional independence statement is implied by a program structure on a given external database. Finally, we give a fragment of program structures for which we obtain a completeness statement of our conditional independence oracle. We close with an experimental evaluation of our approach revealing that our meta-interpreter performs significantly faster than checking the definition of independence using exact inference in ProbLog 2.
the proceedings contain 29 papers. the special focus in this conference is on NASA Formal Methods. the topics include: reasoning with Metric Temporal logic and Resettable Skewed Clocks;centralized Multi-agen...
ISBN:
(纸本)9783031331695
the proceedings contain 29 papers. the special focus in this conference is on NASA Formal Methods. the topics include: reasoning with Metric Temporal logic and Resettable Skewed Clocks;centralized Multi-agent Synthesis with Spatial Constraints via Mixed-Integer Quadratic programming;a Framework for Policy Based Negotiation;rewrite-Based Decomposition of Signal Temporal logic Specifications;Quantitative Verification and Strategy Synthesis for BDI Agents;Multi-objective Task Assignment and Multiagent Planning with Hybrid GPU-CPU Acceleration;reasoning over Test Specifications Using Assume-Guarantee Contracts;from the Standards to Silicon: Formally Proved Memory Controllers;Formalising Liveness Properties in Event-B withthe Reflexive EB4EB Framework;open- and Closed-Loop Neural Network Verification Using Polynomial Zonotopes;formalized High Level Synthesis with Applications to Cryptographic Hardware;From Natural Language Requirements to the Verification of Programmable logic Controllers: Integrating FRET into PLCverif;automata-Based Software Model Checking of Hyperproperties;condition Synthesis Realizability via Constrained Horn Clauses;a Toolkit for Automated Testing of Dafny;Verified ALL(*) Parsing with Semantic Actions and Dynamic Input Validation;Subtropical Satisfiability for SMT Solving;a Linear Weight Transfer Rule for Local Search;adiar 1.1: Zero-Suppressed Decision Diagrams in External Memory;satisfiability of Non-linear Transcendental Arithmetic as a Certificate Search Problem;verifying Attention Robustness of Deep Neural Networks Against Semantic Perturbations;formalizing Piecewise Affine Activation Functions of Neural Networks in Coq;verifying an Aircraft Collision Avoidance Neural Network with Marabou;strategy Synthesis in Markov Decision Processes Under Limited Sampling Access;learning Symbolic Timed Models from Concrete Timed Data;reward Shaping from Hybrid Systems Models in Reinforcement Learning;conservative Safety Monitors of Stochastic Dynamical Sys
In temporal extensions of Answer Set programming (ASP) based on linear-time, the behavior of dynamic systems is captured by sequences of states. While this representation reflects their relative order, it abstracts aw...
详细信息
ISBN:
(纸本)9783031157073;9783031157066
In temporal extensions of Answer Set programming (ASP) based on linear-time, the behavior of dynamic systems is captured by sequences of states. While this representation reflects their relative order, it abstracts away the specific times associated with each state. In many applications, however, timing constraints are important like, for instance, when planning and scheduling go hand in hand. We address this by developing a metric extension of linear-time temporal equilibrium logic, in which temporal operators are constrained by intervals over natural numbers. the resulting Metric Equilibrium logic provides the foundation of an ASP-based approach for specifying qualitative and quantitative dynamic constraints. To this end, we define a translation of metric formulas into monadic first-order formulas and give a correspondence between their models in Metric Equilibrium logic and Monadic Quantified Equilibrium logic, respectively. Interestingly, our translation provides a blue print for implementation in terms of ASP modulo difference constraints.
Epistemic logic Programs (ELPs), extend Answer Set programming (ASP) with epistemic operators. the semantics of such programs is provided in terms of world views, which are sets of belief sets. Different semantic appr...
详细信息
ISBN:
(纸本)9783031157073;9783031157066
Epistemic logic Programs (ELPs), extend Answer Set programming (ASP) with epistemic operators. the semantics of such programs is provided in terms of world views, which are sets of belief sets. Different semantic approaches propose different characterizations of world views. Recent work has introduced semantic properties that should be met by any semantics for ELPs, like the Epistemic Splitting Property, that, if satisfied, allows to modularly compute world views in a bottom-up fashion, analogously to 'traditional' ASP. We analyze the possibility to change the perspective, shifting from a bottom-up to a top-down approach to splitting. Our new definition: (i) copes with concerns regarding unfoundedness of world views and subjective constraint monotonicity;(ii) is provably applicable to many of the existing semantics;(iii) operates similarly to "traditional" ASP;(iv) provably coincides withthe bottom-up notion of splitting at least on the class of Epistemically Stratified Programs (which are, intuitively, those where the use of epistemic operators is stratified).
the process of explaining a piece of evidence by constructing a set of assumptions that are a good explanation for that evidence is ubiquitous in real-life (e.g. in legal systems). In this paper, we introduce, discuss...
详细信息
ISBN:
(纸本)9783031157073;9783031157066
the process of explaining a piece of evidence by constructing a set of assumptions that are a good explanation for that evidence is ubiquitous in real-life (e.g. in legal systems). In this paper, we introduce, discuss, and formalise the notion of stable explanations in a non-monotonic setting. We show how, while applying it to the process of (1) computing a set of literals able to (2) derive a conclusion (3) from a set of defeasible rules, we obtain a restricted version of the notion of abduction. this is both interesting and useful: when an explanation for a given conclusion is stable, it can, in fact, be used to infer the same conclusion independently of other pieces of evidence that are found afterwards.
Probabilistic logic Programs under the distribution semantics (PLPDS) do not allow statistical probabilistic statements of the form "90% of birds fly", which were defined "Type 1" statements by Hal...
详细信息
ISBN:
(纸本)9783031157073;9783031157066
Probabilistic logic Programs under the distribution semantics (PLPDS) do not allow statistical probabilistic statements of the form "90% of birds fly", which were defined "Type 1" statements by Halpern. In this paper, we add this kind of statements to PLPDS and introduce the PASTA ("Probabilistic Answer set programming for STAtistical probabilities") language. We translate programs in our new formalism into probabilistic answer set programs under the credal semantics. this approach differs from previous proposals, such as the one based on "probabilistic conditionals" as, instead of choosing a single model by making the maximum entropy assumption, we take into consideration all models and we assign probability intervals to queries. In this way we refrain from making assumptions and we obtain a more neutral framework. We also propose an inference algorithm and compare it with an existing solver for probabilistic answer set programs on a number of programs of increasing size, showing that our solution is faster and can deal with larger instances.
暂无评论