the Dagstuhl Initiative for systematic benchmarking in answer set programming (ASP) is discussed. Benchmarking is needed in ASP to establish a good practices in the fields of satisfiablity testing and constraint progr...
详细信息
ISBN:
(纸本)354020721X
the Dagstuhl Initiative for systematic benchmarking in answer set programming (ASP) is discussed. Benchmarking is needed in ASP to establish a good practices in the fields of satisfiablity testing and constraint programming. the ASP is facing difficulty of not having a common input language and disagreement on all functionalities. the benchmarking system facilitates the execution of ASP solvers under the same conditions, quaranteeing reproducible and reliable performance outputs.
the exploitation of ASP systems for solving real application problems pointed out the need of combining the expressive power of ASP programming withthe efficient data management features of existing DBMSs. this paper...
详细信息
ISBN:
(纸本)354020721X
the exploitation of ASP systems for solving real application problems pointed out the need of combining the expressive power of ASP programming withthe efficient data management features of existing DBMSs. this paper presents DLVDB, an extension to the DLV system allowing to instantiate logic programs directly on databases and to handle input and output data distributed on several databases.
One of the major reasons for the success of answer set programming in recent years was the shift from a theorem proving to a constraint programming view: problems are represented such that stable models, respectively ...
详细信息
ISBN:
(纸本)354020721X
One of the major reasons for the success of answer set programming in recent years was the shift from a theorem proving to a constraint programming view: problems are represented such that stable models, respectively answer sets, rather than theorems correspond to solutions. this shift in perspective proved extremely fruitful in many areas. We believe that going one step further from a "hard" to a "soft" constraint programming paradigm, or, in other words, to a paradigm of qualitative optimization, will prove equally fruitful. In this paper we try to support this claim by showing that several generic problems in logic based problem solving can be understood as qualitative optimization problems, and that these problems have simple and elegant formulations given adequate optimization constructs in the knowledge representation language.
the language of nonmonotonic causal theories, defined by Norman McCain and Hudson Turner, is an important formalism for representing properties of actions. For causal theories of a special kind, called definite, a sim...
详细信息
ISBN:
(纸本)354020721X
the language of nonmonotonic causal theories, defined by Norman McCain and Hudson Turner, is an important formalism for representing properties of actions. For causal theories of a special kind, called definite, a simple translation into the language of logic programs under the answer set semantics is available. In this paper we define a similar translation for causal theories of a more general form, called almost definite. Such theories can be used, for instance, to characterize the transitive closure of a binary relation. the new translation leads to an implementation of a subclass of almost definite causal theories that employs the answer set solver SMODELS as the search engine.
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.
A new system CMODELS-2 which is able to fix ASSAT's disadvantages was presented. It was found that the new system organizes the search process more efficiently than ASSAT as it does not explore the same part of th...
详细信息
ISBN:
(纸本)354020721X
A new system CMODELS-2 which is able to fix ASSAT's disadvantages was presented. It was found that the new system organizes the search process more efficiently than ASSAT as it does not explore the same part of the search tree more than once. the input language of CMODELS is generated by the preprocessor LPARSE. CMODELS is an answer set solver that uses SAT solvers as search engines.
this paper gives a summary of the First Answer Set programming System Competition that was held in conjunction withthe Ninthinternationalconference on logicprogramming and nonmonotonicreasoning. the aims of the c...
详细信息
ISBN:
(纸本)9783540721994
this paper gives a summary of the First Answer Set programming System Competition that was held in conjunction withthe Ninthinternationalconference on logicprogramming and nonmonotonicreasoning. the aims of the competition were twofold: first, to collect challenging benchmark problems, and second, to provide a platform to assess a broad variety of Answer Set programming systems. the competition was inspired by similar events in neighboring fields, where regular benchmarking has been a major factor behind improvements in the developed systems and their ability to address practical applications.
We consider the simplification of logic programs under the stable-model semantics, with respect to the notions of strong and uniform equivalence between logic programs, respectively. Both notions have recently been co...
详细信息
ISBN:
(纸本)354020721X
We consider the simplification of logic programs under the stable-model semantics, with respect to the notions of strong and uniform equivalence between logic programs, respectively. Both notions have recently been considered for nonmonotoniclogic programs (the latter dates back to the 1980s, though) and provide semantic foundations for optimizing programs with input. Extending previous work, we investigate syntactic and semantic rules for program transformation, based on proper notions of consequence. We furthermore provide encodings of these notions in answer-set programming, and give characterizations of programs which are semantically equivalent to positive and Horn programs, respectively. Finally, we investigate the complexity of program simplification and determining semantical equivalence, showing that the problems range between coNP and II2P complexity, and we present some tractable cases.
this paper is a sequel to Leitgeb(7). We show that certain networks called 'inhibition nets' may be regarded as mechanisms drawing nonmonotonic inferences if only an interpretation of net states as states of b...
详细信息
this paper is a sequel to Leitgeb(7). We show that certain networks called 'inhibition nets' may be regarded as mechanisms drawing nonmonotonic inferences if only an interpretation of net states as states of belief is introduced. We prove that each of the cumulative logical systems studied by Kraus et al.(6) are sound and complete with respect to certain classes of such interpreted inhibition nets. thus, there is an adequate cognitive network semantics for the systems C, CL, P, CM, and M of (nonmonotonic) logic.
暂无评论