Aggregates are among the most frequently used linguistic extensions of answer set programming. The result of an aggregation may introduce new constants during the instantiation of the input program, a feature known as...
详细信息
Aggregates are among the most frequently used linguistic extensions of answer set programming. The result of an aggregation may introduce new constants during the instantiation of the input program, a feature known as value invention. When the aggregation involves literals whose truth value is undefined at instantiation time, modern grounders introduce several instances of the aggregate, one for each possible interpretation of the undefined literals. This paper introduces new data structures and techniques to handle such cases, and more in general aggregations on the same aggregate set identified in the ground program in input. The proposed solution reduces the memory footprint of the solver without sacrificing efficiency. On the contrary, the performance of the solver may improve thanks to the addition of some simple entailed clauses which are not easily discovered otherwise, and since redundant computation is avoided during propagation. Empirical evidence of the potential impact of the proposed solution is given.
We address the problem of verifying the satisfiability of Constrained Horn Clauses (CHCs) based on theories of inductively defined data structures, such as lists and trees. We propose a transformation technique whose ...
详细信息
We address the problem of verifying the satisfiability of Constrained Horn Clauses (CHCs) based on theories of inductively defined data structures, such as lists and trees. We propose a transformation technique whose objective is the removal of these data structures from CHCs, hence reducing their satisfiability to a satisfiability problem for CHCs on integers and booleans. We propose a transformation algorithm and identify a class of clauses where it always succeeds. We also consider an extension of that algorithm, which combines clause transformation with reasoning on integer constraints. Via an experimental evaluation we show that our technique greatly improves the effectiveness of applying the Z3 solver to CHCs. We also show that our verification technique based on CHC transformation followed by CHC solving, is competitive with respect to CHC solvers extended with induction.
In Constraint programming, a portfolio solver combines a variety of different constraint solvers for solving a given problem. This fairly recent approach enables to significantly boost the performance of single solver...
详细信息
In Constraint programming, a portfolio solver combines a variety of different constraint solvers for solving a given problem. This fairly recent approach enables to significantly boost the performance of single solvers, especially when multicore architectures are exploited. In this work, we give a brief overview of the portfolio solver sunny-cp, and we discuss its performance in the MiniZinc Challenge-the annual international competition for Constraint programming solvers-where it won two gold medals in 2015 and 2016.
We define a novel, extensional, three-valued semantics for higher-order logic programs with negation. The new semantics is based on interpreting the types of the source language as three-valued Fitting-monotonic funct...
详细信息
We define a novel, extensional, three-valued semantics for higher-order logic programs with negation. The new semantics is based on interpreting the types of the source language as three-valued Fitting-monotonic functions at all levels of the type hierarchy. We prove that there exists a bijection between such Fitting-monotonic functions and pairs of two-valued-result functions where the first member of the pair is monotone-antimonotone and the second member is antimonotone-monotone. By deriving an extension of consistent approximation fixpoint theory (Denecker et al. 2004) and utilizing the above bijection, we define an iterative procedure that produces for any given higher-order logic program a distinguished extensional model. We demonstrate that this model is actually a minimal one. Moreover, we prove that our construction generalizes the familiar well-founded semantics for classical logic programs, making in this way our proposal an appealing formulation for capturing the well-founded semantics for higher-order logic programs.
In the non-fuzzy (e.g., interval) case, if two expert's opinions are consistent, then, as the result of fusing the knowledge of these two experts, we take the intersection of the two sets (e.g., intervals) describ...
详细信息
ISBN:
(纸本)9783030219208;9783030219192
In the non-fuzzy (e.g., interval) case, if two expert's opinions are consistent, then, as the result of fusing the knowledge of these two experts, we take the intersection of the two sets (e.g., intervals) describing the expert's opinions. In the experts are inconsistent, i.e., if the intersection is empty, then a reasonable idea is to assume that at least one of these experts is right, and thus, to take the union of the two corresponding sets. In practice, expert opinions are often imprecise;this imprecision can be naturally described in terms of fuzzy logic - a technique specifically designed to describe such imprecision. In the fuzzy case, expert opinions are not always absolutely consistent or absolutely inconsistent, they may be consistent to a certain degree. In this case, we show how the above natural idea of fusing expert opinions can be extended to the fuzzy case. As a result, we, in general, get not "and" (which would correspond to the intersection), not "or" (which would correspond to the union), but rather an appropriate fuzzy combination of "and"- and "or"-operations.
In this paper, we introduce an alternative approach to Temporal Answer Set programming that relies on a variation of Temporal Equilibrium logic (TEL) for finite traces. This approach allows us to even out the expressi...
详细信息
In this paper, we introduce an alternative approach to Temporal Answer Set programming that relies on a variation of Temporal Equilibrium logic (TEL) for finite traces. This approach allows us to even out the expressiveness of TEL over infinite traces with the computational capacity of (incremental) Answer Set programming (ASP). Also, we argue that finite traces are more natural when reasoning about action and change. As a result, our approach is readily implementable via multi-shot ASP systems and benefits from an extension of ASP's full-fledged input language with temporal operators. This includes future as well as past operators whose combination offers a rich temporal modeling language. For computation, we identify the class of temporal logic programs and prove that it constitutes a normal form for our approach. Finally, we outline two implementations, a generic one and an extension of the ASP system clingo. Under consideration for publication in theory and practice of logic programming (TPLP)
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,...
详细信息
This paper describes how the logicprogramming System XSB combines top-down and bottomup computation through the mechanisms of variant tabling and subsumptive tabling with abstraction, respectively. It is well known t...
详细信息
This paper describes how the logicprogramming System XSB combines top-down and bottomup computation through the mechanisms of variant tabling and subsumptive tabling with abstraction, respectively. It is well known that top-down evaluation of logical rules in Prolog has a procedural interpretation as recursive procedure invocation (Kowalski 1986). Tabling adds the intuition of short-circuiting redundant computations (Warren 1992). This paper shows how to introduce into tabled logic program evaluation a bottom-up component, whose procedural intuition is the initialization of a data structure, in which a relation is initially computed and filled, on first demand, and then used throughout the remainder of a larger computation for efficient lookup. This allows many Prolog programs to be expressed fully declaratively, programs which formerly required procedural features, such as assert, to be made efficient.
This paper presents PFLP, a library for probabilistic programming in the functional logicprogramming language Curry. It demonstrates how the concepts of a functional logicprogramming language support the implementat...
详细信息
暂无评论