Affiliations: State Key Laboratory of Intelligent Technology and
Systems, Department of Computer Science and Technology, Tsinghua University,
Beijing 100084, China. lisanjiang@tsinghua.edu.cn;
yingmsh@tsinghua.edu.cn | Department of Mathematics, Shaanxi Normal University,
Xi'an 710062, China. liyongm@snnu.edu.cn
Note: [] Address for correspondence: State Key Laboratory of Intelligent
Technology and Systems, Department of Computer Science and Technology, Tsinghua
University, Beijing 100084, China
Abstract: Region Connection Calculus (RCC) is the most widely
studied formalism of Qualitative Spatial Reasoning. It has been known for some
time that each connected regular topological space provides an RCC model. These
'standard' models are inevitable uncountable and regions there cannot be
represented finitely. This paper, however, draws researchers' attention to RCC
models that can be constructed from finite models hierarchically. Compared with
those 'standard' models, these countable models have the nice property that
regions where can be constructed in finite steps from basic ones. We first
investigate properties of three countable models introduced by Düuntsch,
Stell, Li and Ying, resp. In particular, we show that (i) the contact relation
algebra of our minimal model is not atomic complete; and (ii) these three
models are non-isomorphic. Second, for each n>0, we construct a countable RCC
model that is a sub-model of the standard model over the Euclidean unit n-cube;
and show that all these countable models are non-isomorphic. Third, we show
that every finite model can be isomorphically embedded in any RCC model. This
leads to a simple proof for the result that each consistent spatial network has
a realization in any RCC model.
