Proceedings of the American Society for Information Science and Technology

Dix J., Subrahmanian V.S., Pick G.

There are numerous applications where an agent a needs to reason about the beliefs of another agent, as well as about the actions that other agents may take. In [T. Eiter, V.S. Subrahmanian, G. Pick, Heterogeneous Active Agents, I: Semantics, Artificial Intelligence 108(1–2) (1999) 179–255] the concept of an agent program is introduced, and a language within which the operating principles of an agent can be declaratively encoded on top of imperative data structures is defined. In this paper we first introduce certain belief data structures that an agent needs to maintain. Then we introduce the concept of a Meta Agent Program ( map ), that extends the framework of Refs. [T. Eiter, V.S. Subrahmanian, Heterogeneous Active Agents, II: Algorithms and Complexity, Artificial Intelligence 108(1–2) (1999) 257–307; loc. cit.] so as to allow agents to perform metareasoning. We build a formal semantics for map s, and show how this semantics supports not just beliefs agent a may have about agent b 's state, but also beliefs about agents b 's beliefs about agent c 's actions, beliefs about b 's beliefs about agent c 's state, and so on. Finally, we provide a transansation that takes any map as input and converts it into an agent program such that there is a one–one correspondence between the semantics of the map and the semantics of the resulting agent program. This correspondence allows an implementation of map s to be built on top of an implementation of agent programs.

Ruggieri S.

In this paper, we investigate the decidability problem of logic program semantics and observables, focusing in particular on the least Herbrand model (or M -semantics), the C -semantics, and the S -semantics. We introduce bounded logic programs , and show that they coincide with programs such that every ground query has finitely many SLD-refutations via any selection rule. In particular, bounded programs strictly include the well-studied class of acceptable logic programs. We show that the mentioned declarative semantics are decidable when considering acceptable programs and programs bounded by recursive level mappings. Interestingly, the decision procedures have direct implementations in the logic programming paradigm itself as Prolog meta-programs. We relate semantics decidability to program testing. In our terminology, the testing problem consists of checking whether or not the formal semantics of a program includes a given finite set of atoms. With this definition, semantics decidability and the testing problem are equivalent. The decision procedures are then recognized to be automatic tools for testing logic programs. The meta-programming approach reveals to be successful in modeling extensions such as arithmetic built-in's, negation, modular programming and some other declarative semantics. Also, we present some preliminary experimental results and an efficient compilation-oriented approach that overcome the overhead due to meta-programming.

Ben-Eliyahu-Zohary R., Palopoli L., Zemlyanker V.

Sometimes it is more natural to express knowledge in disjunctive Datalog rather than in ordinary Datalog. Several highly complex variants of disjunctive Datalog have been proposed in the past and their expressive power has been studied. In this paper we investigate tractable fragments of disjunctive Datalog. Algorithms are presented to answer queries defined using these fragments and their complexity analyzed. Furthermore, the expressive power of these tractable subsets is studied. The most expressive of the languages considered here is shown to express, in some sense explained in the paper, all polynomial time queries. This is the first identified fragment of disjunctive Datalog with this property.

King A.

Sharing information is useful in specialising, optimising and parallelising logic programs and thus sharing analysis is an important topic of both abstract interpretation and logic programming. Sharing analyses infer which pairs of program variables can never be bound to terms that contain a common variable. We generalise a classic pair-sharing analysis from Herbrand unification to trace sharing over rational tree constraints. This is useful for reasoning about programs written in SICStus and Prolog-III because these languages use rational tree unification as the default equation solver.

Wang K.

In this paper, we propose an argumentation-based semantic framework, called DAS, for disjunctive logic programming. The basic idea is to translate a disjunctive logic program into an argumentation-theoretic framework. One unique feature of our proposed framework is to consider the disjunctions of negative literals as possible assumptions so as to represent incomplete information. In our framework, three semantics preferred disjunctive hypothesis (PDH), complete disjunctive hypothesis (CDH) and well-founded disjunctive hypothesis (WFDH) are defined by three kinds of acceptable hypotheses to represent credulous, moderate and skeptical reasoning in artificial intelligence (AI), respectively. Furthermore, our semantic framework can be extended to a wider class than that of disjunctive programs (called bi-disjunctive logic programs). In addition to being a first serious attempt in establishing an argumentation-theoretic framework for disjunctive logic programming, DAS integrates and naturally extends many key semantics, such as the minimal models, extended generalized closed world assumption (EGCWA), the well-founded model, and the disjunctive stable models. In particular, novel and interesting argumentation-theoretic characterizations of the EGCWA and the disjunctive stable semantics are shown. Thus the framework presented in this paper does not only provide a new way of performing argumentation (abduction) in disjunctive deductive databases, but also is a simple, intuitive and unifying semantic framework for disjunctive logic programming.

Alferes J.J., Leite J.A., Pereira L.M., Przymusinska H., Przymusinski T.C.

