Dynamical Properties of Answer Set Programs

Answer Set Programming: Towards Efficient and Scalable Knowledge Representation and Reasoning

Volume

Papers from the 2001 AAAI Spring Symposium

Contents

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.