Library

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    Resolution versus Search: Two Strategies for SAT (2000)
    Springer
    Journal of automated reasoning 24 (2000), S. 225-275 
    Details
    ISSN: 1573-0670
    Keywords: propositional satisfiability ; backtracking search ; resolution ; computational complexity ; knowledge compilation ; empirical studies
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract The paper compares two popular strategies for solving propositional satisfiability, backtracking search and resolution, and analyzes the complexity of a directional resolution algorithm (DR) as a function of the “width” (w *) of the problem"s graph. Our empirical evaluation confirms theoretical prediction, showing that on low-w * problems DR is very efficient, greatly outperforming the backtracking-based Davis–Putnam–Logemann–Loveland procedure (DP). We also emphasize the knowledge-compilation properties of DR and extend it to a tree-clustering algorithm that facilitates query answering. Finally, we propose two hybrid algorithms that combine the advantages of both DR and DP. These algorithms use control parameters that bound the complexity of resolution and allow time/space trade-offs that can be adjusted to the problem structure and to the user"s computational resources. Empirical studies demonstrate the advantages of such hybrid schemes.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1006303512524
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Bucket Elimination: a Unifying Framework for Processing Hard and Soft Constraints (1997)
    Springer
    Constraints 2 (1997), S. 51-55 
    Details
    ISSN: 1572-9354
    Keywords: search ; variable elimination ; graphs
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract This position paper argues that extending the CSP model to a richer set of tasks such as, constraint optimization, probabilistic inference and decision theoretic tasks can be done within a unifying framework called ‘‘bucket elimination’’. The framework allows uniform hybrids for combining elimination and conditioning guided by the problem's structure and for explicating the tradeoffs between space and time and between time and accuracy.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1009796922698
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Maintenance scheduling problems as benchmarks for constraint algorithms (1999)
    Springer
    Annals of mathematics and artificial intelligence 26 (1999), S. 149-170 
    Details
    ISSN: 1573-7470
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The paper focuses on evaluating constraint satisfaction search algorithms on application based random problem instances. The application we use is a well-studied problem in the electric power industry: optimally scheduling preventive maintenance of power generating units within a power plant. We show how these scheduling problems can be cast as constraint satisfaction problems and used to define the structure of randomly generated non-binary CSPs. The random problem instances are then used to evaluate several previously studied algorithms. The paper also demonstrates how constraint satisfaction can be used for optimization tasks. To find an optimal maintenance schedule, a series of CSPs are solved with successively tighter cost-bound constraints. We introduce and experiment with an “iterative learning” algorithm which records additional constraints uncovered during search. The constraints recorded during the solution of one instance with a certain cost-bound are used again on subsequent instances having tighter cost-bounds. Our results show that on a class of randomly generated maintenance scheduling problems, iterative learning reduces the time required to find a good schedule.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1018906911996
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    On computing minimal models (1996)
    Springer
    Annals of mathematics and artificial intelligence 18 (1996), S. 3-27 
    Details
    ISSN: 1573-7470
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper addresses the problem of computing the minimal models of a given CNF propositional theory. We present two groups of algorithms. Algorithms in the first group are efficient when the theory is almost Horn, that is, when there are few non-Horn clauses and/or when the set of all literals that appear positive in any non-Horn clause is small. Algorithms in the other group are efficient when the theory can be represented as an acyclic network of low-arity relations. Our algorithms suggest several characterizations of tractable subsets for the problem of finding minimal models.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02136172
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Propositional semantics for disjunctive logic programs (1994)
    Springer
    Annals of mathematics and artificial intelligence 12 (1994), S. 53-87 
    Details
    ISSN: 1573-7470
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we study the properties of the class of head-cycle-free extended disjunctive logic programs (HEDLPs), which includes, as a special case, all nondisjunctive extended logic programs. We show that any propositional HEDLP can be mapped in polynomial time into a propositional theory such that each model of the latter corresponds to an answer set, as defined by stable model semantics, of the former. Using this mapping, we show that many queries over HEDLPs can be determined by solving propositional satisfiability problems. Our mapping has several important implications: It establishes the NP-completeness of this class of disjunctive logic programs; it allows existing algorithms and tractable subsets for the satisfiability problem to be used in logic programming; it facilitates evaluation of the expressive power of disjunctive logic programs; and it leads to the discovery of useful similarities between stable model semantics and Clark's predicate completion.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01530761
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Book
    Book
    Constraint processing / (2003)
    San Francisco :Morgan Kaufmann Publishers,
    Details
    Title: Constraint processing /
    Author: Dechter, Rina
    Publisher: San Francisco :Morgan Kaufmann Publishers,
    Year of publication: 2003
    Pages: xx, 481 p.
    ISBN: 1-558-60890-7
    Type of Medium: Book
    Language: English
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    ZIB Catalog
    Zuse Institute Berlin get availability status
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...