×

zbMATH — the first resource for mathematics

A first order forward chaining approach for answer set computing. (English) Zbl 1258.68033
Erdem, Esra (ed.) et al., Logic programming and nonmonotonic reasoning. 10th international conference, LPNMR 2009, Potsdam, Germany, September 14–18, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-04237-9/pbk). Lecture Notes in Computer Science 5753. Lecture Notes in Artificial Intelligence, 196-208 (2009).
Summary: The natural way to use answer set programming (ASP) to represent knowledge in artificial intelligence or to solve a constraint satisfaction problem is to elaborate a first-order logic program with default negation. In a preliminary step this program, with variables, is translated in an equivalent propositional one by a first tool: the grounder. Then, the propositional program is given to a second tool: the solver. This last one computes (if they exist) one or many answer sets (models) of the program, each answer set encoding one solution of the initial problem. Until today, almost all ASP systems apply this two-steps computation.
In this work, our major contribution is to introduce a new approach of answer set computing that escapes the preliminary phase of rule instantiation by integrating it in the search process. Our methodology applies a forward chaining of first-order rules that are grounded on the fly by means of previously produced constants. We have implemented this strategy in our new ASP solver ASPeRiX. The first benefit of our work is to avoid the bottleneck of instantiation phase arising for some problems because of the huge amount of memory needed to ground all rules of a program, even if these rules are not really useful in certain cases. The second benefit is to make the treatment of function symbols easier and without syntactic restriction provided that rules are safe.
For the entire collection see [Zbl 1175.68008].

MSC:
68N17 Logic programming
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68T30 Knowledge representation
Software:
ASPeRiX; ASSAT; Gringo
PDF BibTeX XML Cite
Full Text: DOI