Dynamical Properties of Answer Set Programs

Howard A. Blair

Solutions to problems are often not unique. A representation of a problem as a theory in some logical formalism often admits a number of models representing solutions. The solution-representing models are perhaps required to come from a particular class. The typical strategy is to represent a class of problem instances E, for example the problem of determining a Hamiltonian circuit in a digraph if there is one, as a theory TE, and a specific instance I of E, e.g. a specific digraph, as a theory T1 in such a way that certain kinds of models of the combined theory TE + TI represent the solutions, i.e. in the example, the required Hamiltonian circuits in I, as the result of a mapping from answer sets (the models) solutions of I. As a specific formalism for answer set programming, DATALOG programs with negation and their stable models have received a large amount of attention. While more recent work has built upon this forrealism, for our purposes here we shall stay with a formalism more closely tied directly to DATALOG programs. It will be seen that extensions of the basic formalism can be profitably incorporated in our dynamical systems approach. This work identifies a certain class of DATALO programs which we call call fully normalized.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.