We study the problem of probabilistic deduction with conditional constraints over basic events. We show that globally complete probabilistic deduction with conditional constraints over basic events is NP-hard. We then concentrate on the special case of probabilistic deduction in conditional constraint trees. We elaborate very efficient techniques for globally complete probabilistic deduction. In detail, for conditional constraint trees with point probabilities, we present a local approach to globally complete probabilistic deduction, which runs in linear time in the size of the conditional constraint trees. For conditional constraint trees with interval probabilities, we show that globally complete probabilistic deduction can be done in a global approach by solving nonlinear programs. We show how these nonlinear programs can be transformed into equivalent linear programs, which are solvable in polynomial time in the size of the conditional constraint trees.

Buchheit, M., Donini, F. M., Schaerf, A.

Terminological knowledge representation systems (TKRSs) are tools for designing and using knowledge bases that make use of terminological languages (or concept languages). We analyze from a theoretical point of view a TKRS whose capabilities go beyond the ones of presently available TKRSs. The new features studied, often required in practical applications, can be summarized in three main points. First, we consider a highly expressive terminological language, called ALCNR, including general complements of concepts, number restrictions and role conjunction. Second, we allow to express inclusion statements between general concepts, and terminological cycles as a particular case. Third, we prove the decidability of a number of desirable TKRS-deduction services (like satisfiability, subsumption and instance checking) through a sound, complete and terminating calculus for reasoning in ALCNR-knowledge bases. Our calculus extends the general technique of constraint systems. As a byproduct of the proof, we get also the result that inclusion statements in ALCNR can be simulated by terminological cycles, if descriptive semantics is adopted.

Calvanese, D., Lenzerini, M., Nardi, D.

The notion of class is ubiquitous in computer science and is central in many formalisms for the representation of structured knowledge used both in knowledge representation and in databases. In this paper we study the basic issues underlying such representation formalisms and single out both their common characteristics and their distinguishing features. Such investigation leads us to propose a unifying framework in which we are able to capture the fundamental aspects of several representation languages used in different contexts. The proposed formalism is expressed in the style of description logics, which have been introduced in knowledge representation as a means to provide a semantically well-founded basis for the structural aspects of knowledge representation systems. The description logic considered in this paper is a subset of first order logic with nice computational characteristics. It is quite expressive and features a novel combination of constructs that has not been studied before. The distinguishing constructs are number restrictions, which generalize existence and functional dependencies, inverse roles, which allow one to refer to the inverse of a relationship, and possibly cyclic assertions, which are necessary for capturing real world domains. We are able to show that it is precisely such combination of constructs that makes our logic powerful enough to model the essential set of features for defining class structures that are common to frame systems, object-oriented database languages, and semantic data models. As a consequence of the established correspondences, several significant extensions of each of the above formalisms become available. The high expressiveness of the logic we propose and the need for capturing the reasoning in different contexts forces us to distinguish between unrestricted and finite model reasoning. A notable feature of our proposal is that reasoning in both cases is decidable. We argue that, by virtue of the high expressive power and of the associated reasoning capabilities on both unrestricted and finite models, our logic provides a common core for class-based representation formalisms.

Journal of Articial In telligence Researc h 11 (1999) 361-390 Submitted 6/99; published 11/99 The Complexit y of Reasoning ab out Spatial Congruence Matteo Cristani crist ani@sci.univr.it Dip artimento Scientic oeT e cnolo gic o, Universit ad i V er ona, C a Vignal 2, str ada L eG r azie, I-37134 V er ona Abstract In the recen t literature of Articial In telligence, an in tensiv e researc h eort has b een sp en t, for v arious algebras of qualitativ e relations used in the represen tation of temp oral and spatial kno wledge, on the problem of classifying the computational complexit y of reasoning problems for subsets of algebras. The main purp ose of these researc hes is to describ e a restricted set of maximal tractable subalgebras, ideally in an exhaustiv e fashion with resp ect to the hosting algebras. In this pap er w ei n tro duce a no v el algebra for reasoning ab out Spatial Congruence, sho w that the satisabilit y problem in the spatial algebra MC-4 is NPcomplete, and presen ta complete classication of tractabilit y in the algebra, based on the individuation of three maximal tractable sub classes, one con taining the basic relations. The three algebras are formed b y 14, 10 and 9 relations out of 16 whic h form the full algebra. The main reason for this, as already observ ed b y Jonsson and Drak engren (1997), is probably that spatial reasoning has pro v ed to b e applicable to real-w orld problems, as in Geographical Information Systems (Egenhofer, 1991; Grigni, P apadias, & P apadimitriou, 1995), and Molecular Biology (Cui, 1994). The sp ecic stress on qualitative reasoning ab out space, as observ ed b y Zimmermann (1995), is justied b y the fact that qualitativ e spatial relations can b e treated as e cien tly as their quan titativ e coun terparts, but they seem to be closer to the mo del of relations h umans adopt for spatial reasoning. Ev en though qualitativ e spatial reasoning has an extended literature, in spite of its relativ ely short history, certain asp ects of the discipline ha v e b een neglected. The term morphological reasoning is in tended to suggest reasoning ab out the internal structur e of the ob jects. In the case of spatial reasoning this includes reasoning ab out the size, shap e and in ternal top ology of spatial regions. The purp ose of the presen tw ork is to analyse the complexit y of reasoning ab out relations of congruence, either actual or partial, be t w een spatial regions, using the spatial algebra MC-4 whic h has b een preliminarly analysed b y Cristani (1997). The algebra MC-4 is a Constrain t Algebra (Ladkin & Maddux, 1994) for qualitativ e reasoning ab out the morphological relation of congruence. Tw o spatial regions, in the mo dels do cumen ted in literature, are considered to be equiv alen t if and only if they share in terior and b oundaries, namely if and only if they are the same spatial region.

We investigate the problem of reasoning in the propositional fragment of MBNF, the logic of minimal belief and negation as failure introduced by Lifschitz, which can be considered as a unifying framework for several nonmonotonic formalisms, including default logic, autoepistemic logic, circumscription, epistemic queries, and logic programming. We characterize the complexity and provide algorithms for reasoning in propositional MBNF. In particular, we show that entailment in propositional MBNF lies at the third level of the polynomial hierarchy, hence it is harder than reasoning in all the above mentioned propositional formalisms for nonmonotonic reasoning. We also prove the exact correspondence between negation as failure in MBNF and negative introspection in Moore's autoepistemic logic.