Basic Terms and Definitions

Binary Relations

Properties of Binary Relations

A binary relation R on a set X is a subset of , i.e. is a set of ordered pairs (x,y) withWe will speak of R as a relation instead of . The collection of all binary relations on X will be denoted by Rel(X).

Some important classes of binary relations over a set X are:

• reflexive: x in X it holds that xRx.

• irreflexive: it holds that not xRx.

• symmetric: it holds that if xRy then yRx.

• antisymmetric: it holds that if xRy and yRx then x = y.

• asymmetric: it holds that if xRy then not yRx.

• transitive: it holds that if xRy and yRz then xRz.

• functional: it holds that if xRy and xRz then y=z.

Operations on binary relations

If R is a binary relation over X, then each of the following are binary relations over X:

• Converse: , defined as R^-1 = { (y, x) |}. A binary relation over a set is equal to its converse if and only if it is symmetric. Sometimes the term reverse is used as well. The converse of a surjective and injective function is called its inverse.

• Reflexive closure: R⁼, defined as R⁼ or the smallest reflexive relation over X containing R. This can seen to be equal to the intersection of all reflexive relations containing R.

• Transitive closure: R⁺, defined as the smallest transitive relation over X containing R. This can seen to be equal to the intersection of all transitive relations containing R.

• Transitive-reflexive closure: R^*, defined as R^* = (R⁺)⁼.

If R, S are binary relations over X, then each of the following are binary relations:

• Union: , defined as .

• Intersection:, defined as .

If R and S are binary relations over X, then the following is a binary relation over X as well:

• Composition: is defined as .

• Weak composition: is defined as , or informally the strongest relation which contains .

Ternary Relations

A ternary relation on a set X is accordingly a subset of X×X×X, i.e. is a set of ordered pairs <x,y,z> with x,y,z ∈ X.

Permutations

Because we have three arguments, we have 3! = 6 possible ways of arranging the arguments for a transformation. Following Zimmermann and Freksa [ZF96] the following terminology and symbols refer to these permutations of the arguments (a,b : c):

An example for these binary operations can be found in [DM04].

Composition

With ternary relations, one can think of different ways of composing them. However there are only a few ways to compose them in a way such that it can be used for enforcing local consistency [SN01]. In the case of a real relation algebra, i.e. being closed under transformation and composition, e.g. the flip-flop calculus [IM99], we can enforce 4-consistency [IC00] using the following generalized scheme of strong composition [MN03]:

Unfortunately, some calculi as for example the TPCC calculus is not closed under strong composition. For that reason we can not directly enforce 4-consistency. But we can define a weak composition operation of two relations r₁ and r₂. It is the most specific relation such that:

.

Bibliography

DM04

F. Dylla and R. Moratz. Emprical complexity issues of practical qualitative spatial reasoning about relative position. In Proceedings of the Workshop on Spatial and Temporal Reasoning, ECAI 2004, 2004.

IC00

A. Isli and A. Cohn, Qualitative spatial reasoning: A new approach to cyclic ordering of 2d orientation, Artficial Intelligence 122:137-187, 2000

IM99

A. Isli and R. Moratz, Qualitative Spatial Representation and Reasoning: Algebraic Models for Relative Position, TechReport Universität Hamburg FBI-HH-M-284/99 M-284, 1999

MN03

R. Moratz, B. Nebel, and C. Freksa, Qualitative Spatial Reasoning about Relative Position: The Tradeoff between Strong Formal Properties and Successful Reasoning about Route Graphs. Spatial Cognition 2003: 385-400, 2003

SN01

A. Scivos and B. Nebel, Double-Crossing: Decidability and Computational Complexity of a Qualitative Calculus for Navigation, Proc. COSIT-2001, Springer-Verlag, 2001

ZF96

K.Zimmermann and C. Freksa, Qualitative Spatial Reasoning Using Orientation, Distance, and Path Knowledge, Applied Intelligence, Volume 6, No.1, pp. 49-58, 1996.