the purpose of this paper is to provide a brief overview of how logicprogramming technology has been used by our team in addressing the problem of tertiary protein structure determination. the proposed approach tackl...
详细信息
ISBN:
(纸本)9783642042379
the purpose of this paper is to provide a brief overview of how logicprogramming technology has been used by our team in addressing the problem of tertiary protein structure determination. the proposed approach tackles the problem from the perspective of viewing protein structure as a folding of protein sequences in a discrete representation of space (a crystal lattice structure). logicprogramming and constraint programming technologies can be effectively used to provide an elegant and effective Solution.
We show that the concepts of strong and uniform equivalence of logic programs can be generalized to an abstract algebraic setting of operators on complete lattices. Our results imply characterizations of strong and un...
详细信息
For some problems with many solutions, like planning and phylogeny reconstruction, one way to compute more desirable solutions is to assign weights to Solutions, and then pick the ones whose weights are over (resp. be...
详细信息
ISBN:
(纸本)9783642042379
For some problems with many solutions, like planning and phylogeny reconstruction, one way to compute more desirable solutions is to assign weights to Solutions, and then pick the ones whose weights are over (resp. below) a threshold. this paper studies Computing weighted Solutions to such problems ill Answer Set programming. We investigate two sorts of methods for computing weighted solutions: one suggests modifying the representation of the problem and the other suggests modifying the search procedure of the answer set solver. We show the applicability and the effectiveness of these methods in phylogeny reconstruction.
this paper reports oil the Second Answer Set programming Competition. the competitions in areas of Satisfiability checking, Pseudo-Boolean constraint solving and Quantified Boolean Formula evaluation have proven to be...
详细信息
ISBN:
(纸本)9783642042379
this paper reports oil the Second Answer Set programming Competition. the competitions in areas of Satisfiability checking, Pseudo-Boolean constraint solving and Quantified Boolean Formula evaluation have proven to be a strong driving force for a community to develop better performing systems. Following this experience, the Answer Set programming competition series was set up in 2007, and ran as part of the internationalconference oil logicprogramming and nonmonotonicreasoning (LPNMR). this second competition, held in conjunction with LPNMR 2009, differed from the first one in two important ways. First, while the original competition was restricted to systems designed for the answer set programming language, the sequel was open to systems designed for other modeling languages, as well. Consequently, among the contestants of the second competition were a CLP(FD) team and three model generation systems for (extensions of) classical logic. Second, this latest competition covered not only satisfiability problems but also optimization ones. We present and discuss the set-up and the results of the competition.
Many relevant intractable problems become tractable if some problem parameter is fixed. However, various problems exhibit very different computational properties, depending on how the runtime required for solving them...
详细信息
Many relevant intractable problems become tractable if some problem parameter is fixed. However, various problems exhibit very different computational properties, depending on how the runtime required for solving them is related to the fixed parameter chosen. the theory of parameterized complexity deals with such issues, and provides general techniques for identifying fixed-parameter tractable and fixed-parameter intractable problems. We study the parameterized complexity of various problems in AI and nonmonotonicreasoning. We show that a number of relevant parameterized problems in these areas are fixed-parameter tractable. Among these problems are constraint satisfaction problems with bounded treewidth and fixed domain, restricted forms of conjunctive database queries, restricted satisfiability problems, propositional logicprogramming under the stable model semantics where the parameter is the dimension of a feedback vertex set of the program's dependency graph, and circumscriptive inference from a positive k-CNF restricted to models of bounded size. We also show that circumscriptive inference from a general propositional theory, when the attention is restricted to models of bounded size, is fixed-parameter intractable and is actually complete for a novel fixed-parameter complexity class. (C) 2002 Elsevier Science B.V. All rights reserved.
Several proposals of the semantics of aggregates are based oil different extensions of the stable model semantics, which makes it difficult to compare them. In this note, building upon a reductive approach to designin...
详细信息
ISBN:
(纸本)9783642042379
Several proposals of the semantics of aggregates are based oil different extensions of the stable model semantics, which makes it difficult to compare them. In this note, building upon a reductive approach to designing aggregates, we provide reformulations of some existing semantics in terms of propositional formulas, which help us compare the semanitcs and understand their properties in terms of their propositional formula representations. We also present a generalization of semantics of aggregates without involving grounding, and define loop formulas for programs with aggregates guided by the reductive approach.
We present trichotomy results characterizing the complexity of reasoning with disjunctive logic programs. To this end, we introduce a certain definition schema for classes of programs based on a set of allowed arities...
详细信息
ISBN:
(纸本)9783642042379
We present trichotomy results characterizing the complexity of reasoning with disjunctive logic programs. To this end, we introduce a certain definition schema for classes of programs based on a set of allowed arities of rules. We show that each such class of programs has a finite representation, and for each of the classes definable in the schema we characterize the complexity of the existence of an answer set problem. Next, we derive similar characterizations of the complexity of skeptical and credulous reasoning with disjunctive logic programs. Such results are of potential interest. Oil the one hand, they reveal some reasons responsible for the hardness of computing answer sets. On the other hand. they identify classes of problem instances, for which the problem is "easy" (in P) or "easier than in general" (in NP).
the second postulate of Katsuno and Mendelzon characterizes irrelevant updates. We show that the postulate has to be modified, if nonmonotonic assumptions are considered. Our characterization of irrelevant updates is ...
详细信息
ISBN:
(纸本)354039625X
the second postulate of Katsuno and Mendelzon characterizes irrelevant updates. We show that the postulate has to be modified, if nonmonotonic assumptions are considered. Our characterization of irrelevant updates is based on a dependency framework, which provides an alternative semantics of multidimensional dynamic logicprogramming.
this paper introduces a novel monotonic modal logic, able to characterise reflexive autoepistemic reasoning of the nonmonotonic variant of modal logic SW5: we add a second new modal operator into the original language...
详细信息
ISBN:
(纸本)9783319616605;9783319616599
this paper introduces a novel monotonic modal logic, able to characterise reflexive autoepistemic reasoning of the nonmonotonic variant of modal logic SW5: we add a second new modal operator into the original language of SW5, and show that the resulting formalism called MRAE* is strong enough to capture the minimal model notion underlying some major forms of nonmonotoniclogic among which are autoepistemic logic, default logic, and nonmonotoniclogicprogramming. the paper ends with a discussion of a general strategy, naturally embedding several nonmonotoniclogics of similar kinds.
We explore the use, of Constraint;Lopic programming (CLP) as a platform for experimenting with planning domains ill presence of multiple interacting agents. We develop a novel constraint-based action language B-MAP th...
详细信息
ISBN:
(纸本)9783642042379
We explore the use, of Constraint;Lopic programming (CLP) as a platform for experimenting with planning domains ill presence of multiple interacting agents. We develop a novel constraint-based action language B-MAP that enables the declarative description of large classes of multi-agent and multi-valued domains. B-MAP supports several complex features, including combined effects. concurrency constraint, interacting actions,. mid delayed effects.
暂无评论