We consider positive rules in which the conclusion may contain existentially quantified variables, which makes reasoning tasks (such as Deduction) undecidable. These rules, called "ForallExists-rules," have the same logical form as TGD (tuple-generating dependencies) in databases and as conceptual graph rules. The aim of this paper is to provide a clearer picture of the frontier between decidability and non-decidability of reasoning with these rules. We show that Deduction remains undecidable with a single rule; then we show that none of the known abstract decidable classes is recognizable. Turning our attention to concrete decidable classes, we provide new classes and classify all known classes by inclusion. Finally, we study, in a systematic way, the question "given two decidable sets of rules, is their union decidable?" and provide an answer for all known decidable cases except one.

A wide range of problems, from contingent and multiagent planning to process/service orchestration, can be viewed as games. In many of these, it is natural to spec- ify the possible behaviors procedurally. In this paper, we develop a logical framework for specifying these types of problems/games based on the situation calculus and ConGolog. The framework incorporates game-theoretic path quantifiers as in ATL. We show that the framework can be used to model such problems in a natural way. We also show how verification/synthesis techniques can be used to solve problems expressed in the framework. In particular, we develop a method for dealing with infinite state settings using fixpoint approximation and “characteristic graphs”.

We present a framework for reasoning about actions that not only solves the frame and ramification problems, but also the state default problem—the problem to determine what normally holds at a given time point. Yet, the framework is general enough not to be tied to a specific time structure. This is achieved as follows: We use effect axioms that draw ideas both from Reiter's successor state axioms and the non-monotonic causal theories by Giunchiglia et al. These axioms are formulated in a recently proposed unifying action calculus to guarantee independence of a specific underlying notion of time. Reiter's default logic is then wrapped around the resulting calculus and plays a key role in solving the ramification as well as the state default problem.

In constraint or preference reasoning, a typical task is to compute a solution, or an optimal solution. However, when one has already a solution, it may be important to produce the next solution following the given one in a linearization of the solution ordering where more preferred solutions are ordered first. In this paper, we study the computational complexity of finding the next solution in some common preference-based representation formalisms. We show that this problem is hard in general CSPs, but it can be easy in tree-shaped CSPs and tree-shaped fuzzy CSPs. However, it is difficult in weighted CSPs, even if we restrict the shape of the constraint graph. We also consider CP-nets, showing that the problem is easy in acyclic CP-nets, as well as in constrained acyclic CP-nets where the (soft) constraints are tree-shaped and topologically compatible with the CP-net.

Preference logics and AI preference representation languages are both concerned with reasoning about preferences on combinatorial domains, yet so far these two streams of research have had little interaction. This paper contributes to the bridging of these areas. We start by constructing a "prototypical" preference logic, which combines features of existing preference logics, and then we show that many well-known preference languages, such as CP-nets and its extensions, are natural fragments of it. After establishing useful characterizations of dominance and consistency in our logic, we study the complexity of satisfiability in the general case as well as for meaningful fragments, and we study the expressive power as well as the relative succinctness of some of these fragments.

Handling exceptions in a knowledge-based system has been considered as an important issue in many domains of applications, such as medical domain. In this paper, we propose several preferential semantics for plausible subsumption to deal with exceptions in description logic-based knowledge bases. Our preferential semantics are defined in the framework of possibility theory, which is an uncertainty theory devoted to the handling of incomplete information. We consider the properties of these semantics and their relationships. Entailment of these plausible subsumption relative to a knowledge base is also considered. We show the close relationship between two of our semantics and the mutually dual preferential semantics given by Britz, Heidema and Meyer. Finally, we show that our semantics for plausible subsumption can be reduced to standard semantics of an expressive description logic. Thus, the problem of plausible subsumption checking under our semantics can be reduced to the problem of subsumption checking under the classical semantics.

We propose a new family of probabilistic description logics (DLs) that, in contrast to most existing approaches, are derived in a principled way from Halpern's probabilistic first-order logic. The resulting probabilistic DLs have a two-dimensional semantics similar to certain popular combinations of DLs with temporal logic and are well-suited for capturing subjective probabilities. Our main contribution is a detailed study of the complexity of reasoning in the new family of probabilistic DLs, showing that it ranges from PTime for weak variants based on the lightweight DL EL to undecidable for some expressive variants based on the DL ALC.

It seems to be a common view that in order to interpret probabilistic first-order sentences, either a statistical approach that counts (tuples of) individuals has to be used, or the knowledge base has to be grounded to make a possible worlds semantics applicable, for a subjective interpretation of probabilities. In this paper, we propose novel semantical perspectives on first-order (or relational) probabilistic conditionals that are motivated by considering them as subjective, but population-based statements. We propose two different semantics for relational probabilistic conditionals, and a set of postulates for suitable inference operators in this framework. Finally, we present two inference operators by applying the maximum entropy principle to the respective model theories. Both operators are shown to yield reasonable inferences according to the postulates.

The satisfiability problem for monadic infinite-valued Gödel logic is known to be undecidable. We identify a fragment of this logic extended with strong negation whose satisfiability is not only decidable but it is decidable within classical logic. We use this fragment to formalize the rules of CADIAG-2, a well performing fuzzy expert system assisting in the differential diagnosis in internal medicine. A (classical) satisfiability check of the resulting formulas allowed the detection of some errors in the rules of the system.

We consider a generalized form of planning, possibly involving loops, that arises in nondeterministic domains when ex- plicit strong fairness constraints are asserted over the planning domain. Such constraints allow us to specify the necessity of occurrence of selected effects of nondeterministic actions over domain’s runs. Also they are particularly meaningful from the technical point of view because they exhibit the expressiveness advantage of LTL over CTL in verification. We show that planning for reachability and maintenance goals is EXPTIME-complete in this setting, that is, it has the same complexity as conditional planning in nondeterministic domains (without strong fairness constraints). We also show that within the EXPTIME bound one can solve the more general problems of realizing agent planning programs as well as composition-based planning in the presence of strong fairness constraints.