Answer Set programming (ASP) and propositional satisfiability (SAT) are closely related. In some recent work we have shown that, on a wide set of logic programs called "tight", the main search procedures use...
详细信息
Answer Set programming (ASP) and propositional satisfiability (SAT) are closely related. In some recent work we have shown that, on a wide set of logic programs called "tight", the main search procedures used by ASP and SAT systems are equivalent, i.e., that they explore search trees with the same branching nodes. In this paper, we focus on the experimental evaluation of different search strategies, heuristics and their combinations that have been shown to be effective in the SAT community, in ASP systems. Our results show that, despite the strong link between ASP and SAT, it is not always the case that search strategies, heuristics and/or their combinations that currently dominate in SAT are also bound to dominate in ASP. We provide a detailed experimental evaluation for this phenomenon and we shed light on future development of efficient Answer Set solvers.
In this work we present a backjumping technique for Disjunctive logicprogramming (DLP) under the Answer Set Semantics. It builds upon related techniques that had originally been proposed for propositional satisfiabil...
详细信息
In this work we present a backjumping technique for Disjunctive logicprogramming (DLP) under the Answer Set Semantics. It builds upon related techniques that had originally been proposed for propositional satisfiability testing, which have been adapted to non-disjunctive Answer Set programming (ASP) recently [1,2]. We focus on backjumping without clause learning. We provide a new theoretical framework for backjumping on Disjunctive logic Programs. We optimize the reason calculus, reducing the information to be stored, while fully preserving the correctness and the efficiency of the jumping technique. We implement the proposed technique in DLV, the state-of-the-art DLP system. We have conducted several experiments on hard random problems in order to assess the impact of backjumping. Our conclusion is that when lookahead is employed, there is basically no advantage when enabling backjumping. However, when lookahead is disabled, we can observe that the number of choices in general decreases by a non-negligible factor. In our (naive) implementation this gain is (often more than) compensated by the additional overhead incurred by the reason calculus. It is unclear whether one can reduce this overhead by a more efficient implementation. We therefore conjecture that, at least on hard unstructured instances, backjumping only has an impact when lookahead is not active and when clause learning is employed in addition.
Despite all efforts on intelligent grounding, state-of-the-art answer set solvers still have huge memory requirements, because they compute the ground instantiation of the input program before the actual reasoning sta...
详细信息
Despite all efforts on intelligent grounding, state-of-the-art answer set solvers still have huge memory requirements, because they compute the ground instantiation of the input program before the actual reasoning starts. This prevents ASP to be effective on several classes of problems. In this paper we integrate answer set generation and constraint solving to reduce the memory requirements for a class of multi-sorted logic programs with cardinality constraints. We prove some theoretical results, introduce a provably sound and complete algorithm, and report experimental results showing that our approach can solve problem instances with significantly larger domains.
The paper studies reductions of propositional theories in equilibrium logic to logic programs under answer set semantics. Specifically we are concerned with the question of how to transform an arbitrary set of proposi...
详细信息
The paper studies reductions of propositional theories in equilibrium logic to logic programs under answer set semantics. Specifically we are concerned with the question of how to transform an arbitrary set of propositional formulas into an equivalent logic program and what are the complexity constraints on this process. We want the transformed program to be equivalent in a strong sense so that theory parts can be transformed independent of the wider context in which they might be embedded. It was only recently established [2] that propositional theories are indeed equivalent (in a strong sense) to logic programs. Here this result is extended with the following contributions. (i) We show how to effectively obtain an equivalent program starting from an arbitrary theory. (ii) We show that in general there is no polynomial transformation if we require the resulting program to share precisely the vocabulary or signature of the initial theory. (iii) Extending previous work we show how polynomial transformations can be achieved if one allows the resulting program to contain new atoms. The program obtained is still in a strong sense equivalent to the original theory, and the answer sets of the theory can be retrieved from it.
This paper describes an on-going work aimed at designing and deploying a system for the surveillance and monitoring of an archaeological site, namely the "Valley of the Temples" in Agrigento, Italy. Given th...
详细信息
FlowUML is a logic-based system to validate information flow policies at the requirements specification phase of UML based designs. It uses Horn clauses to specify information flow polices that can be checked against ...
详细信息
ISBN:
(纸本)9728865252
FlowUML is a logic-based system to validate information flow policies at the requirements specification phase of UML based designs. It uses Horn clauses to specify information flow polices that can be checked against flow information extracted from UML sequence diagrams. FlowUML policies can be written at a coarse grain level of caller-callee relationships or at a finer level involving passed attributes.
Understanding classes and methods is a key activity in object-oriented programming, since classes represent the primary abstractions from which applications are built, while methods contain the actual program logic. T...
详细信息
Understanding classes and methods is a key activity in object-oriented programming, since classes represent the primary abstractions from which applications are built, while methods contain the actual program logic. The main problem of this task is to quickly grasp the purpose and inner structure of a class. To achieve this goal, one must be able to overview multiple methods at once. In this paper, we present microprints, pixel-based representations of methods enriched with semantic information. We present three specialized microprints each dealing with a specific aspect we want to understand of methods: (1) state access, (2) control flow, and (3) invocation relationship
Attack graphs represent known attack sequences that attackers can use to penetrate computer networks. Recently, many researchers have proposed techniques for automatically generating attack graphs for a given computer...
详细信息
This paper introduces a novel, more systematic approach to the modeling and control design of machine logic control. The machine logic control is considered to be an event-driven system. A matrix representation of Pet...
详细信息
This paper introduces a novel, more systematic approach to the modeling and control design of machine logic control. The machine logic control is considered to be an event-driven system. A matrix representation of Petri nets is used, for modeling the structure of discrete event-driven system. Its dynamics is described by state-transition equations. The control of discrete event system is introduced by drawing a clear distinction between the plant and the controller model. The proposed approach is illustrated by simulation and experimental results for the lab-scale linear drive position initialization procedure.
We overview the current status and future directions of the Cobalt project. Cobalt is a domain-specific language for implementing compiler optimizations as guarded rewrite rules. Cobalt optimizations operate over a C-...
详细信息
暂无评论