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.

A plan with rich control structures like branches and loops can usually serve as a general solution that solves multiple planning instances in a domain. However, the correctness of such generalized plans is non-trivial to define and verify, especially when it comes to whether or not a plan works for all of the infinitely many instances of the problem. In this paper, we give a precise definition of a generalized plan representation called an FSA plan, with its semantics defined in the situation calculus. Based on this, we identify a class of infinite planning problems, which we call one-dimensional (1d), and prove a correctness result that 1d problems can be verified by finite means. We show that this theoretical result leads to a practical algorithm that does this verification practically, and a planner based on this verification algorithm efficiently generates provably correct plans for 1d problems.

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.

Measuring the inconsistency degree of a knowledge base can help us to deal with inconsistencies. Several inconsistency measures have been given under different multi-valued semantics, including 4-valued semantics, 3-valued semantics, LPm and Quasi Classical semantics. In this paper, we first carefully analyze the relationship between these inconsistency measures by showing that the inconsistency degrees under 4-valued semantics, 3-value semantics, LPm are the same, but different from the one based on Quasi Classical semantics. We then consider the computation of these inconsistency measures and show that computing inconsistency measurement under multi-valued semantics is usually intractable. To tackle this problem, we propose two novel algorithms that respectively encode the problems of computing inconsistency degrees under 4-valued semantics (3-valued semantics, LPm) and under Quasi Classical semantics into the partial Max-SAT problems. We implement these algorithms and do experiments on some benchmark data sets. The preliminary but encouraging experimental results show that our approach is efficient to handle large knowledge bases.

We provide two approaches for explaining inconsistency in multi-context systems, where decentralized and heterogeneous system parts interact via nonmonotonic bridge rules. Inconsistencies arise easily in such scenarios, and nonmonotonicity calls for specific methods of inconsistency analysis. Both our approaches characterize inconsistency in terms of involved bridge rules: either by pointing out rules which need to be altered for restoring consistency, or by finding combinations of rules which cause inconsistency. We show duality and modularity properties, give precise complexity characterizations, and provide algorithms for computation using HEX-programs. Our results form a basis for inconsistency management in heterogeneous knowledge integration systems.

In this paper, we introduce a new class of local consistencies, called df-consistencies, for qualitative constraint networks. Each consistency of this class is based on weak composition and a mapping f that provides a covering for each relation of the considered qualitative calculus. We study the connections existing between some properties of the introduced mappings and the relative inference strength of df-consistencies. The consistency obtained by the usual closure under weak composition corresponds to the weakest element of the class, whereas df-consistencies stronger than weak composition open new promising perspectives. Interestingly, the class of df-consistencies is shown to form a complete lattice where the partial order denotes the relative strength of every two consistencies. We also propose a generic algorithm that allows us to compute the closure of qualitative constraint networks under any "well-behaved" consistency of the class. The experimentation that we have conducted on qualitative constraint networks from the Interval Algebra shows the interest of these new local consistencies, in particular for the consistency problem.