The goal of this research is two-fold: investigate the relationships between constraint solving and default reasoning, and formalize and implement a constraint nonmonotonic programming system. In the past, the possible relationships between default reasoning and constraints has been largely ignored by the two research communities, despite the fact that the two areas are intimately related. As a result, semantics and proof theories for the former, and proof techniques for the latter, have been developed almost totally separately. It is often not clear whether techniques developed in one area could be used, directly or indirectly, to solve problems in the other area. Constraint nonmonotonic systems combine the ideas of programming with constraints and knowledge representation and reasoning with defaults. These systems aim at providing a declarative language to implement a variety of hard problems efficiently. Many of these problems involve specifying and solving constraints. The idea of constraint programming allows the embedding of highly efficient, domain-dependent constraint solvers into a general top-down query answering procedure.
Knowledge representation by constraints and solving constraints constitute an important area of research in computational logic, databases, artificial intelligence, and operational research. A large number of practical computational problems can be characterized as the ones of solving constraints. The past research in the field can be classified into two very general areas: formulation of general, domain-independent constraint solving techniques, and development of domain-dependent techniques. The former usually provides characteristics of classes of constraints and general tools for solving them, such as various backward chaining proof procedures for constraint satisfaction problems, while the latter allows one to build efficient mechanisms for solving domain specific constraints. If we say that domain-independent techniques aims at building ``universal'' machines for classes of constraints, then the domain-dependent approach provides a way to address the problem of efficiency for specific applications. These two areas complement each other for the goal of solving constraints. More recently, the research on constraints has been challenged by a number of new constraint problems; e.g. over constraint problems, under constraint problems, hierarchical constraints, prioritised constraints, and the need to accommodate conditional constraints. It is not clear whether and how the conventional techniques could be adopted or extended to solve these problems. Sometimes it it even unclear what exactly the formulation of a constraint problem is. For example, the notion of priority could have different interpretations, some of which are suitable for certain types of applications but not for others. These problems are often approached by investigation of constraint solving techniques for each constraint problem at a time. However, our earlier investigation indicates that some of these constraint problems share a common characteristic; they are nonmonotonic in nature. For example, the relation between priority and default is investigated deeply in a number of papers by Dr. You and his colleagues at University of Alberta. In this research we will attempt to understand these constraint problems as logic programming with default negation. The main advantage is that the proof procedures for logic programming directly provide a ``universal'' machine for computing these constraints. The availability of such a universal machine lays the ground for further investigations of more efficient algorithms. Constraint logic programming languages are developed to accommodate user-defined constraints. In these languages domain specific constraint solvers can be embedded into positive logic programming. However, these systems are not expressive enough to handle more complex constraints such as prioritised constraints and conditional constraints. This is because (i) priority is in general a nonmonotonic language construct; (ii) positive logic programming with constraints assumes the availability of constraint solvers for the underlying constraint problems; and (iii) constraint predicates cannot appear in the head of a clause due to the mechanism of embedding. The idea of constraint nonmonotonic programming systems combines constraint programming with default reasoning. The most general form of a rule in this language is: $$ a_1 \vee ... \vee a_n \leftarrow C_1, ..., C_m, b_1, ..., b_k, not ~d_1,..., not ~d_m$$ where $C_i$'s are constraints and $not~ d_j$'s are {\em default negations}. It reduces to {\em (positive) constraint logic programming} if we remove disjunction $\vee$ and default negations. It reduces to {\em disjunctive logic programming} when $C_i$'s are removed. It is {\em normal logic programming} when both $\vee$ and $C_i$'s are removed. Such a constraint nonmonotonic programming system is interesting in several aspects. (I) It provides a general constraint programming system while allowing efficient constraint solvers (if they are available) to be embedded. (II) The expressive power of default negation and disjunction allows a number of constraint problems to be compiled to normal or disjunctive logic programs. Very often these constraint problems are not known to possess sound and complete query answering procedures (except for an explicit enumeration of all possibilities). (III) With embedded constraint solvers we obtain a system of composing constraints; that is, one is able to express constraints over constraints. In this framework appropriate methodologies could be explored; e.g. the compilation of prioritised constraints may make use of some embedded constraint solvers. The proposed system is novel in its combination of constraint logic programming and default reasoning. The idea has also been investigated by (Kakas ICLP'95) where disjunction is not accommodated and the possibility of handling complex constraint problems not investigated. It is important to comment here that although it is commonly agreed that efficient algorithms for solving constraints tend to be those that are domain specific, some recent research has demonstrated the advantages of the domain-independent approaches. The work by Dr. Niemela and his group has shown that an efficient method of computing stable models provides comparable and often better performance than special purpose satisfiability checkers and some best planning systems. In addition, in dealing with real world problems, especially some complex software systems that involve constraints, trade-offs between effectiveness of coding and the efficiency of the code often need to be made. For example, if the delivery time is more important, efficiency is often compromised. A declarative, general purpose constraint solver allows one to develop application code more effectively, though sometimes with sacrifices of efficiency. \section{Previous Activity} For the last ten years, Dr. You has engaged in research in theories and proof techniques of nonmonotonic reasoning, in particular, default reasoning in logic programming with negation and disjunction. Dr. You is a world class authority on these topics. Here is a summary of the previous activities that are relevant to this proposal. \begin{itemize} \item {\em Semantics of Logic Programming and Nonmonotonic Reasoning} Dr. You (along with Dr. L. Yuan) proposed the one of the only three semantics that have survived for normal logic programs, the {\em regular model semantics}] (You and Yuan PODS '90). Later in (You and Yuan JLP '95) it is shown that a number of extensions to the stable semantics are equivalent to the regular model semantics. The regular model semantics overcomes the drawbacks of the stable model semantics by using a 3-valued logic. Unlike the stable semantics, a regular model for any normal program always exists. It is this feature that leads to a sound and complete (for ground programs), top-down query answering procedure, The relationships between logic programming with negation and other forms of nonmonotonic reasoning has been studied deeply in a number of papers (You et al ICLP'97, Wang et al ECAI'96, Yuan and You JAR'93, Li and You 91). \item {\em Top-Down Query Answering Procedures} In (You et al JICSLP90), a top-down query answering procedure, which is based on a form of abduction, is formulated for disjunctive programs. This procedure serves as the basis for the constraint nonmonotonic system proposed here. \item {\em Relating Constraints, Priority, Defeasible Inheritance, and Defaults} The central theme is this area of research is that logic programming with negation and disjunction is sufficiently expressive for a number of applications; very often a problem can be understood by its representation in logic programming. This theme is elaborated and demonstrated with examples in a recent tutorial (You JICSLP'98). For example, a paper is given at IJCAI'97 on representing defeasible inheritance networks in default logic, which is further improved to a translation to normal logic programs. It is this result that explains a number of difficulties in the path-based approach to defeasible inheritance networks, which can be easily overcome by logic programming technology. In (You et at ICLP'97) a relation between disjunctive logic programming and prioritised constraints is presented. In a serious papers the relationships among priority, defaults, minimal models are studied (e.g. Wang et al ECAI'96, You et al under review by IEEE TDKE). \end{itemize} \section{Objective and Method} The goal of this research is to investigate relations between constraints and default reasoning, and build a constraint nonmonotonic programming system. The following three problems will be researched simultaneously. \begin{itemize} \item {\em Representation of Constraints in Logic Programming} We will be looking for compilation methods that translate some constraint problems into normal or disjunctive logic programs. By compilation, we mean a polynomial time and space translation. Since the translated logic programs are a specific class of logic programs, their properties will be studied, which could be used to simplify and improve the logic programming procedures. If a constraint problem is translated to a normal program, we will run it on the {\bf Smodels} system to obtain some performanace results and analyze them. The properties of these translations will be studied too. \item {\em A Constraint Nonmonotonic Programming System} We have shown earlier that an extended version of the Eshghi-Kowalski procedure is sound and complete for (ground) disjunctive programs under the regular extension semantics (You et al. JICSLP98). The procedure is based on a form of abductive reasoning, and can be used to query, for example, in AI planning and scheduling, whether there is a plan that achieves the goal, and whether there is a schedule that satisfies the specified constraints. The procedure will be extended to nonground programs with a form of constructive negation, and incorporate constraint solving in a way similar to constraint (positive) logic programming languages. Not only may constraint solvers be embedded into the reasoning processes, but also non-conventional constraint problems may be complied to logic programs with these constructs. Thus, logic programming proof procedures can be used as general constraint solvers for a variety of constraint problems. We will look into the possibility of employing the basic mechanisms of Smodels in a top-down query answering procedure. The idea is to compute look-ahead information to prune the search space and guide the backward chaining search (sometimes referred to in the literature as ``look ahead'' techniques). Under the narrower scope where there is no disjunction and embedding of constraint solvers, the procedure we are investigating is in fact a top-down query answering procedure for the Smodels system. Such a procedure seems particularly important in some applications where we are primarily interested in whether a claim is true in one extension, e.g., in a multi-agent system where communications could be just queries to other agents before an agent's action is determined. In these cases, the generation of complete solution sets is usually an overkill, and consequently bears much higher cost in general. In this sense, the procedure that we investigate could be used to complement the current Smodels system. The full, complete system is a longer term research goal. The implementation will be pursued using Prolog technology in a number of stages: \begin{itemize} \item Implement a tabulated Prolog that combines loop checking and tabling. The system differs from that of Stony Brook in that the former is a linear system while the latter is not. The theoretical work is completed now. The system will be implemented soon. \item Implement on top of this tabulated Prolog the regular model semantics. \item Implement an interface with constraint solvers. \end{itemize} \item {\em Applications} Beside testing the system for a variety of toy and small scaled problems, we are interested in how such a constraint system may play out in a programming environment. One major application that we have started looking into is in the area of database implementation. With the exploding market for financial services, scientific databases, and multimedia data applications, often accessed through the World Wide Web, object-relational database systems have emerged as the next great wave of database technology. The development of object-oriented database management systems faces some serious challenges, such as type checking for rich extensions of object-oriented data types and concurrency control for long durational transactions. In many cases, the difficulty of the implementation lies in how to resolve conflicts among many involved entities. These are essentially constraint problems. Default reasoning provides a powerful tool for resolving some of key problems in the implementation of object-relational database management systems. For example, we have recently developed an algorithm for concurrency control of long durational transactions based on the stable model semantics of logic programs with default negation. We plan to build an object-relational database management system by integrating a default reasoning engine with a persistent Java object manager. We believe that this integration will make the implementation of object-relational database servers much easier than using traditional approaches. \end{itemize} \section{Expected Results} In the short term, especially during the visit and sometime thereafter, the following results are expected: \begin{itemize} \item The translations of some constraint problems to normal logic programs are obtained. It is expected that the regular model semantics of these translated programs coincide with the stable model semantics. Thusthey can be run on Smodels to obtain performance results. These results will be compared with those using specialized constraint solvers in case they are already presented in the literature. \item The formulation of a top-down procedure for the regular model semantics which employs the mechanisms of {\bf Smodels} to generate ``forward looking'' information to prune the search space. \item A prototype system will be implemented once the formulation is completed. \end{itemize} \section{Selected Publication} Those labeled with a * are particularly relevant to the proposal here. \vspace{.1in} \noindent * J. You, L. Yuan, and R. Goebel. Regular extension semantics and disjunctive Eshghi-Kowalski procedure. In {\em Proc. Int'l Joint Conference and Symposium on Logic Programming}, MIT Press, Manchester, UK, June 1998. \vspace{.1in} \noindent * J. You. Inheritance with Exceptions and Logic Programming. In {\em Tutorial Proceedings of Int'l Joint Conference and Symposium on Logic Programming}, Manchester, UK, June 1998. \vspace{.1in} \noindent * J. You, X. Wang, L. Yuan. Compiling defeasible inheritance networks to general logic programs. Under review by {\em Artificial Intelligence} as a research note. A preliminary version appeared in {\em Proc. IJCAI '97}. \vspace{.1in} \noindent * J. You, X. Wang, and L. Yuan. Nonmonotonic reasoning with prioritised argumentation. Under review by {\em IEEE TDKE}. A preliminary version appeared in {\em Nonmonotonic Extensions of Logic Programming}, LNAI 1216, 1997. \vspace{.1in} \noindent L. Yuan and J. You. Coherence approach to logic program revision. {\em IEEE Transactions on Data and Knowledge Engineering}, 10(1), pp 108-119, 1998. \vspace{.1in} \noindent * J. You, X. Wang, L. Yuan. Disjunctive logic programming as constrained inferences. {\em Proc. 14th Int'l Conf. on Logic Programming}, Leuven, Belgium, pp. 361-375, MIT Press, July 1997. \vspace{.1in} \noindent J. You, L. Yuan, R. Goebel. An abductive semantics for disjunctive logic programs and its proof procedure. {\em Proc. 17th FST and TCS (Foundations of Software Technology and Theoretical Computer Science)}, LNCS 1346, pp. 138-153, Kharagpur, India, Dec 1997. \vspace{.1in} \noindent J. You, R. Cartwright, and Ming Li. Iterative belief revision in extended logic programming. {\em Theoretical Computer Science}, 170(1-2), pp 383-406, 1996. \vspace{.1in} \noindent X. Wang, J. You, L. Yuan. Circumscription by inference rules with priority. In {\em Proc. 12th European Conf. on Artificial Intelligence}, Wolfgang Wahlster (ed.), pages 110-115, 1996. \vspace{.1in} \noindent * J. You and L. Yuan. On the equivalence of semantics for normal logic programs. {\em Journal of Logic Programming}, 22(3):211-222, March 1995. \vspace{.1in} \noindent J. You, S. Ghosh, L. Yuan, R. Goebel. An introspective framework for paraconsistent logic programs. In {\em Proc. Int'l Symposium on Logic Programming}. MIT Press, pages 384-398, Portland, Oregon, Dec. 1995. \vspace{.1in} \noindent J.~You and L.~Yuan. A three-valued semantics for deductive databases and logic programs. {\em Journal of Computer and System Sciences}, 49(2): 334-361, Oct. 1994. A preliminary version appears in {\em PODS'90.} \vspace{.1in} \noindent J. You and R. Cartwright. Tractable argumentation semantics via iterative belief revision. In {\em Proc. Int'l Symposium on Logic Programming}, Ithaca, New York, MIT Press, pages 239-254, Nov. 1994. \vspace{.1in} \noindent J. You and L. Li. Two cumulativity results on J- and PJ-default logic. In {\em Proc. 10th Canadian Conf. on Artificial Intelligence}, pages 219-226, May 1994. \vspace{.1in} \noindent J.~You, L. Li and L. Yuan. Construction of belief sets for logic programs and default theories. {\em Journal of Computers and Artificial Intelligence, the Special Issue on Deductive Databases}, 13(2-3): 159-178, 1994. \vspace{.1in} \noindent L.~Yuan and J.~You. Autoepistemic circumscription and logic programming. {\em Journal of Automated Reasoning}, 10: 143-160, 1993. \vspace{.1in} \noindent L. Yuan and J. You. Knowledge base revision using circumscription. In {\em Proc. 3rd Int'l Conf. on DOOD}, pages 444-458, Dec. 1993. \vspace{.1in} \noindent L.~Li and J.~You. Making default inferences from logic programs. {\em Computational Intelligence}, 7:142--153, 1991. \end{document}