[Home] [Publications] [Personal]
On minimal models of the Region Connection Calculus
By Lirong Xia and Sanjiang Li.
Published in
Fundamenta Informaticae
69(4): 427-446, 2006.
Abstract
Region Connection Calculus (RCC) is one primary
formalism of qualitative spatial reasoning. Standard RCC models are
continuous ones where each region is infinitely divisible. This
contrasts sharply with the predominant use of finite, discrete
models in applications. In a recent paper, Li et al. (2004) initiate
a study of countable models that can be constructed step by step
from finite models. Of course, some basic problems are left
unsolved, for example, how many nonisomorphic countable RCC models
are there? This paper investigates these problems and obtains the
following results: (i) the exotic RCC model described by Gotts
(1996) is isomorphic to the minimal model given by Li and Ying
(2004); (ii) there are continuum many non-isomorphic minimal RCC
models, where a model is minimal if it can be isomorphically
embedded in each RCC model.
Paper
[pdf] version or
[ps] version.