This paper tackles the problem of evaluating the degree of inconsistency in spatial and temporal qualitative reasoning. We first introduce postulates to propose a formal framework for measuring inconsistency in this context. Then, we provide two inconsistency measures that can be useful in various AI applications. The first one is based on the number of constraints that we need to relax to get a consistent qualitative constraint network. The second inconsistency measure is based on variable restrictions to restore consistency. It is defined from the minimum number of variables that we need to ignore to recover consistency. We show that our proposed measures satisfy required postulates and other appropriate properties. Finally, we discuss the impact of our inconsistency measures on belief merging in qualitative reasoning.

In this paper, we focus on a recently introduced problem in the context of spatial and temporal qualitative reasoning, called the MAX-QCN problem. This problem involves obtaining a spatial or temporal configuration that maximizes the number of satisfied constraints in a qualitative constraint network (QCN). To efficiently solve the MAX-QCN problem, we introduce and study two families of encodings of the partial maximum satisfiability problem (PMAX-SAT). Each ofthese encodings is based on, what we call, a forbidden covering with regard to the composition table of the considered qualitative calculus. Intuitively, a forbidden covering allows us to express, in a more or less compact manner, the non-feasible configurations for three spatial or temporal entities.The experimentation that we have conducted with qualitative constraint networks from the Interval Algebra shows the interest of our approach.

RCC8 is a constraint language that serves for qualitative spatial representation and reasoning by encoding the topological relations between spatial entities. We focus on efficiently characterizing non-redundant constraints in large real world RCC8 networks and obtaining their prime networks. For a RCC8 network N a constraint is redundant, if removing that constraint from N does not change the solution set of N. A prime network of N is a network which contains no redundant constraints, but has the same solution set as N. We make use of a particular partial consistency, namely, G-path consistency, and obtain new complexity results for various cases of RCC8 networks, while we also show that given a maximal distributive subclass for RCC8 and a network N defined on that subclass, the prunning capacity of G-path consistency and path consistency is identical on the common edges of G and the complete graph of N, when G is a triangulation of the constraint graph of N. Finally, we devise an algorithm based on G-path consistency to compute the unique prime network of a RCC8 network, and show that it significantly progresses the state-of-the-art for practical reasoning with real RCC8 networks scaling up to millions of nodes.