UC San Diego

This work discusses two new extensions of Answer Set Programming (ASP) and a new computational method for solving the following two problems : (1) given a finite propositional logic program P which has a stable model, find a stable model M of P, and (2) given a finite propositional logic program P which has no stable model, find a maximal program P' which is a subset of P which has a stable model and find a stable model M' of P'. The first extension called Preference Set Constraint (PSC) programming extends the Set Constraint programming introduced by Marek and Remmel to allow reasoning with preferences. The generality of PSC programming is demonstrated by showing that PSC programming can be used to express optimal stable models of Answer Set Optimization (ASO) of Brewka, Niemela and Truszczynski; general preferences of Son and Pontelli. An extension of PSC programming can be used to express preferred answer sets and weakly preferred answer sets of Brewka and Eiter. It is proven that under mild assumptions the problem of determining whether M is a preferred PSC stable model of a PSC program P is CoNP-complete. The second extension called Hybrid ASP (H-ASP) allows to combine logical reasoning and numerical algorithms. One of the goals of H- ASP is to allow users to reason about dyamical systems that exhibit both continuous and discrete aspects. In this work it is shown how H-ASP can be used to compute a finite horizon optimal strategy for an agent acting in a dynamic domain. The discussion leads to an introduction of a new programming language H-ASP#. It is proven that the computational complexity of H-ASP# program W# is EXP- complete in the length of W#. The new computational method for solving the above mentioned two problems called the Metropolized Forward Chaining (MFC) algorithm is based on combining the Metropolis algorithm and the Forward Chaining algorithm of Marek, Nerode and Remmel. The use of Stochastic Approximation Monte Carlo (SAMC) algorithm of in the MFC instead of the Metropolis algorithm is discussed. The results of the computational experiments conducted with the two versions of MFC are reported. Values for some of the parameters to be used with MFC are suggested. An asymptotic result for certain choices of parameters is proven