We examine a variety of representations for storing and reasoning about spatial information and distinguish between quantitative representations grounded in numerical coordinate systems and qualitative representations, based on a high-level conceptual vocabulary for the description of spatial situations. We suggest that qualitative languages, can add powerful functionality to spatial information systems, which have traditionally processed only quantitative data. Trade-offs between expressive power, computational tractability and 'naturalness' are considered for several qualitative formalisms. We explain how a significant class of topological relations can be described by a 1st-order language and how these can be encoded into 0-order intuitionistic logic to yield an effective reasoning algorithm. We discuss ways of combining qualitative and quantitative information within a coherent architecture and describe an implementation of a hybrid spatial information system, incorporating three types of spatial information: quantitative data-structures are employed in a database of polygonal regions; a qualitative relational language is used to express high-level queries; and intuitionistic propositional logic is used to compute the inferences needed to answer these queries.

The aim of the paper is to describe a temporal constraint based solver for (job shop) scheduling problems. The heart of the solver is a "well behaved" restriction of the framework of TCSPs defined by R. Dechter, I. Meiri and J. Pearl (1991): the restriction is an algebra and expresses convex constraints or unions of two such constraints. We give a general description of the solver and show its completeness.