A necessary relation algebra for mereotopology
by
Michael Winter
University of the Federal Armed Forces Munich, Germany
Coauthors: Ivo Düntsch (University of Ulster, Nothern Ireland), Gunther Schmidt (University of the Federal Armed Forces Munich, Germany)

A large part of contemporary spatial reasoning is based on the investigations of the behaviour of ``part of'' relations and their extensions to ``contact relations'' in various spatial domains. The Region Connection Calculus (RCC) was introduced as a tool for reasoning about spatial phenomena, and has since received some prominence.

It is well-known that the expressiveness of the calculus of binary relations, introduced by Tarski, is equivalent to the expressive power of the three variable fragment of first order logic. Thus, it is natural to use methods of relations algebras to study ``contact relations'' and explore their expressive power.

We show that the basic operations of the relational calculus on a ``contact relation'' generate at least 25 relations in any model of the RCC, and hence, in any standard model of mereotopology. It follows that the expressiveness of the RCC in relational logic is much greater than the original 8 RCC base relations might suggest.

Date received: December 18, 2000