We propose a systematic approach for generating linear implied constraints that link the values returned by several automata with accumulators after consuming the same input sequence. The method handles automata whose...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
We propose a systematic approach for generating linear implied constraints that link the values returned by several automata with accumulators after consuming the same input sequence. The method handles automata whose accumulators are increased by (or reset to) some non-negative integer value on each transition. We evaluate the impact of the generated linear invariants on conjunctions of two families of time-series constraints.
This paper investigates the use of a Prolog coded SMT solver in tackling a well known constraints problem, namely packing a given set of consecutive squares into a given rectangle, and details the developments in the ...
详细信息
ISBN:
(纸本)9781450352918
This paper investigates the use of a Prolog coded SMT solver in tackling a well known constraints problem, namely packing a given set of consecutive squares into a given rectangle, and details the developments in the solver that this motivates. The packing problem has a natural model in the theory of quantifier-free integer difference logic, a theory supported by many SMT solvers. The solver used in this work exploits a data structure consisting of an incremental Floyd-Warshall matrix paired with a watch matrix that monitors the entailment status of integer difference constraints. It is shown how this structure can be used to build unsatisfiable theory cores on the fly, which in turn allows theory learning to be incorporated into the solver. Further, it is shown that a problem-specific and non-standard approach to learning can be taken where symmetry breaking is incorporated into the learning stage, magnifying the effect of learning. It is argued that the declarative framework allows the solver to be used in this white box manner and is a strength of the solver. The approach is experimentally evaluated.
HEX-programs are an extension of answer set programs (ASP) with external sources. To this end, external atoms provide a bidirectional interface between the program and an external source. The traditional evaluation al...
详细信息
BigDatalog is an extension of Datalog that achieves performance and scalability on both Apache Spark and multicore systems to the point that its graph analytics outperform those written in GraphX. Looking back, we see...
详细信息
We describe the new version of the PDDL-to-ASP translator plasp. First, it widens the range of accepted PDDL features. Second, it contains novel planning encodings, some inspired by SAT planning and others exploiting ...
详细信息
ISBN:
(纸本)9783319616605;9783319616599
We describe the new version of the PDDL-to-ASP translator plasp. First, it widens the range of accepted PDDL features. Second, it contains novel planning encodings, some inspired by SAT planning and others exploiting ASP features such as well-foundedness. All of them are designed for handling multi-valued fluents in order to capture both PDDL as well as SAS planning formats. Third, enabled by multi-shot ASP solving, it offers advanced planning algorithms also borrowed from SAT planning. As a result, plasp provides us with an ASP-based framework for studying a variety of planning techniques in a uniform setting. Finally, we demonstrate in an empirical analysis that these techniques have a significant impact on the performance of ASP planning.
We develop an approach to test suite generation for Constrained Combinatorial Testing (CCT), one of the most widely studied combinatorial testing techniques, based on Answer Set programming (ASP). The resulting catnap...
详细信息
ISBN:
(纸本)9783319616605;9783319616599
We develop an approach to test suite generation for Constrained Combinatorial Testing (CCT), one of the most widely studied combinatorial testing techniques, based on Answer Set programming (ASP). The resulting catnap system accepts a CCT instance in fact format and combines it with a first-order encoding for generating test suites, which can subsequently be solved by any off-the-shelf ASP systems. We evaluate the effectiveness of our approach by empirically contrasting it to the best known bounds obtained via dedicated implementations.
We describe the first automatic approach for merging coreference annotations obtained from multiple annotators into a single gold standard. Merging is subject to hard constraints (consistency) and optimization criteri...
详细信息
ISBN:
(纸本)9783319616605;9783319616599
We describe the first automatic approach for merging coreference annotations obtained from multiple annotators into a single gold standard. Merging is subject to hard constraints (consistency) and optimization criteria (minimal divergence from annotators) and involves an equivalence relation over a large number of elements. We describe two representations of the problem in Answer Set programming and four objective functions suitable for the task. We provide two structurally different real-world benchmark datasets based on the METU-Sabanci Turkish Treebank, and we report our experiences in using the Gringo, Clasp, and Wasp tools for computing optimal adjudication results on these datasets.
Forgetting is an operation that allows the removal, from a knowledge base, of middle variables no longer deemed relevant, while preserving all relationships (direct and indirect) between the remaining variables. When ...
详细信息
ISBN:
(纸本)9783319616605;9783319616599
Forgetting is an operation that allows the removal, from a knowledge base, of middle variables no longer deemed relevant, while preserving all relationships (direct and indirect) between the remaining variables. When investigated in the context of Answer-Set programming, many different approaches to forgetting have been proposed, following different intuitions, and obeying different sets of properties. This talk will present a bird's-eye view of the complex landscape composed of the properties and operators of forgetting defined over the years in the context of Answer-Set programming, zooming in on recent findings triggered by the formulation of the so-called strong persistence, a property based on the strong equivalence between an answer-set program and the result of forgetting modulo the forgotten atoms, which seems to best encode the requirements of the forgetting operation.
The Nurse Scheduling problem (NSP) is a combinatorial problem that consists of assigning nurses to shifts according to given practical constraints. In previous years, several approaches have been proposed to solve dif...
详细信息
ISBN:
(纸本)9783319616605;9783319616599
The Nurse Scheduling problem (NSP) is a combinatorial problem that consists of assigning nurses to shifts according to given practical constraints. In previous years, several approaches have been proposed to solve different variants of the NSP. In this paper, an ASP encoding for one of these variants is presented, whose requirements have been provided by an Italian hospital. We also design a second encoding for the computation of "optimal" schedules. Finally, an experimental analysis has been conducted on real data provided by the Italian hospital using both encodings. Results are very positive: the state-of-the-art ASP system CLINGO is able to compute one year schedules in few minutes, and it scales well even when more than one hundred nurses are considered.
We present the latest, substantially improved, version of NoHR, a reasoner designed to answer queries over hybrid theories composed of an OWL ontology in Description logics and a set of non-monotonic rules in logic Pr...
详细信息
ISBN:
(纸本)9783319616605;9783319616599
We present the latest, substantially improved, version of NoHR, a reasoner designed to answer queries over hybrid theories composed of an OWL ontology in Description logics and a set of non-monotonic rules in logicprogramming. Whereas the need to combine the distinctive features of these two knowledge representation and reasoning approaches stems from real world applications, their integration is nevertheless theoretically challenging due to their substantial semantical differences. NoHR has been developed as a plug-in for the widely used ontology editor Protege - in fact, the first hybrid reasoner of its kind for Protege, building on a combination of reasoners dedicated to OWL and rules - but it is also available as a library, allowing for its integration within other environments and applications. Compared to previous versions of NoHR, this is the first that supports all polynomial OWL profiles, and even beyond, allowing for its usage with real-world ontologies that do not fit within a single profile. In addition, NoHR has now an enhanced integration with its rule engine, which provides support for a vast number of standard built-in Prolog predicates that considerably extend its usability.
暂无评论