Generalising and re-using knowledge learned while solving one problem instance has been neglected by state-of-the-art answer set solvers. We suggest a new approach that generalises learned nogoods for re-use to speed-...
详细信息
Generalising and re-using knowledge learned while solving one problem instance has been neglected by state-of-the-art answer set solvers. We suggest a new approach that generalises learned nogoods for re-use to speed-up the solving of future problem instances. Our solution combines well-known ASP solving techniques with deductive logic-based machine learning. Solving performance can be improved by adding learned non-ground constraints to the original program. We demonstrate the effects of our method by means of realistic examples, showing that our approach requires low computational cost to learn constraints that yield significant performance benefits in our test cases. These benefits can be seen with ground-and-solve systems as well as lazy-grounding systems. However, ground-and-solve systems suffer from additional grounding overheads, induced by the additional constraints in some cases. By means of conflict minimization, non-minimal learned constraints can be reduced. This can result in significant reductions of grounding and solving efforts, as our experiments show.
Recent progress in logicprogramming (e.g. the development of the answer set programming (ASP) paradigm) has made it possible to teach it to general undergraduate and even middle/high school students. Given the limite...
详细信息
Recent progress in logicprogramming (e.g. the development of the answer set programming (ASP) paradigm) has made it possible to teach it to general undergraduate and even middle/high school students. Given the limited exposure of these students to computer science, the complexity of downloading, installing, and using tools for writing logic programs could be a major barrier for logicprogramming to reach a much wider audience. We developed onlineSPARC, an online ASP environment with a self-contained file system and a simple interface. It allows users to type/edit logic programs and perform several tasks over programs, including asking a query to a program, getting the answer sets of a program, and producing a drawing/animation based on the answer sets of a program.
Reduction to the satisfiablility problem for constrained Horn clauses (CHCs) is a widely studied approach to automated program verification. The current CHC-based methods for pointer-manipulating programs, however, ar...
详细信息
ISBN:
(数字)9783030449148
ISBN:
(纸本)9783030449148;9783030449131
Reduction to the satisfiablility problem for constrained Horn clauses (CHCs) is a widely studied approach to automated program verification. The current CHC-based methods for pointer-manipulating programs, however, are not very scalable. This paper proposes a novel translation of pointer-manipulating Rust programs into CHCs, which clears away pointers and heaps by leveraging ownership. We formalize the translation for a simplified core of Rust and prove its correctness. We have implemented a prototype verifier for a subset of Rust and confirmed the effectiveness of our method.
Probabilistic logicprogramming is an effective formalism for encoding problems characterized by uncertainty. Some of these problems may require the optimization of probability values subject to constraints among prob...
详细信息
Separation logic is a useful tool for proving the correctness of programs that manipulate memory, especially when the model of memory includes higher-order state: Step-indexing, predicates in the heap, and higher-orde...
详细信息
ISBN:
(数字)9783030449148
ISBN:
(纸本)9783030449148;9783030449131
Separation logic is a useful tool for proving the correctness of programs that manipulate memory, especially when the model of memory includes higher-order state: Step-indexing, predicates in the heap, and higher-order ghost state have been used to reason about function pointers, data structure invariants, and complex concurrency patterns. On the other hand, the behavior of system features (e.g., operating systems) and the external world (e.g., communication between components) is usually specified using first-order formalisms. In principle, the soundness theorem of a separation logic is its interface with first-order theorems, but the soundness theorem may implicitly make assumptions about how other components are specified, limiting its use. In this paper, we show how to extend the higher-order separation logic of the Verified Software Toolchain to interface with a first-order verified operating system, in this case CertiKOS, that mediates its interaction with the outside world. The resulting system allows us to prove the correctness of C programs in separation logic based on the semantics of system calls implemented in CertiKOS. It also demonstrates that the combination of interaction trees + CompCert memories serves well as a lingua franca to interface and compose two quite different styles of program verification.
Cooperation among constraint solvers is difficult because different solving paradigms have different theoretical foundations. Recent works have shown that abstract interpretation can provide a unifying theory for vari...
详细信息
Cooperation among constraint solvers is difficult because different solving paradigms have different theoretical foundations. Recent works have shown that abstract interpretation can provide a unifying theory for various constraint solvers. In particular, it relies on abstract domains which capture constraint languages as ordered structures. The key insight of this paper is viewing cooperation schemes as abstract domains combinations. We propose a modular framework in which solvers and cooperation schemes can be seamlessly added and combined. This differs from existing approaches such as SMT where the cooperation scheme is usually fixed (e.g., Nelson-Oppen). We contribute to two new cooperation schemes: (i)interval propagators completionthat allows abstract domains to exchange bound constraints, and (ii)delayed productwhich exchanges over-approximations of constraints between two abstract domains. Moreover, the delayed product is based on delayed goal of logicprogramming, and it shows that abstract domains can also capture control aspects of constraint solving. Finally, to achieve modularity, we propose theshared productto combine abstract domains and cooperation schemes. Our approach has been fully implemented, and we provide various examples on the flexible job shop scheduling problem.
This paper presents a logic framework for modeling the interaction among deductive databases in a peer-to-peer (P2P) environment. Each peer joining a P2P system provides or imports data from its neighbors by using a s...
详细信息
This paper presents a logic framework for modeling the interaction among deductive databases in a peer-to-peer (P2P) environment. Each peer joining a P2P system provides or imports data from its neighbors by using a set of mapping rules, that is, a set of semantic correspondences to a set of peers belonging to the same environment. By using mapping rules, as soon as it enters the system, a peer can participate and access all data available in its neighborhood, and through its neighborhood it becomes accessible to all the other peers in the system. A query can be posed to any peer in the system and the answer is computed by using locally stored data and all the information that can be consistently imported from the neighborhood. Two different types of mapping rules are defined: mapping rules allowing to import a maximal set of atoms not leading to inconsistency (called maximal mapping rules) and mapping rules allowing to import a minimal set of atoms needed to restore consistency (called minimal mapping rules). Implicitly, the use of maximal mapping rules states it is preferable to import as long as no inconsistencies arise;whereas the use of minimal mapping rules states that it is preferable not to import unless a inconsistency exists. The paper presents three different declarative semantics of a P2P system: (i) the Max Weak Model Semantics, in which mapping rules are used to import as much knowledge as possible from a peer's neighborhood without violating local integrity constraints;(ii) the Min Weak Model Semantics, in which the P2P system can be locally inconsistent and the information provided by the neighbors is used to restore consistency, that is, to only integrate the missing portion of a correct, but incomplete database;(iii) the Max-Min Weak Model Semantics that unifies the previous two different perspectives captured by the Max Weak Model Semantics and Min Weak Model Semantics. This last semantics allows to characterize each peer in the neighborhood as a
Multi-core and highly-connected architectures have become ubiquitous, and this has brought renewed interest in language-based approaches to the exploitation of parallelism. Since its inception, logicprogramming has b...
详细信息
Multi-core and highly-connected architectures have become ubiquitous, and this has brought renewed interest in language-based approaches to the exploitation of parallelism. Since its inception, logicprogramming has been recognized as a programming paradigm with great potential for automated exploitation of parallelism. The comprehensive survey of the first twenty years of research in parallel logicprogramming, published in 2001, has served since as a fundamental reference to researchers and developers. The contents are quite valid today, but at the same time the field has continued evolving at a fast pace in the years that have followed. Many of these achievements and ongoing research have been driven by the rapid pace of technological innovation, that has led to advances such as very large clusters, the wide diffusion of multi-core processors, the game-changing role of general-purpose graphic processing units, and the ubiquitous adoption of cloud computing. This has been paralleled by significant advances within logicprogramming, such as tabling, more powerful static analysis and verification, the rapid growth of Answer Set programming, and in general, more mature implementations and systems. This survey provides a review of the research in parallel logicprogramming covering the period since 2001, thus providing a natural continuation of the previous survey. In order to keep the survey self-contained, it restricts its attention to parallelization of the major logicprogramming languages (Prolog, Datalog, Answer Set programming) and with an emphasis on automated parallelization and preservation of the sequential observable semantics of such languages. The goal of the survey is to serve not only as a reference for researchers and developers of logicprogramming systems, but also as engaging reading for anyone interested in logic and as a useful source for researchers in parallel systems outside logicprogramming. Under consideration in theory and practice of Logi
In this paper we consider Epistemic logic Programs, which extend Answer Set programming (ASP) with "epistemic operators" and "epistemic negation", and a recent approach to the semantics of such pro...
详细信息
In this paper we consider Epistemic logic Programs, which extend Answer Set programming (ASP) with "epistemic operators" and "epistemic negation", and a recent approach to the semantics of such programs in terms of World Views. We propose some observations on the existence and number of world views. We show how to exploit an extended ASP semantics in order to: (i) provide a characterization of world views, different from existing ones;(ii) query world views and query the whole set of world views.
Decision support systems play an important role in medical fields as they can augment clinicians to deal more efficiently and effectively with complex decision-making processes. In the diagnosis of headache disorders,...
详细信息
Decision support systems play an important role in medical fields as they can augment clinicians to deal more efficiently and effectively with complex decision-making processes. In the diagnosis of headache disorders, however, existing approaches and tools are still not optimal. On the one hand, to support the diagnosis of this complex and vast spectrum of disorders, the International Headache Society released in 1988 the International Classification of Headache Disorders (ICHD), now in its 3rd edition: a 200 pages document classifying more than 300 different kinds of headaches, where each is identified via a collection of specific nontrivial diagnostic criteria. On the other hand, the high number of headache disorders and their complex criteria make the medical history process inaccurate and not exhaustive both for clinicians and existing automatic tools. To fill this gap, we present head-asp, a novel decision support system for the diagnosis of headache disorders. Through a REST Web Service, head-asp implements a dynamic questionnaire that complies withICHD-3by exploiting two logical modules to reach a complete diagnosis while trying to minimize the total number of questions being posed to patients. Finally, head-asp is freely available on-line and it is receiving very positive feedback from the group of neurologists that is testing it.
暂无评论