Skip to main content

A method for solving np search based on model expansion and grounding

Resource type
Thesis type
(Thesis) M.Sc.
Date created
The logical task of model expansion (MX) has been proposed as a declarative constraint programming framework for solving search and decision problems. We present a method for solving NP search problems based on MX for first order logic extended with inductive definitions and cardinality constraints. The method involves grounding, and execution of a propositional solver, such as a SAT solver. Our grounding algorithm applies a generalization of the relational algebra to construct a ground formula representing the solutions to an instance. We demonstrate the practical feasibility of our method with an implementation, called MXG. We present axiomatizations of several NP-complete benchmark problems, and experimental results comparing the performance of MXG with state-of-the-art Answer Set programming (ASP) solvers. The performance of MXG is competitive with, and often better than, the ASP solvers on the problems studied.
Copyright statement
Copyright is held by the author.
The author has not granted permission for the file to be printed nor for the text to be copied and pasted. If you would like a printable copy of this thesis, please contact
Scholarly level
Member of collection
Download file Size
etd3275.pdf 2.23 MB

Views & downloads - as of June 2023

Views: 0
Downloads: 0