Adding reasoning abilities to context-aware systems has been a focus of research in pervasive computing for several years and a broad range of approaches has been suggested. In particular, the well-known trade-off between expressivity and inferential power has been discussed as a major concern, as dimensions of context include well-known hard domains, such as spatial, temporal, and causal knowledge. In practice however, experiments report acceptable run-times and complexity of the used reasoning mechanism does not seem to be an issue at all. Two questions are addressed in this paper: why this is the case and whether these positive results will scale up as context-aware systems are leaving their experimental environments, are extended and modified by application developers, and employed in everyday life by millions of end-users.

The paper presents an analysis of results from pervasive computing, qualitative spatial and temporal reasoning, and logic-based contextual reasoning. The goal was to carve out the theoretical core of fast contextual reasoning reported from experimental context-aware systems, and to discuss how these good properties can be made to scale up. The findings suggest that partial order reasoning is the core of tractable contextual reasoning. Examples illustrate the surprisingly high expressiveness and inferential power, and serve to emphasize the interrelations between tractable reasoning in pervasive computing, qualitative spatial and temporal reasoning, and logic-based contextual reasoning.