We report on how the declarative nature of answer set programming allows one to model and solve some well-known and challenging classes of problems in the general domain of bioinformatics. We briefly survey the main r...
详细信息
We report on how the declarative nature of answer set programming allows one to model and solve some well-known and challenging classes of problems in the general domain of bioinformatics. We briefly survey the main results appeared in the areas of genomics, structure prediction, and systems biology.
The Stable Roommates problem with Ties and Incomplete lists (SRTI) is a matching problem characterized by the preferences of agents over other agents as roommates, where the preferences may have ties or be incomplete....
详细信息
The Stable Roommates problem with Ties and Incomplete lists (SRTI) is a matching problem characterized by the preferences of agents over other agents as roommates, where the preferences may have ties or be incomplete. SRTI asks for a matching that is stable and, sometimes, optimizes a domain-independent fairness criterion (e.g. Egalitarian). However, in real-world applications (e.g. assigning students as roommates at a dormitory), we usually consider a variety of domain-specific criteria depending on preferences over the habits and desires of the agents. With this motivation, we introduce a knowledge-based method to SRTI considering domain-specific knowledge and investigate its real-world application for assigning students as roommates at a university dormitory.
A novel logic program like language, weight constraint rules, is developed for answer set programming purposes. It generalizes normal logic programs by allowing weight constraints in place of literals to represent, e....
详细信息
A novel logic program like language, weight constraint rules, is developed for answer set programming purposes. It generalizes normal logic programs by allowing weight constraints in place of literals to represent, e.g., cardinality and resource constraints and by providing optimization capabilities. A declarative semantics is developed which extends the stable model semantics of normal programs. The computational complexity of the language is shown to be similar to that of normal programs under the stable model semantics. A simple embedding of general weight constraint rules to a small subclass of the language called basic constraint rules is devised. An implementation of the language, the SMODELS System, is developed based on this embedding. It uses a two level architecture consisting of a front-end and a kernel language implementation. The front-end allows restricted use of variables and functions and compiles general weight constraint rules to basic constraint rules. A major part of the work is the development of an efficient search procedure for computing stable models for this kernel language. The procedure is compared with and empirically tested against satisfiability checkers and an implementation of the stable model semantics. It offers a competitive implementation of the stable model semantics for normal programs and attractive performance for problems where the new types of rules provide a compact representation. (C) 2002 Elsevier Science B.V. All rights reserved.
We extend probabilistic action language pBC+ with the notion of utility in decision theory. The semantics of the extended pBC+ can be defined as a shorthand notation for a decision-theoretic extension of the probabili...
详细信息
We extend probabilistic action language pBC+ with the notion of utility in decision theory. The semantics of the extended pBC+ can be defined as a shorthand notation for a decision-theoretic extension of the probabilistic answer set programming language LPMLN. Alternatively, the semantics of pBC+ can also be defined in terms of Markov decision process (MDP), which in turn allows for representing MDP in a succinct and elaboration tolerant way as well as leveraging an MDP solver to compute a pBC+ action description. The idea led to the design of the system pbcplus2mdp, which can find an optimal policy of a pBC+ action description using an MDP solver.
In this paper, a Gaifman-Shapiro-style module architecture is tailored to the case of SMODELS programs under the stable model semantics. The composition of SMODELS program modules is suitably limited by module conditi...
详细信息
In this paper, a Gaifman-Shapiro-style module architecture is tailored to the case of SMODELS programs under the stable model semantics. The composition of SMODELS program modules is suitably limited by module conditions which ensure the compatibility of the module system with stable models. Hence the semantics of an entire SMODELS program depends directly on stable models assigned to its modules. This result is formalized as a module theorem which truly strengthens V. Lifschitz and H. Turner's splitting-set theorem (June 1994, Splitting a logic program. In Logic programming: Proceedings of the Eleventh International Conference on Logic programming, Santa Margherita Ligure, Italy, P. V. Hentenryck, Ed. MIT Press, 23-37) for the class of SMODELS programs. To streamline generalizations in the future, the module theorem is first proved for normal programs and then extended to cover SMODELS programs using a translation from the latter class of programs to the former class. Moreover, the respective notion of module-level equivalence, namely modular equivalence, is shown to be a proper congruence relation: it is preserved under substitutions of modules that are modularly equivalent. Principles for program decomposition are also addressed. The strongly connected components of the respective dependency graph can be exploited in order to extract it module structure when there is no explicit a priori knowledge about the modules of a program. The paper includes a practical demonstration of tools that have been developed for automated (de)composition of SMODELS programs.
In this paper we provide an alternative semantics for Equilibrium Logic and its monotonic basis, the logic of Here-and-There (also known as Godel's G(3) logic) that relies on the idea of denotation of a formula, t...
详细信息
In this paper we provide an alternative semantics for Equilibrium Logic and its monotonic basis, the logic of Here-and-There (also known as Godel's G(3) logic) that relies on the idea of denotation of a formula, that is, a function that collects the set of models of that formula. Using the three-valued logic G(3) as a starting point and an ordering relation (for which equilibrium/stable models are minimal elements) we provide several elementary operations for sets of interpretations. By analysing structural properties of the denotation of formulas, we show some expressiveness results for G(3) such as, for instance, that conjunction is not expressible in terms of the other connectives. Moreover, the denotational semantics allows us to capture the set of equilibrium models of a formula with a simple and compact set expression. We also use this semantics to provide several formal definitions for entailment relations that are usual in the literature, and further introduce a new one called strong entailment. We say that alpha strongly entails beta when the equilibrium models of alpha boolean AND gamma are also equilibrium models of beta boolean AND gamma for any context gamma. We also provide a characterisation of strong entailment in terms of the denotational semantics, and give an example of a sufficient condition that can be applied in some cases.
Integrating diverse formalisms into modular knowledge representation systems offers increased expressivity, modeling convenience, and computational benefits. We introduce the concepts of abstract inference modules and...
详细信息
Integrating diverse formalisms into modular knowledge representation systems offers increased expressivity, modeling convenience, and computational benefits. We introduce the concepts of abstract inference modules and abstract modular inference systems to study general principles behind the design and analysis of model generating programs, or solvers, for integrated multi-logic systems. We show how modules and modular systems give rise to transition graphs, which are a natural and convenient representation of solvers, an idea pioneered by the SAT community. These graphs lend themselves well to extensions that capture such important solver design features as learning. In the paper, we consider two flavors of learning for modular formalisms, local and global. We illustrate our approach by showing how it applies to answer set programming, propositional logic, multi-logic systems based on these two formalisms and, more generally, to satisfiability modulo theories. (C) 2016 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).
作者：
Alviano, MarioDodaro, CarmineUniv Calabria
Dept Math & Comp Sci Via Pietro Bucci 30B I-87036 Arcavacata Di Rende CS Italy Univ Genoa
Dept Informat Bioengn Robot & Syst Engn Viale Francesco Causa 15 I-16145 Genoa GE Italy
Modern, efficient answer set programming solvers implement answerset search via non-chronological backtracking algorithms. The extension of these algorithms to answerset enumeration is nontrivial. In fact, adding bl...
详细信息
Modern, efficient answer set programming solvers implement answerset search via non-chronological backtracking algorithms. The extension of these algorithms to answerset enumeration is nontrivial. In fact, adding blocking constraints to discard already computed answersets is inadequate because the introduced constraints may not fit in memory or deteriorate the efficiency of the solver. On the other hand, the algorithm implemented by CLASP, which can run in polynomial space, requires to modify the answerset search procedure. The algorithm is revised in this paper so as to make it almost independent from the underlying answerset search procedure, provided that the procedure accepts as input a logic program and a list of assumption literals, and returns an answerset (and associated branching literals). In fact, thanks to an alternative view in terms of transition systems, the revised algorithm is suitable to easily accommodate the enumerate of models of other Boolean languages, among them classical models of propositional theories. On a pragmatic level, the paper presents two implementations of the enumeration algorithm, in WASP for answerset enumeration, and in GLUCOSE for classical models enumeration. The implemented systems are compared empirically to the state of the art solver CLASP.
An answerset is a plain set of literals which has no further structure that would explain why certain literals are part of it and why others are not. We show how argumentation theory can help to explain why a literal...
详细信息
An answerset is a plain set of literals which has no further structure that would explain why certain literals are part of it and why others are not. We show how argumentation theory can help to explain why a literal is or is not contained in a given answerset by defining two justification methods, both of which make use of the correspondence between answersets of a logic program and stable extensions of the assumption-based argumentation (ABA) framework constructed from the same logic program. Attack Trees justify a literal in argumentation-theoretic terms, i.e. using arguments and attacks between them, whereas ABA-Based answerset Justifications express the same justification structure in logic programming terms, that is using literals and their relationships. Interestingly, an ABA-Based answerset Justification corresponds to an admissible fragment of the answerset in question, and an Attack Tree corresponds to an admissible fragment of the stable extension corresponding to this answerset.
Constraint solving is applied in different application contexts. Examples thereof are the configuration of complex products and services, the determination of production schedules, and the determination of recommendat...
详细信息
Constraint solving is applied in different application contexts. Examples thereof are the configuration of complex products and services, the determination of production schedules, and the determination of recommendations in online sales scenarios. Constraint solvers apply, for example, search heuristics to assure adequate runtime performance and prediction quality. Several approaches have already been developed showing that machine learning (ML) can be used to optimize search processes in constraint solving. In this article, we provide an overview of the state of the art in applying ML approaches to constraint solving problems including constraint satisfaction, SAT solving, answer set programming (ASP) and applications thereof such as configuration, constraint-based recommendation, and model-based diagnosis. We compare and discuss the advantages and disadvantages of these approaches and point out relevant directions for future work.
暂无评论