We develop an approach called bounded combinatorial reconfiguration for solving combinatorial reconfiguration problems based on answer set programming. The general task is to study the solution spaces of source combin...
详细信息
ISBN:
(纸本)9783031436185;9783031436192
We develop an approach called bounded combinatorial reconfiguration for solving combinatorial reconfiguration problems based on answer set programming. The general task is to study the solution spaces of source combinatorial problems and to decide whether or not there are sequences of feasible solutions that have special properties. The resulting recongo solver covers all metrics of the solver track in the most recent international competition on combinatorial reconfiguration (CoRe Challenge 2022). recongo ranked first in the shortest metric of the single-engine solvers track.
In this paper, the identification of context-free grammars based on the presentation of samples is investigated. The main idea of solving this problem proposed in the literature is reformulated in two different ways: ...
详细信息
ISBN:
(数字)9783030504236
ISBN:
(纸本)9783030504236;9783030504229
In this paper, the identification of context-free grammars based on the presentation of samples is investigated. The main idea of solving this problem proposed in the literature is reformulated in two different ways: in terms of general constrains and as an answerset program. In a series of experiments, we showed that our answer set programming approach is much faster than our alternative method and the original SAT encoding method. Similarly to a pioneer work, some well-known context-free grammars have been induced correctly, and we also followed its test procedure with randomly generated grammars, making it clear that using our answerset programs increases computational efficiency. The research can be regarded as another evidence that solutions based on the stable model (answerset) semantics of logic programming may be a right choice for complex problems.
We introduce an approach to detecting inconsistencies in large biological networks by using answer set programming. To this end, we build upon a recently proposed notion of consistency between biochemical/genetic reac...
详细信息
We introduce an approach to detecting inconsistencies in large biological networks by using answer set programming. To this end, we build upon a recently proposed notion of consistency between biochemical/genetic reactions and high-throughput profiles of cell activity. We then present an approach based on answer set programming to check the consistency of large-scale data sets. Moreover, we extend this methodology to provide explanations for inconsistencies by determining minimal representations of conflicts. In practice, this can be used to identify unreliable data or to indicate missing reactions.
In this paper we propose an extension of answer set programming (ASP) to deal with (possibly partial) evaluable functions. To this aim, we start from the most general logical counterpart of ASP, Quantified Equilibrium...
详细信息
In this paper we propose an extension of answer set programming (ASP) to deal with (possibly partial) evaluable functions. To this aim, we start from the most general logical counterpart of ASP, Quantified Equilibrium Logic (QEL), and propose a variant QEL(F)(=) where the set of functions is partitioned into Herbrand functions (or constructors) and evaluable functions (or operations). We show how this extension has a direct connection to Scott's Logic of Existence, and introduce several useful derived operators, some of them directly borrowed from Scott's formalisation. Using this general framework for arbitrary theories, we proceed to focus on a syntactic subclass that corresponds to normal logic programs with evaluable functions and equality. We provide a translation of this class into function-free normal programs and consider a safety condition so that the resulting program is also safe, under the usual meaning in ASP. Finally, we also establish a formal comparison to Lin and Wang's approach (FASP) dealing with evaluable total functions.
In the context of pattern mining, the utility of a pattern can be described as a preference ordering over a choice set;it can be actually assessed from very different perspectives and at different abstraction levels. ...
详细信息
ISBN:
(纸本)9783030911676;9783030911669
In the context of pattern mining, the utility of a pattern can be described as a preference ordering over a choice set;it can be actually assessed from very different perspectives and at different abstraction levels. However, while the topic of High-Utility Pattern Mining (HUPM) has been widely studied, the basic assumption is that each item in a knowledge base is associated with one, static utility. In this paper we introduce, among others, the notion of facets for items, which allows to cope with this limitation and, moreover, we show how a more structured representation of available information, coupled with facets defined also for higher abstraction levels, paves the way to new opportunities for HUPM. In particular, the proposed framework allows to introduce some new advanced classes of utility functions in the detection process, whose relevance is also experimentally evaluated. A real use case on paper reviews is exploited to analyze the potentiality of the proposed framework in knowledge creation and discovery. Given the wide variety of analytical scenarios that can be envisioned in this new setting, we take full advantage of the capabilities of answer set programming and its extensions for a fast encoding and testing of the framework.
The goal of the Nurse Scheduling Problem (NSP) is to find an assignment of nurses to shifts according to specific requirements. Given its practical relevance, many researchers have developed different strategies for s...
详细信息
ISBN:
(纸本)9783319701691;9783319701684
The goal of the Nurse Scheduling Problem (NSP) is to find an assignment of nurses to shifts according to specific requirements. Given its practical relevance, many researchers have developed different strategies for solving several variants of the problem. One of such variants was recently addressed by an approach based on answer set programming (ASP), obtaining promising results. Nonetheless, the original ASP encoding presents some intrinsic weaknesses, which are identified and eventually circumvented in this paper. The new encoding is designed by taking into account both intrinsic properties of NSP and internal details of ASP solvers, such as cardinality and weight constraint propagators. The performance gain of CLINGO and wasp is empirically verified on instances from ASP literature. As an additional contribution, the performance of CLINGO and wasp is compared to other declarative frameworks, namely SAT and ILP;the best performance is obtained by CLINGO running the new ASP encoding.
A promising approach to tackle intractable problems is given by combining decomposition methods with dynamic programming algorithms. One such decomposition concept is tree decomposition. In this paper, we provide a ne...
详细信息
ISBN:
(纸本)9780769545967
A promising approach to tackle intractable problems is given by combining decomposition methods with dynamic programming algorithms. One such decomposition concept is tree decomposition. In this paper, we provide a new algorithm using this combined approach for solving reasoning problems in propositional answer set programming.
This paper presents a method that adapting planning description to bring the semantic information into play for service composition through action language C. It shows how service descriptions can be expressed by prec...
详细信息
ISBN:
(纸本)9783642226915
This paper presents a method that adapting planning description to bring the semantic information into play for service composition through action language C. It shows how service descriptions can be expressed by preconditions and effects and the action language C provides a richer syntax and semantic for complex service descriptions. We also presents the algorithm of translating semantic web service described by OWL-S to action language C. Thanks to the structured description and the powerful expression of C. we only consider the initial Situation and the desired goal ignoring details of transition and planning. At last we use satisfiability planning to solve the planning problem by translating the action language into disjunctive logic program.
answer set programming (ASP) is a well known paradigm for knowledge representation and for automating commonsense reasoning. Query-driven implementations of Predicate ASP, e.g., the s(CASP) system, permit top-down exe...
详细信息
ISBN:
(纸本)9783031248405;9783031248412
answer set programming (ASP) is a well known paradigm for knowledge representation and for automating commonsense reasoning. Query-driven implementations of Predicate ASP, e.g., the s(CASP) system, permit top-down execution of answerset programs without the need for grounding them. In this paper we consider the problem of analyzing a jury trial for the crime of homicide. We demonstrate how knowledge related to reaching a guilty/not-guilty verdict can be modeled in ASP, and how s(CASP) can be used to analyze the situations under various assumptions. Detailed justification can be provided for each possible verdict, thanks to s(CASP). The goal, and the main contribution, of this paper is to show how a complex situation-whose analysis has been traditionally considered to be within the purview of only humans-can be automatically analyzed using a query-driven predicate ASP system such as s(CASP). For illustration, we use the well-known fictional case of Commonwealth of Massachusetts v. Johnson used in the cognitive science literature. Frank Johnson and Alan Caldwell had a quarrel, which was later followed by Frank Johnson stabbing Alan Caldwell. However, this seemingly simple case was complex in many ways: the lack of critical information led to different verdicts from different jurors. This paper attempts to formalize the logic behind each story construction using s(CASP) and expanding it to similar situations.
In imperative programming, the Domain-Driven Design methodology helps in coping with the complexity of software development by materializing in code the invariants of a domain of interest. Code is cleaner and more sec...
详细信息
ISBN:
(纸本)9783031520372;9783031520389
In imperative programming, the Domain-Driven Design methodology helps in coping with the complexity of software development by materializing in code the invariants of a domain of interest. Code is cleaner and more secure because any implicit assumption is removed in favor of invariants, thus enabling a fail fast mindset and the immediate reporting of unexpected conditions. This article introduces a notion of template for answer set programming that, in addition to the don't repeat yourself principle, enforces locality of some predicates by means of a simple naming convention. Local predicates are mapped to the usual global namespace adopted bymainstream engines, using universally unique identifiers to avoid name clashes. This way, local predicates can be used to enforce invariants on the expected outcome of a template in a possibly empty context of application, independently by other rules that can be added to such a context. Template applications transpiled this way can be processed by mainstream engines and safely shared with other knowledge designers, even when they have zero knowledge of templates.
暂无评论