1,721,013 research outputs found
Using LPNMR for problem specification and code generation
No full textInvited talk. Springer-Verlag Lecture Notes in Computer Scienc
Automated reformulation of specifications by safe delay of constraints
No full textIn this paper we propose a form of reasoning on specifications of combinatorial problems, with the goal of reformulating them so that they are more efficiently solvable. The reformulation technique highlights constraints that can be safely "delayed", and solved afterwards. Our main contribution is the characterization (with soundness proof) of safe-delay constraints with respect to a criterion on the specification, thus obtaining a mechanism for the automated reformulation of specifications applicable to a great variety of problems, e.g., graph coloring, bin-packing, and job-shop scheduling. This is an advancement with respect to the forms of reasoning done by state-of-the-art-systems, which typically just detect linearity of specifications. Another contribution is an experimentation on the effectiveness of the proposed technique using six different solvers, which reveals promising time savings. (c) 2006 Elsevier B.V. All rights reserved
Approximate Inference in Default Logic and Circumscription
No full textWe propose a technique for dealing with the high complexity of reasoning under propositional default logic and circumscription. The technique is based on the notion of approximation: A logical consequence relation is computed by means of sound and progressively “more complete” relations, as well as complete and progressively “more sound” ones. Both sequences generated in this way converge to the original consequence relation and are easier to compute. Moreover they are given a clear semantics based on multivalued logic. With this technique unsoundness and incompleteness are introduced in a controlled way and precisely characterized
A SURVEY OF COMPLEXITY RESULTS FOR NONMONOTONIC LOGICS
No full textThis paper surveys the main results appearing in the literature on the computational complexity of non-monotonic inference tasks. We not only give results about the tractability/intractability of the individual problems but we also analyze sources of complexity and explain intuitively the nature of easy/hard cases. We focus mainly on non-monotonic formalisms, like default logic, autoepistemic logic, circumscription, closed-world reasoning, and abduction, whose relations with logic programming are clear and well studied. Complexity as well as recursion-theoretic results are surveyed
Circumscribing datalog: expressive power and complexity
No full textAbstractIn this paper we study a generalization of datalog, the language of function-free definite clauses. It is known that standard datalog semantics (i.e., least Herbrand model semantics) can be obtained by regarding programs as theories to be circumscribed with all predicates to be minimized. The extension proposed here, called datalogcirc, consists in considering the general form of circumscription, where some predicates are minimized, some predicates are fixed, and some vary. We study the complexity and the expressive power of the language thus obtained. We show that this language (and, actually, its non-recursive fragment) is capable of expressing all the queries in DB-co-NP and, as such, is much more powerful than standard datalog, whose expressive power is limited to a strict subset of PTIME queries. Both data and combined complexities of answering datalogcirc queries are studied. Data complexity is proved to be co-NP-complete. Combined complexity is shown to be in general hard for co-NE and complete for co-NE in the case of Herbrand bases containing k distinct constant symbols, where k is bounded
- …