In this paper we investigate updates of knowledge bases represented by logic programs. In order to represent negative information, we use generalized logic programs which allow default negation not only in rule bodies but also in their heads. We start by introducing the notion of an update P⊕U of one logic program P by another logic program U . Subsequently, we provide a precise semantic characterization of P⊕U , and study some basic properties of program updates. In particular, we show that our update programs generalize the notion of interpretation update. We then extend this notion to compositional sequences of logic programs updates P 1 ⊕P 2 ⊕⋯, defining a dynamic program update, and thereby introducing the paradigm of dynamic logic programming . This paradigm significantly facilitates modularization of logic programming, and thus modularization of non-monotonic reasoning as a whole. Specifically, suppose that we are given a set of logic program modules, each describing a different state of our knowledge of the world. Different states may represent different time points or different sets of priorities or perhaps even different viewpoints. Consequently, program modules may contain mutually contradictory as well as overlapping information. The role of the dynamic program update is to employ the mutual relationships existing between different modules to precisely determine, at any given module composition stage, the declarative as well as the procedural semantics of the combined program resulting from the modules.

Heaton A., Abo-Zaed M., Codish M., King A.

The domain of positive Boolean functions, Pos , is by now well established for the analysis of the variable dependencies that arise within logic programs. Analyses based on Pos that use binary decision diagrams (BDDs) have been shown to be efficient for a wide range of practical programs. However, independent of the representation, a Pos analysis can never come with any efficiency guarantees because of its potential exponential behaviour. This paper considers groundness analysis based on a simple subdomain of Pos and compares its precision with that of Pos .

Sagonas K., Swift T., Warren D.S.

The well-founded semantics has gained wide acceptance partly because it is a skeptical semantics. That is, the well-founded model posits as unknown atoms which are deemed true or false in other formalisms such as stable models. This skepticism makes the well-founded model not only useful in itself, but also suitable as a basis for other forms of non-monotonic reasoning. For instance, since algorithms to compute stable models are intractable, the atoms relevant to such algorithms can be limited to those undefined in the well-founded model. Thus, an engine that efficiently evaluates programs according to the well-founded semantics can be seen as a prerequisite to practical systems for non-monotonic reasoning. This paper describes the architecture of the Warren Abstract Machine (WAM)-based abstract machine underlying the XSB system. This abstract machine, called the SLG-WAM, uses tabling to efficiently compute the well-founded semantics of non-ground normal logic programs in a goal-directed way. To do so, the SLG-WAM requires sophisticated extensions to its core tabling engine for fixed-order stratified programs. A mechanism must be implemented to represent answers that are neither true nor false, and the delay and simplification operations – which serve to break and to resolve cycles through negation, must be implemented. We describe fully these extensions to our tabling engine, and demonstrate the efficiency of our implementation in two ways. First, we present a theorem that bounds the need for delay to those literals which are not dynamically stratified for a fixed-order computation. Second, we present performance results that indicate that the overhead of delay and simplification to Prolog – or tabled – evaluations is minimal.

Zhou J.

The design, implementation and application of a natural constraint language NCL are presented. At the solver level, to support the solving of a large scope of combinatorial problems, a rich set of conventional constraints is defined within a constraint framework that strongly combines Boolean logic, integer constraints and set reasoning over finite domains. The basic computation model for solving conjunctions of elementary constraints with possible existential and universal quantifications is described using rewrite rules. At the language level, to upgrade the expressive power, a natural syntax (context-dependent), which completely adopts mathematical notations, is designed. To enhance the constraint handling capability, quantification, logical switch, referencing mechanism, global/dynamic constraints, meta expressions, multi-criteria optimization, and search specifications are cooperatively introduced in a single constraint system. Compared to existing modeling languages, a strong feature of NCL is: Data, constraints and control are fully integrated and are clearly separable. Especially, though NCL deals with several data types such as Boolean, integer, set, index, reference, array and tuple, there is no need to declare data explicitly. This context-sensitive data typing makes NCL programs direct, concise and liberal.

Poole D.

The independent choice logic (ICL) is part of a project to combine logic and decision/game theory into a coherent framework. The ICL has a simple possible-worlds semantics characterised by independent choices and an acyclic logic program that specifies the consequences of these choices. This paper gives an abductive characterization of the ICL. The ICL is defined model-theoretically, but we show that it is naturally abductive: the set of explanations of a proposition g is a concise description of the worlds in which g is true. We give an algorithm for computing explanations and show it is sound and complete with respect to the possible-worlds semantics. What is unique about this approach is that the explanations of the negation of g can be derived from the explanations of g . The use of probabilities over choices in this framework and going beyond acyclic logic programs are also discussed.

Iwayama N., Satoh K.

We present a method to compute abduction in logic programming. We translate an abductive framework into a normal logic program with integrity constraints and show the correspondence between generalized stable models and stable models for the translation of the abductive framework. Abductive explanations for an observation can be found from the stable models for the translated program by adding a special kind of integrity constraint for the observation. Then, we show a bottom-up procedure to compute stable models for a normal logic program with integrity constraints. The proposed procedure excludes the unnecessary construction of stable models on early stages of the procedure by checking integrity constraints during the construction and by deriving some facts from integrity constraints. Although a bottom-up procedure has the disadvantage of constructing stable models not related to an observation for computing abductive explanations in general, our procedure avoids the disadvantage by expecting which rule should be used for satisfaction of integrity constraints and starting bottom-up computation based on the expectation. This expectation is not only a technique to scope rule selection but also an indispensable part of our stable model construction because the expectation is done for dynamically generated constraints as well as the constraint for the observation.