arXiv:1606.09140v3 [cs.AI] 19 Jun 2017

ALGEBRAIC FOUNDATIONS FOR QUALITATIVE CALCULI
AND NETWORKS
ROBIN HIRSCH, MARCEL JACKSON, AND TOMASZ KOWALSKI

Abstract. Binary Constraint Problems have traditionally been considered
as Network Satisfaction Problems over some relation algebra. A constraint
network is satisfiable if its nodes can be mapped into some representation
of the relation algebra in such a way that the constraints are preserved. A
qualitative representation φ is like an ordinary representation, but instead of
requiring that (a;b)φ is the composition aφ ◦bφ of the relations aφ and bφ , as we
do for ordinary representations, we only require that cφ ⊇ aφ ◦bφ ⇐⇒ c ≥ a;b,
for each c in the algebra. A constraint network is qualitatively satisfiable if its
nodes can be mapped to elements of a qualitative representation, preserving the
constraints. If a constraint network is satisfiable then it is clearly qualitatively
satisfiable, but the converse can fail, as we show. However, for a wide range
of relation algebras including the point algebra, the Allen Interval Algebra,
RCC8 and many others, a network is satisfiable if and only if it is qualitatively
satisfiable.
Unlike ordinary composition, the weak composition arising from qualitative representations need not be associative, so we can generalise by considering network satisfaction problems over non-associative algebras. We prove
that computationally, qualitative representations have many advantages over
ordinary representations: whereas many finite relation algebras have only infinite representations, every finite qualitatively representable algebra has a
finite qualitative representation; the representability problem for (the atom
structures of) finite non-associative algebras is NP-complete; the network
satisfaction problem over a finite qualitatively representable algebra is always
in NP; the validity of equations over qualitative representations is co-NPcomplete. On the other hand we prove that there is no finite axiomatisation
of the class of qualitatively representable algebras.

1. Introduction
Computer scientists have been solving systems of binary constraints for a long
time. Temporal reasoning, for example, is often dealt with by solving a set of
temporal constraints between events, represented in a network : a ﬁnite complete
graph whose edges are labelled by a choice of alternative temporal relations. The
network is satisfiable if it is possible to map the nodes to temporal events in such
a way that each pair of nodes is mapped to a pair of events satisfying one of the
alternative temporal relations labelling that edge. An algebra of these relations,
in one of the simplest cases, is the point algebra, where the primitive alternative
relations are =, <, > and the events are points on a linear ﬂow of time. Relational
compositions of these basic relations are recorded in the table in the upper left
corner of Figure 1, where ◦ denotes composition of binary relations.
The second author was supported by ARC Future Fellowship FT120100666 and Discovery
Project DP1094578. The third author was supported by ARC Future Fellowship FT100100952.
1

2

ROBIN HIRSCH, MARCEL JACKSON, AND TOMASZ KOWALSKI

◦
=
<
>

=
=
<
>

b

< >
< >
< 1
1 >

<
a
<

a

<, >

b

d

<

<

d

c

<, >
<
<, =
c

<

Q

Figure 1. The point algebra: composition table, a constraint network, a solution, a strong representation. Here 1 denotes {=, <, >}
(all three relations are permitted).
Consider the network over the point algebra given in Figure 1. It is satisﬁable in
a linear order of just four distinct points, but a representation of the point algebra
has to be inﬁnite, because < ◦ < is identical to <, which entails not just transitivity
(<◦< is contained in <) but also density (< is contained in <◦<). This discrepancy
between an inﬁnitely representable algebra and ﬁnitely satisfiable networks over it,
is not too serious in this case because every ﬁnite linear order embeds into the
rational numbers. Hence, if a network has a solution in some linear order then it
can be embedded into a representation of the point algebra.
To deal with temporal intervals rather than point-events, the Allen Interval
Algebra [All83] is very commonly used. Here, we have thirteen alternative primitive
relations between intervals on a linear ﬂow of time. For the Allen Interval Algebra,
a solution to a constraint network would be a ﬁnite set of intervals in a linear order
with an appropriate relation holding between each pair, but a representation of this
algebra is again inﬁnite: it consists of ordered pairs taken from a dense linear order
without endpoints [LM94]. And again, there is no real discrepancy here because
every ﬁnite arrangement of intervals in a linear order embeds into a set of intervals
of rational numbers.
But when one tries to generalise the above examples to apply relational reasoning
in other domains, the discrepancy becomes a real issue. A very clear example of this
occurs in spatial reasoning, where an analogue of the Allen Interval Algebra with
relations between spatial regions is used. This algebra is called RCC8. One of the
basic relations considered in RCC8 is external connectedness (EC), whose intended
interpretation is that xECy if regions x and y touch at the borders but only at
the borders, for example as in the left-hand side of Figure 2. Now, RCC8 requires
that EC ◦ EC ⊇ EC, which is reasonable if we think of regions topologically as
open balls (open disks in R2 ; more generally, open sets with boundaries of genus
0), because then for any xECy we can ﬁnd a z with xECzECy, as in the lefthand side of Figure 2. However, in real-life applications, this assumption is not

ALGEBRAIC FOUNDATIONS FOR QUALITATIVE CALCULI AND NETWORKS

3

y
z
x
x

y

Figure 2. Some relations between spatial regions

always warranted. For it happens that one region can be completely surrounded by
another. This is the spatial relation San Marino bears to Italy, the Vatican City to
Rome, and Lesotho to South Africa. When this happens, as in the right-hand side
of Figure 2, where region y is the annulus surrounding region x, we have xECy,
but (x, y) ∈
/ EC ◦ EC.
The problem was identiﬁed, and rightly diagnosed to be an anomaly. The remedy was to consider an algebra of binary relations where relational composition is
replaced by another binary operation, called weak composition, approximating real
composition from above (see, for example [LR04]). Weak composition is deﬁned in
such a way that when (x, y) is in the weak composition of EC with EC it is not
mandatory that there is a z with xECzECy, it is merely permitted that such a z
should exist. (Note, below we distinguish two diﬀerent meanings of weak composition from the literature: either it is merely permitted that such a z should exist, or
it is permitted and additionally there must be x′ , y ′ , z ′ such that x′ ECz ′ ECy ′ i.e.
the composition has to be realised at least once. The two corresponding types of
representations we consider are feeble and qualitative respectively, see below.) Since
then, an impressive body of research has been conducted in qualitative reasoning
based on these notions of weak composition (see [CCL+ 15] for a survey).
One restriction to this framework of qualitative reasoning is that the identity
relation is assumed to be an indivisible primitive relation (an atom of the algebra),
so that unary properties of states cannot be expressed directly. So, for example,
suppose we want to assert that a certain time interval occurs during an interval
where the printer is working. In the Allen Interval Algebra we can express that one
interval i occurs during another interval j but we cannot assert properties of the
interval j. In our framework we may introduce a subidentity atom w with intended
semantics jwj if and only if the printer is working on the interval j. A similar
extension was required for Kleene Algebra, where it was necessary to introduce the
test operator in order to express properties of states, rather than relations [Koz97].
Here, we make no assumption that the identity is atomic.
A further restriction is that the deﬁnition of weak composition only applies in
the setting of ﬁnitely many primitive relations. However, there are applications in
Artiﬁcial Intelligence where inﬁnitely many diﬀerent relations are needed. A number of diﬀerent researchers who wished to add quantitative reasoning to qualitative
constraint systems, adopted languages containing inﬁnitely many constraints (e.g.

4

ROBIN HIRSCH, MARCEL JACKSON, AND TOMASZ KOWALSKI

[KL91, Mei96, Hir96] or see [OW08] for a survey of metric temporal logic, also see
Example 6.7 below).
In this article we deﬁne the weak composition of two binary relations in general;
our deﬁnition coincides with the original one where it applies, but covers a wider
range of algebras of binary relations. We also deﬁne a corresponding notion of qualitative representation. In a classical representation of a relation algebra (referred
to henceforth as a strong representation), given two points x, y for which it is consistent for there to be a z with (x, z) ∈ a, (z, y) ∈ b it is then mandatory that such
a point z exists. This requirement is relaxed in a qualitative representation, see
Deﬁnition 2 below. A constraint network is qualitatively satisﬁable if it embeds into
a qualitative representation. We will see that this corresponds much more closely
to the intuitive approach to binary constraint problems, such as those illustrated
in Figure 1. There, the four element chain is in fact a qualitative representation of
the point algebra.
1.1. Fixed vs. arbitrary representations. When considering the constraint
satisfaction problem in its general setting one typically has a ﬁxed domain for each
variable and the interpretation of any relation symbols used in the constraints is
also ﬁxed.
In keeping with that, a great deal of the research into qualitative
reasoning focusses on a ﬁxed set of relations on a ﬁxed base set and considers the
satisﬁability of constraints in that setting, in other words the issue is the satisﬁability of constraints in a single, ﬁxed representation. To illustrate the value of
this approach, suppose we wish to schedule a series of meetings in a discrete ﬂow
of time where there are exactly four time points, as in Figure 1. A set of binary
constraints on the scheduling of events could be represented as a network over the
point algebra, but the question to consider is not whether the network is satisﬁable
in some qualitative representation, it is whether the network can be satisﬁed in
the qualitative representation of the point algebra consisting of a linear order of
four points. For this kind of problem it is the satisﬁability of a network in a ﬁxed
representation that should be considered. (The complexity of this problem can
be fairly high, for example in [Lee14] a single model based on dipoles in the real
plane, (i.e. elements of R4 ) is adopted and it is shown that the network satisfaction
problem is ∃R-complete for various algebras of relative directional constraints over
this model. For a more extreme case, consider a graph algebra with three primitive
constraints: equals, adjacent and non-adjacent. Let S be an undecidable set of
ﬁnite connected graphs and let G be the disjoint union of all graphs in S. Given
any ﬁnite connected graph F we can deﬁne a network on the same set of nodes,
edges are labelled ‘adjacent’ and irreﬂexive non-edges are labelled ‘non-adjacent’.
Since this network is qualitatively satisﬁable in G if and only if F ∈ S, the problem
of determining whether a network is satisﬁable in G is undecidable.)
However, there are applications where the representation is not ﬁxed, for example
in spatial reasoning using RCC8 the exact topography of the relations between
regions may not be known. Many of the theorems proved in the previously cited
papers establish properties that hold over a whole class of representations, e.g.
results in [Ren02] refer to the solvability of RCC8 constraints over non-empty,
regular, closed regions, regardless of the particular topology under consideration.
The main decision problem considered in the current paper is to decide if a given
network is satisﬁable in an arbitrary qualitative representation.

ALGEBRAIC FOUNDATIONS FOR QUALITATIVE CALCULI AND NETWORKS

5

Results obtained in this paper indicate that qualitative representations have
computational advantages over strong representations. All the algebras of relations
mentioned above have strong representations, but only on inﬁnite base sets. In
contrast, we show that if a ﬁnite algebra of relations (formally, a non-associative
algebra) has a qualitative representation then it has one on a ﬁnite base set. A
consequence is that the problem of determining whether a ﬁnite non-associative
algebra is qualitatively representable is in NP (indeed it is NP-complete) whereas
the strong representation problem is known to be undecidable [HH01b].
Furthermore, although it happens to be the case that a consistent, atomic network of constraints (a consistent network with only a single primitive relation on
each edge) is always satisﬁable for the algebras of relations previously mentioned,
and hence a polynomial time, non-deterministic algorithm can solve the network
satisfaction problem for these algebras by guessing a primitive label for each edge
and then checking their consistency, this does not work for other algebras of spatial
relations. For example, consider the interval and duration algebra INDU whose
twenty-ﬁve primitive relations are similar to Allen’s thirteen primitive interval relations, but also determine whether the duration of the ﬁrst interval is smaller,
equal or greater in duration than the second interval [PKS99]. There are known,
consistent, atomic INDU-networks which cannot be satisﬁed by intervals [Lig11,
Figure 8.11]. Thus consistency of a network does not suﬃce to prove that the
network is satisﬁable, even if the network is atomic. Although the network satisfaction problem remains in NP for INDU-networks, there are known relation algebras
where the problem has much worse complexity [Hir99]. On the other hand, for
any ﬁnite algebra of relations the network satisfaction problem over qualitative
representations always belongs to NP.
Similarly, although the validity of equations valid over strong representations was
shown to be undecidable by Tarski, the validity of equations valid over all qualitative
representations is decidable (indeed it is co-NP-complete). Our conclusion is
that qualitative representations are not only more appropriate to express the kind
of contraints that arise from many applications, but they are more amenable to
algorithmic reasoning.

1.2. Historical remarks. The structures we called algebras above, were conceived
as calculi: formal rules for manipulating relations, invented and developed ad hoc,
to suit the purpose at hand. This is evident in the naming: for example, RCC8
is so called because it was originally developed in [RCC92] as Region Connection
Calculus, with 8 basic relations, hence the acronym RCC8 (although the names
of the three authors might also have something to do with it). Later, mathematicians observed that such calculi, including the point algebra, Allen Interval
Algebra and RCC8, were examples of Tarski’s Relation Algebras. As far as we
know, this observation was ﬁrst made in [LM88, LM94]. In this setting, the basic relations are boolean atoms in a relation algebra, the edges of a network are
labelled by arbitrary elements of the relation algebra and the network is satisﬁable if its nodes can be mapped into some representation of the relation algebra
in such a way that the label of an edge of the network holds at the corresponding two points in the representation. However, as we outlined above, there were

6

ROBIN HIRSCH, MARCEL JACKSON, AND TOMASZ KOWALSKI

diﬃculties in restricting to strong representations, particularly for relation algebras such as RCC8, and this led to the weaker notion of qualitative representation, now very widely studied in knowledge representation and its applications, see
[DWM01, LR04, LW06, MSW06, CCL+ 15, RL05], for example.
1.3. Notation. We deal with abstract algebras and concrete representations as
binary relations and separate the notation, to some extent. Working abstractly
we use +, − as the basic boolean operators and introduce standard abbreviations,
such as x · y = −(−x + −y) and x ≤ y ↔ x + y = y. The identity constant is 1′ ,
the converse operator is ˘ and any algebraic multiplication-like operator (including
weak composition, below) will be denoted by ;. Working with concrete binary
relations we write ∪, \ for the operators corresponding to +, − and we write IdD =
{(x, x) : x ∈ D} for the identity relation over a domain D, corresponding to the
abstract 1′ , though we may drop the subscript D if it is clear from the context.
The converse of a binary relation r will be written as r˘ = {(y, x) : (x, y) ∈ r}. We
write r ◦ s = {(x, y) ∈ D × D : ∃z ∈ D (x, z) ∈ r ∧ (z, y) ∈ s} for the composition of
two binary relations r, s. Our convention is that converse has highest precedence,
followed by composition which takes precedence over other operators, for example
a · b ; c˘ denotes a · (b ; (c˘)). For any set S we write ℘(S) for the power set of S.
2. Background
A qualitative calculus has traditionally been deﬁned (see, for example, [LR04])
by specifying a ﬁnite partition Π = (R0 , . . . , Rn ) of the set D × D, for some ﬁxed
(usually inﬁnite) domain D, with the following properties:
(1) The identity relation IdD is an element of the partition,
(2) Π is closed under relational converses, that is, R˘ ∈ Π for every R ∈ Π.
The set {R0 , . . . , Rn } generates a boolean subalgebra B of P(D × D) under the
usual set-theoretical operations. Clearly, R0 , . . . , Rn are atoms of B; these include
the identity relation. Moreover, B is closed under relational converses. However, B
is not in general closed under relational composition, as the example of Figure 2
indicates. This is remedied by considering weak composition instead: an operation
deﬁned by
[
S ; T = {R ∈ Π : R ∩ (S ◦ T ) 6= ∅}
where S ◦ T stands for the true composition of S and T . So deﬁned, S ; T is the
smallest element of B containing S ◦ T .
Thus, a qualitative calculus carries a natural algebraic structure of the type of
a relation algebra. Viewed from an abstract algebraic perspective, a qualitative
calculus is a hybrid object: an abstract algebra together with a concrete interpretation, or a representation. As in [WHW14], one of our aims in this article is to
separate the two sides of a qualitative calculus, into syntax (algebra) and semantics (representation), and so investigate the foundations of qualitative calculi in a
manner similar to model theoretical analysis of classical mathematics.
Before we state the basic deﬁnitions, let us recall the two generalisations that
we adopt from the outset. Firstly, we will lift the ﬁniteness assumption. It is not
necessary for a deﬁnition of weak composition, and from a universal algebraic point
of view admitting inﬁnite algebras is more natural, furthermore, as we have seen,
there are applications where it is desirable to include inﬁnite relation algebras, for
example when we wish to express metric constraints. Secondly, we do not require

ALGEBRAIC FOUNDATIONS FOR QUALITATIVE CALCULI AND NETWORKS

7

that the identity is an atom, as subidentity relations provide a natural way of
modelling properties, that is, subsets of the domain, by representing a set Z ⊆ D
by the relation {(z, z) : z ∈ Z}.
DEFINITION 1. Let D be a set and let S be a set of binary relations over D,
that is, S ⊆ P(D × D). S is a herd if
(1) S forms a boolean set algebra with top element D × D, so S is closed under
finite intersections and complement relative to D × D,
(2) IdD ∈ S,
(3) If A ∈ S then the converse relation A˘ is in S.
In a herd S given any two elements A, B ∈ S if there is a minimal C ∈ S
containing A ◦ B then we say that the weak composition of A and B is C. If S is
ﬁnite, then such a minimal element is sure to exist, since S is closed under ﬁnite
intersections.
For herds with inﬁnitely many relations, the weak composition of two elements
is not always deﬁned (a minimal element containing A ◦ B may not exist), however
the case we are interested in is the case where the weak composition of A and
B is deﬁned, and for the abstract algebraic structure corresponding to herds we
include a binary composition operator ;, so the signature is the same as that of
a relation algebra: it is a boolean algebra with an extra nullary operation 1′ for
identity, a unary operation ˘ for converse, and a binary operation ; to denote weak
composition and it obeys all the axioms deﬁning a relation algebra except perhaps
associativity (see below). Maddux calls such an algebra a non-associative relation
algebra [Mad82, Deﬁnition 1.2], or non-associative algebra for short. [LR04] already
observed that their qualitative calculi are non-associative algebras and it is easily
veriﬁed that the herds considered here are non-associative algebras too, in the cases
where weak composition is deﬁned.
An algebra A = (A, 0, 1, +, −, 1′,˘, ;) of the type of relation algebras belongs to
the variety NA of non-associative algebras, if
(1) (A, 0, 1, +, −) is a boolean algebra,
(2) (A, 1′ ,˘, ;) is an involuted monoid, i.e. it satisﬁes
(a) 1′ ; x = x = x ; 1′
(b) x˘˘ = x
(c) (x ; y)˘ = y˘ ; x˘
(3) ˘ and ; are normal additive operators, that is
(a) 0˘ = x ; 0 = 0,
(b) (x + y)˘ = x˘ + y˘, x ; (y + z) = (x ; y) + (x ; z)
(4) x ; y · z˘ = 0 if and only if y ; z · x˘ = 0 (Peircean law)
By additivity, the operators are monotone, e.g. y ≤ z → x; y ≤ x; z, etc. Since
the operators ˘, ; are conjugated it turns out that every non-associative algebra is
completely additive, i.e. if S is a subset of the elements of A with a supremum ΣS
then (ΣS)˘ is the supremum of {s˘ : s ∈ S} and for any a ∈ A the element a; ΣS is
the supremum of {a; s : s ∈ S} [JT51, Theorem 1.14].
In the following we deﬁne a qualitative representation as an isomorphism from
an non-associative algebra to a herd. In [LR04, Deﬁnition 3] the corresponding
deﬁnition is only required to be a homomorphism, injectivity is not required. One
diﬃculty with this weaker notion of representation is that trivial map from an

8

ROBIN HIRSCH, MARCEL JACKSON, AND TOMASZ KOWALSKI

arbitrary non-associative algebra to the herd on an empty domain is a non-injective
homomorphism, and we wish to exclude this trivial case.
DEFINITION 2. Let A = (A, 0, 1, +, −, 1′,˘, ;) be a non-associative algebra. A
qualitative representation φ of an algebra A is an injection to a herd S of binary
relations over base D, such that
(1) 0φ = ∅, 1φ = D × D, (1′ )φ = IdD ,
(2) (a + b)φ = aφ ∪ bφ , (−a)φ = (D × D) \ aφ ,
(3) (a˘)φ = (aφ )˘,
(4) cφ ⊇ aφ ◦ bφ ↔ c ≥ a ; b
for all a, b, c ∈ A. If A has a qualitative representation, then we say that A is
a qualitatively representable algebra. The class of all qualitatively representable
algebras we will denote by QRA.
If (a ; b)φ = aφ ◦ bφ for all a, b ∈ A then the qualitative representation φ is
a strong representation. RRA is the variety generated by the class of all strongly
representable relation algebras.
If φ is a qualitative representation of a non-associative algebra A, observe that
a; b is always deﬁned (for a, b, ∈ A) and Deﬁnition 2.4 requires that it is the minimal
solution of c ∈ A, cφ ⊇ aφ ◦ bφ .
The class of strongly representable relation algebras is already known to be
extremely complicated: without ﬁnite axiomatisation in ﬁrst order logic, with
undecidable equational theory and with undecidable membership problem for ﬁnite algebras [HH01b]. The class QRA is known to be a proper subclass of NA
[LR04, WHW14], or see Example 6.4 below. We show below that the class QRA
has intermediate diﬃculty: it is also without a ﬁnite axiomatisation (Theorem 19)
but it is NP-complete to decide membership for ﬁnite algebras (Theorem 14).
The deﬁnition of qualitative representation (Deﬁnition 2) is based on the definition of weak composition for partition schemes given in [LR04, §2.3], however
our deﬁnition applies not just to ﬁnite partition schemes, it works even for inﬁnite herds. Moreover, Ligozat and Renz appear to include two distinct notions
of weak composition. In [RL05, abstract] they require that weak composition is
“the strongest relation containing the real composition”, in agreement with much
of the relevant literature and in agreement with Deﬁnition 2 above. However, in
[LR04, Deﬁnition 3] and in [Lig05, Deﬁnition 2] only the right to left implication
of Deﬁnition 2.4 is required, that is, they only require (a ; b)φ ⊇ aφ ◦ bφ and do not
insist that c = a; b is the minimal solution of cφ ⊇ aφ ◦ bφ as c ranges over elements
of the algebra. We call this looser deﬁnition of a qualitative representation a feeble
representation and investigate it separately in Section 6. Example 6.1 and 6.4 below show that there is a real discrepancy between qualitative representations and
feeble representations. ([WHW14, Proposition 2] dispute a quite separate point in
[RL05], concerning the notion of “closure under constraints”.)
LEMMA 3. Let φ : A → ℘(D × D) respect the boolean operators, the identity
and the converse operator, i.e. 1φ = D × D, (−a)φ = (D × D) \ aφ , (a + b)φ =
aφ ∪bφ , (1′ )φ = IdD and (a˘)φ = {(y, x) : (x, y) ∈ aφ }. The following are equivalent
(1) φ is a qualitative representation
(2) for all a, b, c ∈ A
(a; b · c 6= 0) ↔ ∃x, y, z ∈ D((x, y) ∈ aφ ∧ (y, z) ∈ bφ ∧ (x, z) ∈ cφ ).

ALGEBRAIC FOUNDATIONS FOR QUALITATIVE CALCULI AND NETWORKS

9

Proof. For (1) ⇒ (2), suppose φ is a qualitative representation. If there are x, y, z ∈
D such that (x, y) ∈ aφ , (y, z) ∈ bφ , (x, z) ∈ cφ then (a; b · c)φ = (a; b)φ ∩ cφ ⊇
aφ ◦ bφ ∩ cφ 6= ∅, so a; b · c 6= 0. If no such x, y, z exist then aφ ◦ bφ ⊆ (−c)φ and
since (a; b)φ is smallest such that (a; b)φ ⊇ aφ ◦ bφ it follows that (a; b)φ ⊆ (−c)φ ,
(a; b)φ ∩ cφ = ∅, so a; b · c = 0.
Conversely assume (2). If (a; b)φ 6⊇ aφ ◦ bφ then there are x, y, z with (x, y) ∈
aφ , (y, z) ∈ bφ and (x, z) ∈ (−(a; b))φ , hence by (2) a; b · (−(a; b)) 6= 0, a contradiction. We conclude (a; b)φ ⊇ aφ ◦ bφ . If cφ ⊇ aφ ◦ bφ then there do not exist x, y, z
such that (x, y) ∈ aφ , (y, z) ∈ bφ and (x, z) ∈ (−c)φ so by (2), a; b · (−c) = 0 and
c ≥ a; b, thus c = a; b is the minimal solution in A of cφ ⊇ aφ ◦ bφ , this proves that
; is correctly represented as weak composition.

3. Atom Structures and Examples
In the case of an atomic algebra, a convenient way of specifying the operators is
by deﬁning its atom structure.
DEFINITION 4. Let X be the set of atoms (minimal, non-zero elements) of a
non-associative algebra A. The atom structure At(A) is defined as
At(A) = (X, E,˘, C)
where E is the set of atoms below the identity, ˘ is the converse function restricted
to atoms, and C is the set of consistent triples of atoms, that is, those triples of
atoms (a, b, c) such that a ; b ≥ c.
Conversely, given (X, E,˘, C), where E ⊆ X, ˘ is a unary function on X and C ⊆
X 3 we may define the complex algebra Cm(X, E,˘, C) = (P(X), ∅, X, ∪, \, E,˘, ;)
where P(X) is the power set of X, E is the identity element, ˘ is extended to sets
of atoms by taking unions, and multiplication is defined by S ; T = {x ∈ X : ∃s ∈
S, t ∈ T (s, t, x) ∈ X}.
For any atomic non-associative algebra A with atoms X, the map deﬁned by
a 7→ {x ∈ X : x ≤ a} is an embedding of A into Cm(At(A)) and in the case where
A is complete and atomic, this map is surjective, i.e. an isomorphism. Observe,
for ﬁnite algebras, that the number of atoms is the logarithm (base two) of the
number of elements of the algebra. It is clear, by additivity, that the constant
1′ and the operators ˘, ; are determined by the atom structure, when the atom
structure is ﬁnite and in fact, as we noted earlier, every non-associative algebra is
completely additive so the operators of an arbitrary atomic, non-associative algebra
are determined by its atom structure.
The next lemma is proved in [Mad82, Theorem 2.2(2)].
LEMMA 5. Let (S, E,˘, C) consist of a set S, a subset E ⊆ S, a unary function
˘: S → S satisfying s˘˘ = s, and subset C ⊆ S × S × S. The following are equivalent
• (S, E,˘, C) is the atom structure of some non-associative algebra,
• For all a, b, c ∈ S we have a = b iff there is e ∈ E such that (e, a, b) ∈ C,
and if (a, b, c) ∈ C then (b˘, a˘, c˘) ∈ C and (c˘, a, b˘) ∈ C.
The six triples (a, b, c), (b, c˘, a˘), (c, b˘, a), (a˘, c, b), (b˘, a˘, c˘), (c˘, a, b˘) are called
the Peircean transforms of (a, b, c). In practice, the triples are given in composition
tables such as the one used in Figure 1 to deﬁne the point algebra. The entry for

10

ROBIN HIRSCH, MARCEL JACKSON, AND TOMASZ KOWALSKI

a ; b is the join of the set {c : (a, b, c) ∈ C}, so if (a, b, c1 ), (a, b, c2 ), (a, b, c3 ) ∈ C, the
entry for a ; b will be c1 + c2 + c3 .
In the following examples we deﬁne some ﬁnite non-associative algebras by giving
their atom structures, except for the ﬁnal example which is deﬁned directly.
EXAMPLES 6.
(1) The first of our non-associative algebras has three atoms,
{e, e′ , a}, hence eight elements. The identity is e + e′ , each element is selfconverse, multiplication is defined in the table on the left below

;
e
e′
a

e
e
0
a

e′
0
e′
a

a

a
a
a
1

e

e′

1
a

0
a

2

e′

Multiplication is not associative, for example (e ; e′ ) ; a = 0 ; a = 0 but e ; (e′ ;
a) = e ; a = a. This non-associative algebra has a qualitative representation
φ over a base of three points {0, 1, 2}, shown on the right, above: eφ =
Id{0} , (e′ )φ = Id{1,2} and aφ = {(x, y) : x 6= y < 3}, φ is defined on sums
of atoms by additivity.
Now let θ be obtained by restricting the qualitative representation φ to
the base {0, 1}, illustrated below.
a
e

0

1

e′

a
Since (b; c)θ ⊇ bθ ◦ cθ for any b, c in the algebra and all atoms are witnessed,
θ is a feeble representation over the base {0, 1}. However, aθ ◦ aθ = Id{0,1}
and a; a = 1 is not minimal subject to containing aθ ◦ aθ (the minimal
solution is e + e′ < 1), so θ is not a qualitative representation.
(2) This non-associative algebra has atoms {1′ , a, a′ , ×} (so sixteen elements).
All elements are self-converse, this time the identity 1′ is an atom, multiplication is defined by
;
1′
a
a′
×

1′
1′
a
a′
×

a
a
1′ + a
0
×

a′
a′
0
1 ′ + a′
×

×
×
×
×
1 ′ + a + a′

Again, associativity fails because (a;a′ );a′ = 0;a′ = 0 but a;(a′ ;a′ ) = a;(1′ +
a′ ) = a. A qualitative representation θ on base {0, 1, 2} ∪ {0′ , 1′ , 2′ }, shown
below, is defined by (1′ )θ = Id{x,x′ :x<3} , aθ = {(m, n) : m 6= n, m, n < 3},
(a′ )θ = {(m′ , n′ ) : m 6= n, m, n < 3}, ×θ = {(m, n′ ), (m′ , n) : m, n < 3}.

ALGEBRAIC FOUNDATIONS FOR QUALITATIVE CALCULI AND NETWORKS

11

Here and below, reflexive identity loops have been omitted.
×
2
a

a
a

0

2′

×
a′
1

a′

0′

×

a′
1′

×
(3) The next algebra has atoms {1′ , a, b, c} where the identity is 1′ , all atoms
are self-converse and multiplication is defined by the table below, known to
Maddux as relation algebra 2565 , [Mad06]. A strong representation of it is
illustrated on the right.
;
1′
a
b
c

1′
1′
a
b
c

a
a
1′
c
b

b
b
c
1′
a

3

c
c
b
a
1′

a
c

b
b

1

0
a

c
2

This algebra happens to be associative (hence a relation algebra). The only
consistent triples of non-identity atoms are the permutations of (a, b, c). If
we restrict the base to a set of three elements, say {1, 2, 3}, we obtain a different qualitative representation, no longer a strong representation because
although 1′ = c; c and (2, 2) is in the representation of 1′ , there is no point
v in the base {1, 2, 3} such that (2, v) and (v, 2) are in the representation
of c. This relation algebra can have no qualitative representation, nor even
a feeble representation, on a base of more than four points, because it is
impossible to colour the edges of K5 using three colours, a, b, c, while avoiding triangles with two edges of the same colour. In fact the two qualitative
representations just mentioned are the only qualitative representations of
this relation algebra, up to base isomorphism.
(4) Our next example is a non-associative algebra which does not have a qualitative representation, though it has a feeble one. Its atoms are {e, e′ , a, a˘},
1′ = e + e′ and composition is given by
e e′
;
e e 0
e′ 0 e′
a 0 a
a˘ a˘ 0

a
a
0
a
a + a˘ + e′

a˘
0
a˘
a + a˘ + e
a˘

12

ROBIN HIRSCH, MARCEL JACKSON, AND TOMASZ KOWALSKI

By Lemma 5 this is the atom structure of a non-associative algebra (not
associative because a = a; a = (a; e′ ); a 6= a; (e′ ; a) = a; 0 = 0). A feeble
representation θ on the points 0, 1 is shown below
a˘
e

0

1

e′

a
If φ were a qualitative representation then since a; a · a 6= 0 there would
be x, y, z in the base such that (x, y), (y, z), (x, z) ∈ aφ and (y, y) ∈ (1′ )φ .
Since 1′ = e + e′ either (y, y) ∈ eφ or (y, y) ∈ (e′ )φ , in the former case
(x, y) ∈ aφ ◦ eφ ⊆ (a; e)φ = 0φ and in the latter case (y, z) ∈ (e′ ; a)φ = 0φ ,
in each case we get a contradiction.
(5) Examples of relation algebras not even possessing feeble representations are
provided in the proof of Theorem 19 below.
(6) This example shows that associativity does not suffice to ensure a qualitatively representable algebra has a strong representation. Let K be McKenzie’s non-representable algebra (see [McK70]). It is defined by the following
multiplication table for the atoms
; 1′
a
1′ 1′
a
a
a a
a˘ a˘
1
b b a+b

a˘
b
a˘
b
1
a+b
a˘
a˘ + b
a˘ + b
−b

8•
♣♣♣ ^❂❂❂
❂❂
♣♣♣
•O
❂❂
❂
•
✁@
✁
✁
• f◆◆◆
✁✁
◆◆◆ ✁✁✁
•

where b˘ = b. As McKenzie showed, it is associative but has no strong
representation. Let N5 be the pentagon lattice considered as an ordered set,
illustrated in the right above. It is easy to show that boolean combinations
of the relations Id, <, >, # (where # stands for incomparability), form
a herd over N5 × N5 , and the map 1′ 7→ Id, a 7→ <, a˘ 7→ >, b 7→ #,
extends naturally to a qualitative representation of K. We leave it as an
instructive exercise to prove that no qualitative representation can exist
over a set with 4 or fewer elements. (Hint: you have to be able to compose
incomparability with itself and get < and >.)
(7) Our final example is an infinite relation algebra, for expressing metric constraints on a linearly ordered metric space. Its elements are finite unions of
real intervals, e.g. (2, 5) ∪ [6, 8]. There is one identity atom, namely [0, 0],
converse is defined by (m, n)˘ = (−n, −m), and composition is defined by
(m, n); (m′ , n′ ) = (m + m′ , n + n′ ) for m > n, m′ > n′ , with similar definitions for closed and semi-open intervals. A strong representation θ over
the real numbers may be obtained by letting (x, y) ∈ (m, n)θ ⇐⇒ m <
y − x < n, with similar definitions for closed and semi-open intervals. This
provides a useful way of expressing metric constraints between points, e.g.
the constraint (x, y) ∈ ([−3, −2] ∪ [2, 3])θ means that the distance between
x and y is at least two and not more than three.

ALGEBRAIC FOUNDATIONS FOR QUALITATIVE CALCULI AND NETWORKS

13

4. Semi-associativity and associativity
In order to axiomatise the class of qualitatively representable algebras we might
start by taking the axioms of non-associative relation algebra and add some weakening of the associativity law. Maddux deﬁnes two such weakenings: the semiassociative law x ; (1 ; 1) = (x ; 1) ; 1 and the weak-asociativity law [Mad82]
(x · 1′ ) ; (1 ; 1) = ((x · 1′ ) ; 1) ; 1. In the deﬁnition of the qualitative calculus
given by [LR04] the identity 1′ is required to be an atom and for this case the
weak associativity law is sure to hold (since x · 1′ is either 0 or 1′ ) as shown in
[WHW14, Section 3]. However, when we consider cases where the identity is not
an atom, we see that the algebra of Examples 6.1 above fails the weak associativity law (and consequently also fails the stronger semi-associativity law) because
(e ; 1) ; 1 = (e + d) ; 1 = 1 but e ; (1 ; 1) = e ; 1 = e + d, so weak associativity is not
valid over qualitative representations. On the other hand, since (a; b)θ ⊇ aθ ◦ bθ ,
for any qualitative (or feeble) representation θ over domain D, it follows that the
equation
(1 ; x) ; 1 = 1 ; (x ; 1)
is an example of a validity over qualitative (respectively, feeble) representations (in
any herd on base D, both sides equal 1 = D × D if x 6= 0 and both sides equal 0 if
x = 0).
An algebra is integral if x ; y = 0 → x = 0 or y = 0. It is known for semiassociative algebras that an algebra is integral iﬀ the identity is an atom [Mad90,
Theorem 4]. However, in the algebra of Example 6.2 above, the identity is an atom
but the algebra is not integral. It follows that this algebra is not semi-associative,
indeed d ; 1 = 1′ + d + f but (d ; 1) ; 1 = 1.
Semi-associativity for weak composition was touched upon in [LR04] where it was
shown that if relations are serial (have total domains) then the weak composition
is semi-associative. In fact, in our more general setting where the identity need not
be an atom, it suﬃces to assume that nonempty relations have pairwise overlapping
domains.
LEMMA 7. Let φ be a qualitative representation of a non-associative algebra A
to a herd S. Then, the following are equivalent :
(1) If a, b ∈ A \ {0} then (aφ )˘ ◦ bφ 6= ∅ (nonempty relations have overlapping
domains),
(2) A is integral,
(3) A is semi-associative and the identity is an atom.
Proof. As we noted, in semi-associative algebras integrality is equivalent to the
identity being an atom so we get (3) ⇒ (2). To prove (2) ⇒ (3) we will show that
integrality implies semi-associativity in non-associative algebras. Working backwards, suppose semi-associativity fails in A. By monotonicity of composition in
non-associative algebras, since 1′ ≤ 1, we have x ; (1 ; 1) = x ; 1 ≤ (x ; 1) ; 1, for any
x ∈ A. Thus, the failure of semi-associativity is witnessed by some 0 6= a ∈ A such
that a ; 1 < (a; 1); 1. So, there is (a; 1); 1 ≥ b 6= 0 such that a ; 1 · b = 0. But then,
a˘ ; b · 1 = 0 by the Peircean law, and so a˘ ; b = 0 where a˘, b 6= 0 and the algebra
is not integral. Thus the equivalence of (2) and (3) is true in any non-associative
algebra.

14

ROBIN HIRSCH, MARCEL JACKSON, AND TOMASZ KOWALSKI

To prove the equivalence of (2) and (1), observe that a = 0 ⇐⇒ a˘ = 0 and
(a˘)φ ◦ bφ = ∅ ⇐⇒ (a˘; b)φ = ∅ ⇐⇒ a˘; b = 0, using the fact that c = a˘; b is the
minimal solution of cφ ⊇ (a˘)φ ◦ bφ .

Let A be a non-associative algebra, and φ be a qualitative representation, i.e. a
map from A to P(D × D) for some set D satisfying the conditions of Deﬁnition 2.
Consider the following condition on φ:
(*)

(aφ ◦ bφ ) ∩ (cφ ◦ dφ ) = ∅ ⇐⇒ (a ; b) · (c ; d) = 0.

Intuitively, (*) says that two consistent triangles share a label (the right-hand side)
if and only if a quadrangle witnessing this fact can be found in the representation (the left-hand side). Observe that the right-to-left implication holds for any
qualitative representation φ, since (x; y)φ ⊇ xφ ◦ y φ .
THEOREM 8. If there exists a qualitative representation of A satisfying (*),
then A is associative.
Proof. To prove associativity, let a, b, c, d ∈ A be arbitrary. Then
((a ; b) ; c) · d = 0 ⇐⇒ (a ; b) · (d ; c˘) = 0
φ

φ

φ

by Peircean law for ;
φ

⇐⇒ (a ◦ b ) ∩ (d ◦ c˘ ) = ∅

(*)

⇐⇒ ((aφ ◦ bφ ) ◦ cφ ) ∩ dφ = ∅

Peircean law for ◦

φ

φ

φ

φ

associativity of ◦

φ

⇐⇒ (b ◦ c ) ∩ (a˘ ◦ d ) = ∅

Peircean law for ◦

⇐⇒ (b; c) · (a˘; d) = 0

(*)

⇐⇒ (a ; (b ; c)) · d = 0

Peircean law for ;

⇐⇒ (a ◦ (b ◦ c )) ∩ d = ∅
φ

φ

φ

Since d is arbitrary it follows that (a; b); c = a; (b; c).



Observe that the McKenzie algebra K is associative, but its qualitative representation of over the base N5 does not satisfy (*), because we have (#◦<)∩(#◦>) = ∅
whereas (b ; a) · (b ; a˘) = b. However, there is a qualitative representation of K
satisfying (*), for example over the base D = {⊥, a1 , b1 , c1 , a2 , b2 , c2 , ⊤} with <
deﬁned as the transitive closure of ⊥ < a1 < b1 < c1 < ⊤, ⊥ < a2 < b2 < c2 < ⊤.
The following conjecture remains open: if A is associative and has a qualitative
representation then it has a qualitative representation satisfying (*).
5. Network Satisfaction Problem
DEFINITION 9. Let A be a non-associative algebra. A network (N, λ) over A
consists of a finite set N of nodes and a function λ : (N × N ) → A. A network
(N, λ) is consistent if
(a) λ(x, x) ≤ 1′ ,
(b) λ(x, y) ; λ(y, z) · λ(x, z) 6= 0, for all nodes x, y, z ∈ N ,
(c) λ(x, y) · λ(y, x)˘ 6= 0,
(d) λ(x, y) 6= 0, for all nodes x, y ∈ N .
A network (N, λ) is path-consistent (or algebraically closed) if it is consistent and
additionally λ(x, y); λ(y, z) ≥ λ(x, z), for all x, y, z ∈ N . An atomic network (N, λ)
is a network where λ(x, y) is always an atom of A. Every consistent atomic network
is path-consistent.

ALGEBRAIC FOUNDATIONS FOR QUALITATIVE CALCULI AND NETWORKS

15

A network (N, λ) embeds into a strong representation φ if there is a map ′
from N to the base of φ such that for all x, y ∈ N we have (x′ , y ′ ) ∈ λ(x, y)φ ,
similarly (N, λ) embeds into a qualitative representation θ if there is a map ′ from
N to the base of a qualitative representation θ such that for all x, y ∈ N we have
(x′ , y ′ ) ∈ λ(x, y)θ . A network over A is strongly satisﬁable if it embeds into some
strong representation of A and it is qualitatively satisﬁable if it embeds into some
qualitative representation of A. Clearly, if (N, λ) is strongly satisfiable then it is
qualitatively satisfiable.
A strong representation φ of the finite relation algebra A is universal if every
consistent atomic network embeds into φ.
Note that the conditions (c) and (d) for a consistent network follow from (a) and
(b) (see [HH02, Lemma 7.2]), so we could have left them out of the deﬁnition, but
since they are naturally expected nonetheless, we decided to keep them in. Our
deﬁnition of a consistent network coincides with what Hirsch and Hodkinson [HH02]
call a network. We believe this less restrictive deﬁnition of a network (essentially,
just as a labelled complete directed graph) to be more convenient in the present
context as it is closer to the standard terminology used in the area of qualitative
calculi as well as in constraint satisfaction.
REMARK 10. Conisider the non-associative algebra of Example 6.1. It has a
qualitative representation, but since it is not associative it can have no strong representation. The network shown in Example 6.1 is qualitatively satisfiable but not
strongly satisfiable.
Let A be an atomic relation algebra. If A has a universal representation then
any network is qualitatively satisfiable iff it is strongly satisfiable. It is known
that the point and interval algebras have universal representations [LM94] and it
follows from results in [BW11] that RCC8 has a universal representation, hence for
these three relation algebras a network is strongly satisfiable iff it is qualitatively
satisfiable.
LEMMA 11. Let A be a finite non-associative algebra. A has a qualitative representation if and only if there is a consistent atomic network (N, λ) over A such
that for each consistent triple of atoms (a, b, c) of A there are nodes x, y, z ∈ N
such that λ(x, y) = a, λ(y, z) = b and λ(x, z) = c.
Proof. Let φ be a qualitative representation over base D. For each x, y ∈ D let
λ(x, y) be the (unique) atom a such that (x, y) ∈ aφ , such an atom must exist since
A is ﬁnite. Clearly (D, λ) is consistent and atomic, though it might be inﬁnite.
Furthermore, if a, b, c are atoms such that a ; b ≥ c then there must be x, y, z with
λ(x, y) = a, λ(y, z) = b and λ(x, z) = c, by Lemma 3. Hence there is a ﬁnite subset
D0 ⊆ D such that the restriction of λ to D0 is atomic, consistent and therefore an
atomic network, and still witnesses all triples of atoms,
Conversely, if (N, λ) is a consistent atomic network witnessing all consistent
triples of atoms then the binary relation ∼ over the nodes of N deﬁned by x ∼
y ⇐⇒ N (x, y) ≤ 1′ is easily seen to be an equivalence relation, indeed a congruence. The equivalence class of a node x is denoted [x]. We may deﬁne a qualitative
representation φ whose base is the set of all ∼-equivalence classes, by
aφ = {([x], [y]) : N (x, y) ≤ a}

16

ROBIN HIRSCH, MARCEL JACKSON, AND TOMASZ KOWALSKI

for a ∈ A. Since ∼ is a congruence φ is well-deﬁned, since edges are labelled by
atoms φ respects the boolean operators, since the network is consistent it is clear
that φ respects the converse operator, and since N (x, y) ≤ 1′ ⇐⇒ [x] = [y] the
identity is correctly represented. By Lemma 3, φ is a qualitative representation. 
LEMMA 12. If A is a finite, qualitatively representable, atomic non-associative
algebra then A has a qualitative representation with at most 3|At(A)|3 points in its
base.
Proof. By the previous lemma, if A is qualitatively representable then there is a
consistent atomic network witnessing all consistent triples of atoms. There are at
most |At(A)|3 such triples, so 3|At(A)|3 points suﬃce to witness them all. The
atomic network deﬁned by restricting to this set of up to 3|At(A)|3 points is consistent and still witnesses all consistent triples of atoms, hence it deﬁnes a qualitative
representation of the required size, by the proof of the right to left implication of
Lemma 11.

The upper bound of Lemma 12 seems to overestimate the necessary size of a
qualitative representation rather largely. Although we will not try to provide a
sharper bound here, we will present an illustrative example. Consider RCC5: a
version of RCC8 with no distinction between “tangential” and “non-tangential”
connectedness. Its composition table is
ε
; 1′
1′ 1′
ε
ε ε
ε
ε˘ ε˘ 1′ + ε + ε˘ + π
π π
ε+π
ε+π+δ
δ δ

ε˘
ε˘
1
ε˘
ε˘ + π + δ
δ

π
π
ε+π+δ
ε˘ + π
1
ε+π+δ

δ
δ
δ
ε˘ + π + δ
ε˘ + π + δ
1

with ε, π and δ interpreted intuitively as proper part, proper overlap, and disjointness relations, respectively. This algebra has a qualitative representation over a
base consisting of just eleven “regions”, namely, the following subsets of {1, . . . , 7}:
A = {1, 6}

B = {1, 2, 3, 5, 6}

C = {1, 2, 6}

D = {1, 2, 3, 5, 6, 7}

E = {1}

F = {1, 2, 3, 5}

G = {2, 3}

H = {1, 4, 6}

I = {1, 3}

J = {1, 2, 3, 4, 5}

K = {4, 5, 6}

with the relations ε, π and δ mapped, respectively, to proper subset relation,
nonempty symmetric diﬀerence relation, and empty intersection relation.
We conjecture that our representation on the 11 regions A, . . . , K is the smallest
number of regions possible for a qualitative representation of RCC5.
REMARK 13. The study of syllogistics [Aristotle, prior analytics] can be described using RCC5. Namely, setting:
Every S is P

iff

(S, P ) ∈ 1′ + ε

Some S is P

iff

(S, P ) ∈ 1′ + ε + ε˘ + π

No S is P

iff

(S, P ) ∈ δ

Some S is not P

iff

(S, P ) ∈ ε˘ + π + δ

we obtain a faithful interpretation of traditional logic of categorical propositions.

ALGEBRAIC FOUNDATIONS FOR QUALITATIVE CALCULI AND NETWORKS

17

We turn to questions of computational complexity. We say that a ﬁnite atom
structure has a qualitative representation if its complex algebra has one. We begin
with a result that contrasts with the corresponding question for strong representations which is known to be undecidable [HH01b].
THEOREM 14. The problem of determining whether a finite atom structure has
a qualitative representation is NP-complete.
Proof. If a ﬁnite atom structure with n atoms has a qualitative representation
then, by Lemma 12, it has a qualitative representation of size at most 3n3 . Hence
a non-deterministic algorithm may simply construct a base with up to 3n3 points
and guess an atom between each pair of points, then check to see if the resulting
network is consistent and that every triple of atoms is witnessed (see Lemma 11).
Since the run-time of this non-deterministic algorithm is bounded by a polynomial
function, we conclude that the qualitative representation problem is in NP.
For NP-hardness, we reduce the 3-colour graph vertex problem for ﬁnite graphs.
Let G = (V, E) be a ﬁnite graph with vertices V and directed edges E, where this
edge set is symmetric and irreﬂexive. Cases where E = ∅ are trivially 1-colourable,
so we assume E 6= ∅. If we extend G by adding some isolated vertices to V it will
not aﬀect the 3-colourability of the graph, so we assume that G has an independent
set of size 5 (formally, there are v0 , v1 , . . . , v4 ∈ V such that (vi , vj ) 6∈ E, for i, j < 5)
and a triangle containing one edge and two non-edges (there are u, v, w ∈ V such
that (u, v) ∈ E but (u, w), (v, w) 6∈ E). Next, we extend G to G∞ = (V ∞ , E∞ ), by
adding a single node connected to all the nodes of V , i.e. V ∞ = V ∪ {∞}, E∞ =
E ∪ {(∞, u), (u, ∞) : u ∈ V }, where ∞ 6∈ V . It is clear that G∞ is 4-colourable if
and only if G is 3-colourable. Because G has an independent set of size 5, any 4colouring of G∞ must include non-adjacent nodes of the same colour, and because
of the triangle with one edge and two non-edges any colouring must include nonadjacent nodes of diﬀerent colours.
We deﬁne a non-associative atom structure (S, E,˘, C) as follows. The set of
atoms is
S = {1′ } ∪ SGG ∪ SCC ∪ SGC ∪ SCG
where SGG = {suv : (u, v) ∈ E∞ }∪{g} (graph atoms, here g is a symbol not appearing in V ∞ , used for non-edges), SCC = {a, b, c} (colouring atoms), SGC = {y, n}
(used to map graph nodes to colours) and SCG = {y˘, n˘} (the converses of SGC ).
The identity is an atom E = {1′ }, and all atoms are self-converse except suv˘ = svu
and the converses of y, n are y˘, n˘ respectively. [The intention here is that atoms suv
will be used to encode the edges (u, v) of the graph G∞ , g (“gap”) corresponds to
non-edges and the atoms a, b, c ∈ SCC will encode the undirected edges of a graph
with no more than four nodes (see Examples 6.3) and these nodes will represent
distinct colours. y, y˘ (“yes”) and n, n˘ (“no”) will be used to connect this set of
up to four nodes to the nodes of G∞ while encoding a legitimate 4-colouring. A
schematic of the desired qualitative representation is shown in Figure 3.]
All Peircean transforms of the following triples of atoms are forbidden.
(I) (1′ , x, y) where x 6= y, (identity law)
(II) (α, β, γ), where α ∈ SIJ , β ∈ SJ ′ K ′ and γ ∈ SI ∗ K ∗ , unless I = I ∗ , J =
J ′ , K ′ = K ∗ (∈ {G, C}) (types must match),
(III) (α, α, β) where α, β ∈ SCC , (see Examples 6.3, only permutations of the
triple (a, b, c) are consistent for SCC atoms),

18

ROBIN HIRSCH, MARCEL JACKSON, AND TOMASZ KOWALSKI

∞
y
1

n
n

2

c

a
c

0
s0,5

3

4

s4,5

b

b

a

5

Figure 3. A schematic diagram of the intended qualitative representation for (S, E,˘, C), when G is 3-colourable. The graph G∞
is on the left, with vertex set {0, 1, 2, 3, 4, 5, ∞} and edges shown
in black. An independent set can be found on the ﬁve vertices
{0, 1, 2, 3, 4} and a triple of vertices with one edge can be found at
{0, 1, 5}. The vertex ∞ is adjacent to all vertices and nonedges are
shown in grey (and would be labeled by g). On the right, there is
a second tetrahedral graph on 4 vertices (with names γ1 , γ2 , γ3 , γ4
omitted) and with undirected edges a, b, c as in Example 6.3. Edges
connecting the graph G∞ to these vertices are labelled y or n, according to the colour of the vertex of G∞ .
(IV) (suv , sv′ w′ , α) where (u, v), (v ′ , w′ ) ∈ E∞ , unless v = v ′ (node indices must
match),
(V) (suv , svw , g) where (u, v), (v, w) ∈ E∞ and either (u, w) ∈ E∞ or u = w, (g
only allowed on non-edges),
(VI) (s∞u , α, g) where u ∈ V, α ∈ SGG (∞ adjacent to all other nodes),
(VII) (y, α, y) where α ∈ SCC (only one colour per node)
(VIII) (suv , y, y) where (u, v) ∈ E∞ (adjacent nodes have diﬀerent colours)
The set C of consistent triples of atoms consists of all triples not forbidden by
(I)–(VIII), above.
The reduction maps (V, E) to the atom structure (S, E,˘, C) just deﬁned. We
check that this reduction is correct. Suppose ρ is a 4-colouring of the vertices of
G∞ such that adjacent nodes have diﬀerent colours, there are non-adjacent nodes
of the same colour and non-adjacent nodes of diﬀerent colours. Let the colours be
γ1 , γ2 , γ3 , γ4 . We deﬁne an atomic network (N, λ) where N = V ∞ ∪ {γ1 , γ2 , γ3 , γ4 }.
For the labelling λ we let λ(x, x) = 1′ (all x ∈ N ), λ(u, v) = suv for (u, v) ∈ E∞ ,
λ(u, v) = g if u 6= v ∈ V ∞ , (u, v) ∈
/ E. As in the strong representation for
Examples 6.3, let λ(γ1 , γ2 ) = λ(γ3 , γ4 ) = a, λ(γ1 , γ3 ) = λ(γ2 , γ4 ) = b, λ(γ1 , γ4 ) =
λ(γ2 , γ3 ) = c and λ(γj , γi ) = λ(γi , γj ) for 1 ≤ i < j ≤ 4. Finally, for each u ∈ V ∞
and for 1 ≤ i ≤ 4, let λ(v, γi ) = y if ρ(v) = γi else (if ρ(v) 6= γi ) λ(v, γi ) = n.
The atoms y˘ and n˘ are used to label the converse edges for edges labelled y, n
respectively. It is a routine check that this deﬁnes a consistent atomic network.
Since there are non-adjacent nodes of the same colour the triple (g, y, y) is witnessed

ALGEBRAIC FOUNDATIONS FOR QUALITATIVE CALCULI AND NETWORKS

19

and since there are non-adjacent nodes of diﬀerent colours (g, y, n) and (g, n, y) are
also witnessed. It is easily checked that all other consistent triples of atoms are also
witnessed hence, by Lemma 11, the complex algebra over (S, E,˘, C) is qualitatively
representable.
For the converse, let (N, λ) be any complete, consistent atomic network witnessing each consistent triple and containing no forbidden triples for the atom structure (S, E,˘, C): in other words, (N, λ) provides a qualitative representation of
(S, E,˘, C). We show that G∞ is 4-colourable, hence G is 3-colourable. By forbidden triple II, a triple (α, β, γ) is forbidden if exactly one or all three of α, β, γ belongs
to SGC ∪ SCG . Hence the edges labelled by atoms in SGC ∪ SCG = {y, y˘, n, n˘}
form a complete bipartite graph on N , say N is the disjoint union of N1 and N2 .
By forbidden triple II again, every edge with source in N1 (say) and target in N2
has a label in SGC , every edge with source in N2 and target in N1 has a label in
SCG , edges with source and target within N1 have label in {1′ } ∪ SGG and edges
with source and target in N2 have label in {1′ } ∪ SCC .
Now we show that |N1 | = |V ∞ | and that the labels suv deﬁne a graph on N1
isomorphic to G∞ . Let u ∈ V and let ∞′ , u′ ∈ N1 denote the source and target
of some edge labelled by s∞u . For each x ∈ N1 \ {∞′ } the edge (∞′ , x) must be
labelled by s∞v for some v ∈ V by forbidden triples II, IV and VI, and if (∞′ , y) is
also labelled by s∞′ v then x = y by forbidden triple V. Hence there is a bijection
′
: V ∞ → N1 mapping ∞ to ∞′ and mapping v ∈ V to the unique v ′ ∈ N1 such
that (∞′ , v ′ ) is labelled s∞v . So we may assume that N1 is identical to the set V ∞ ,
and that the label of each edge (∞, w) (for w ∈ V ) is s∞w . By forbidden triples IV
and V we see that the label of the edge (u, v) is suv if (u, v) ∈ E, 1′ if u = v and g
otherwise. By forbidden triple III, N2 cannot have more than four points, (we saw
in Examples 6.3 that N2 has either three or four points).
Let u ∈ N1 . As (y, y, α) is always forbidden by VII, there is at most one edge
labelled y leaving u and because (svu , y, n) is consistent and the edge labelled svu
is unique (where (u, v) ∈ E), there is exactly one edge labelled y leaving u. Thus,
we may deﬁne a map ρ : V ∞ → N2 by letting ρ(u) be the unique element of N2
such λ(u, ρ(u)) = y, for each u ∈ V ∞ = N1 . Since (suv , y, y) is forbidden by VIII
whenever (u, v) ∈ E∞ , ρ is a valid 4-colouring of G∞ .

THEOREM 15. Let A be a finite non-associative algebra. The network qualitative
satisfaction problem over A is in NP.
Proof. For each consistent triple of atoms t, let (Tt , λt ) be a partially labelled atomic
network with three nodes, witnessing the triple of atoms. Assume for distinct consistent triples t, s that Tt ∩ Ts = ∅. Given a network (N, λ), take the disjoint union
of (N, λ) and the disjoint partial triangles (Tt , λt ) as t ranges over consistent triples
of atoms. Then, non-deterministically guess all unlabelled edges and for each edge
(x, y) of N , guess an atom below λ(x, y). Finally check that the resulting atomic
network is consistent. By Lemma 11, this correctly tests qualitative satisﬁability
and runs non-deterministically in polynomial time.

A traditional approach to solving the network satisfaction problem (for strong
representations) is to reﬁne a given network to a path consistent network on the
same nodes. This path-consistent reﬁnement may be computed deterministically
in cubic time. If the reﬁned network is inconsistent (has a zero label) then the
original network is unsatisﬁable. There are some algebras where the converse also

20

ROBIN HIRSCH, MARCEL JACKSON, AND TOMASZ KOWALSKI

holds — if the reﬁned network is consistent then the original network must be
satisﬁable — for example, path-consistency entails satisﬁability for networks over
the Point Algebra [VKvB89, Theorem 5]. However, for many relation algebras
the converse fails, for example, there are known path-consistent but unsatisﬁable
networks over the Allen Interval Algebra [All83, Figure 5]. The Allen Interval
algebra possesses a universal representation (see Deﬁnition 9), so the satisﬁability
of a network may be tested along the lines of the proof of the preceding theorem, by
non-deterministically picking an atom below the label of each edge of the network
and checking the consistency of the resulting atomic reﬁnement. Such satisﬁability
checkers may run faster if a network is ﬁrst reﬁned to a path-consistent network,
before the non-deterministic choice of atoms is made. For algebras which do not
have universal representations however, it is not suﬃcient to ﬁnd a consistent atomic
reﬁnement of a network, for example, there are consistent atomic networks over the
interval-with-duration calculus INDU, not satisﬁable in any strong representation
(see our remarks in Section 1.1). Indeed there are ﬁnite relation algebras for which
the network satisfaction problem is undecidable [Hir99].
Nevertheless, for qualitative representations the non-deterministic algorithm given
in the preceding theorem is necessary and suﬃcient for qualitative representability.
Hence in general the network qualitative satisfaction problem can have much lower
complexity than the network satisfaction problem.
THEOREM 16. The problem of determining whether an equation is valid over
qualitative representations is co-NP-complete.
Proof. Let t(x̄) = s(x̄) be an equation that fails in some herd S, where x̄ =
(x0 , . . . , xk−1 ) is a ﬁnite tuple of variables. Then t(ā)S 6= s(ā)S holds for some
tuple ā = (a0 , . . . , ak−1 ) of relations in the herd S and there is a pair of points
x, y from the base of S such that (x, y) belongs to one but not the other of t(ā)S
and s(ā)S . Let X be a ﬁnite subset of the base of S including x and y and also
including, for each subterm p; q occuring in either s or t, three points u, v, w such
that (u, v) ∈ p and (v, w) ∈ q, provided such points exist in the base of S. The
size of X is at most three times the length of the equation t(x̄) = s(x̄). Let
S↾X be the herd on the base X consisting of the relations {r ∩ (X × X) : r ∈ S}.
Lemma 3 and a simple induction shows that (u, v) ∈ p(a0 , . . . , ak−1 )S ⇐⇒ (u, v) ∈
p(a0 ∩ (X × X), . . . , ak−1 ∩ (X × X))S↾X , for any u, v ∈ X and any subterm
p(x̄) of either t(x̄) or s(x̄). Hence (x, y) belongs to one but not the other of
t(a0 ∩ (X × X), . . . , ak−1 ∩ (X × X))S↾X , s(a0 ∩ (X × X), . . . , ak−1 ∩ (X × X))S↾X
and the equations t(x̄) = s(x̄) fails in a herd on a base of size at most three times
the length of the equation. Thus, the failure of the equation may be tested nondeterministically by choosing a base of size at most three times the length of the
equation, guessing which pairs of points belong to each of the relations x0 , . . . , xk−1
and verifying that the equation fails. This proves that the validity of equations
problem is co-NP.
Validity is co-NP-hard because the validity problem for propositional formulas
reduces to it.

The reader has probably guessed, or knows already, that the corresponding problem for strongly representable relation algebras is much harder: the equational
theory of strongly representable relation algebras is undecidable [Tar41].

ALGEBRAIC FOUNDATIONS FOR QUALITATIVE CALCULI AND NETWORKS

21

6. Feeble representations
We mentioned earlier that [LR04, Deﬁnition 3] only requires (a; b)φ ⊇ aφ ◦ bφ in
their deﬁnition of weak composition, and do not insist on minimality subject to that
(although elsewhere in their paper they imply a deﬁnition which accords with our
deﬁnition of qualitative representation, see Deﬁnition 2.4). In this section we investigate this weaker type of representability. Although qualitative representations are
of greater relevance to much of the literature in qualitative calculi, feeble representations are more directly related to research on the binary constraint satisfaction
problem, where for any constraints a, b and a solution for variables x, y, z, we may
infer from a(x, y), b(y, z) that (a ◦ b)(x, z) holds, but there is no requirement, given
(a ◦ b)(x, z), that there should be three variables x′ , y ′ , z ′ such that a(x′ , y ′ ) and
b(y ′ , z ′ ).
Let A be a non-associative algebra and let φ : A → ℘(D × D) (some base D)
respect the boolean operators, represent 1′ as the identity and respect the converse
operator. If (a; b)φ ⊇ aφ ◦ bφ (for all a, b ∈ A) then φ is called a feeble qualitative
representation, or simply a feeble representation, of A. The proof of the following
lemma is very similar to the proof of Lemma 11.
LEMMA 17. Let A be a finite non-associative algebra. A has a feeble representation if and only if there is a consistent atomic network (N, λ) over A such that
for every atom a of A there are x, y ∈ N with λ(x, y) = a.
In a feeble representation of a ﬁnite algebra, instead of requiring a witness for
each consistent triple of atoms, we only require a witness for each each single atom,
while avoiding any forbidden triple of atoms.
One obvious shortcoming of this notion is that a feeble representation of an
algebra A does not determine A, because some consistent triples may be absent in
the representation. Indeed, we saw that the herd on a base of two points shown
in the second part of Example 6.1 provides a feeble representation of two nonisomorphic non-associative algebras: the algebra of Example 6.1 and the algebra of
Example 6.4. Unfortunately, the complexity of the feeble representation problem
remains the same as that of the qualitative representation problem.
THEOREM 18. The problem of determining whether a finite atom structure has
a feeble representation is NP-complete.
Proof. If a ﬁnite atom structure with n atoms has a feeble representation then we
may restrict the base to a set of at most 2n points so that all atoms are still witnessed
in the restriction, hence the atom structure has a feeble representation of size at
most 2n. Thus, a non-deterministic algorithm may guess an atomic labelling over
a set of at most 2n points and check if the labelling deﬁnes a feeble representation.
So the feeble representation problem is in NP.
For NP-hardness, we reduce the Monochromatic Triangle problem for ﬁnite
graphs. Let G = (V, E) be a ﬁnite graph with vertices V and directed, irreﬂexive,
symmetric edges E (i.e. (u, v) ∈ E ⇐⇒ (v, u) ∈ E). The Monochromatic Triangle
problem asks if there is a 2-colouring of the edges, that is, a symmetric function
ρ : E → {r, b} such that ρ is not constant over the three edges of any triangle of
the graph. This problem is known to be NP-complete, see [GJ79, p. 191]. Any
complete graph with six or more nodes is a no instance, hence we will only consider
instances of this problem containing at least one non-edge.

22

ROBIN HIRSCH, MARCEL JACKSON, AND TOMASZ KOWALSKI

u
r
v
u

v

g

b(v,w)
pv

u′
g

b(u,v)
w

×

v′

r(v,w)
qv

pw
∞

w

×

r(u,v)
pu

b

×

w′

qu

qw
∞′

Figure 4. A 2-colouring of the edges (u, v), (v, w) of a graph with
nodes u, v, w (above) and a consistent atomic network witnessing
all atoms in (S, E,˘, C), obtained from it (below). The atomic
network determines a feeble representation.

Given a symmetric, irreﬂexive graph G = (V, E), we deﬁne a non-associative
atom structure (S, E,˘, C) as follows.
S = {1′ } ∪ {×} ∪ SGG ∪ S∞G ∪ SG∞
where SGG = {cuv : c ∈ {r, b}, (u, v) ∈ E} ∪ {g}, S∞G = {pu , qu : u ∈ V } and
SG∞ = {p˘u , q˘u : u ∈ V }. The identity is an atom E = {1′ } and converse is
deﬁned by cuv˘ = cvu (for any c ∈ {r, b} and (u, v) ∈ E) , the converses of pu , qu are
p˘u , q˘u and 1′ , ×, g are self-converse. Let C consist of all triples of atoms except
for Peircean transforms of the following forbidden triples of atoms.
(1′ , x, y), where x 6= y,
(×, ×, ×) and (×, α, β), where × 6∈ {α, β},
(α, β, γ) where α ∈ SIJ , β ∈ SJ ′ K and any atom γ, unless J = J ′ ,
(pu , cu1 v , pv1 ), (qu , cu1 v , qv ), any c ∈ {r, b} any u, u1 , v, v1 ∈ V , unless
u = u1 and v = v1 ,
(V) (pu , g, pv ), (qu , g, qv ), where (u, v) ∈ E or u = v,
(VI) (pu , α, qv ), for any atom α and any u, v ∈ V ,
(VII) (cuv , cvw , cuw ), any c ∈ {r, b} and any u, v, w ∈ V .
(I)
(II)
(III)
(IV)

Note that the set of atoms does not include a subset S∞∞ , so triples III and II
forbid all triples of non-identity atoms of the form (α, β, γ) where α ∈ S∞G and
β ∈ SG∞ , thus pu ; p˘v equals 1′ if u = v else it is zero, for all u, v ∈ V . Also, there
are no atoms cuu for c ∈ {r, b} since (u, u) 6∈ E, so by forbidden triples II, III IV, V
we have p˘u ; pu = 1′ . Similarly qu ; q˘v ≤ 1′ and q˘u ; qu = 1′ .

ALGEBRAIC FOUNDATIONS FOR QUALITATIVE CALCULI AND NETWORKS

23

The reduction maps (V, E) to the complex algebra of the atom structure (S, E,˘, C)
just deﬁned. Before we prove the correctness of this reduction, we mention the intended roles of the atoms. Given any consistent, atomic network witnessing all
atoms, the atom × will deﬁne a bipartite edge relation over the set of nodes of the
network (as in Examples 6.2). Each part of the network contains a copy of the
graph together with a single auxiliary node and will encode a valid colouring of the
graph, with atoms ruv and buv encoding edges coloured red and blue, respectively,
while g (“gap”) corresponds to non-edges. The atom pu labels the edge from the
auxiliary node to u in one part of the network while the atom qu is used in the
other part. They are used to ensure that the encoding describes the way edges ﬁt
together correctly. Conversely, given an arbitrary edge colouring of G there is dual
colouring obtained by swapping red and blue edge labels. By using the colouring
on one copy of G and the dual colouring on another copy of G we may construct a
consistent, atomic network in which each atom ruv and buv is witnessed. Such an
atomic network is illustrated in Figure 4, based on a two colouring of a three node
graph.
Now we make this more precise by checking that the reduction is correct. Suppose ρ : E → {r, b} is a symmetric colouring avoiding monochrome triangles.
Let V+ consist of the nodes of V together with a single extra point ∞ and let
V+′ = {x′ : x ∈ V+ } be a set of the same size as V+ disjoint from it. We will deﬁne
an atomic network (V+ ∪ V+′ , λ) avoiding all forbidden triples (so consistent) and
witnessing every atom, thereby showing that the complex algebra over (S, E,˘, C)
has a feeble representation. To deﬁne λ:
λ(x, x) = 1′

x ∈ V+ ∪ V+′

λ(x, y ′ ) = ×

x ∈ V+ , y ′ ∈ V+′

λ(∞, u) = pu

u∈V

′

′

λ(∞ , u ) = qu
λ(u, v) = cuv

u∈V
(u, v) ∈ E, ρ(u, v) = c ∈ {r, b}

′

′

(u, v) ∈ E, ρ(u, v) = c

′

′

(u, v) 6∈ E, u 6= v

λ(u , v ) = c̄uv
λ(u, v) = λ(u , v ) = g

where c̄ denotes ‘the other colour’, for c ∈ {r, b}, and each converse edge is labelled
by the converse atom, e.g. λ(u, ∞) = p˘u . It is a routine check that this deﬁnes
a consistent atomic network and that every atom labels at least one edge. By
Lemma 17, (S, E,˘, C) has a feeble representation.
For the converse, suppose the complex algebra over (S, E,˘, C) has a feeble representation, by Lemma 17 there is a consistent, atomic network (N, λ) witnessing
all atoms. We must show that G is a yes instance of the monochromatic triangle
problem.
By forbidden triple II we have that for any x, y, z ∈ N either none or exactly two of {λ(x, y), λ(x, z), λ(y, z)} equal ×. It follows that the set of pairs
{(x, y) : x, y ∈ N, λ(x, y) = ×} forms a complete bipartite graph with nodes N .
So N is the disjoint union N1 ∪ N2 , say, and λ(x, y) = × iﬀ either x ∈ N1 , y ∈ N2
or x ∈ N2 , y ∈ N1 .
Since all atoms are witnessed there are nodes z, x ∈ N such that λ(z, x) = pu ,
without loss z, x ∈ N1 . By forbidden triple III, for every y ∈ N1 \ {z} the label
λ(z, y) belongs to S∞G , so it is pv or qv for some v ∈ V , but it cannot be qv by

24

ROBIN HIRSCH, MARCEL JACKSON, AND TOMASZ KOWALSKI

forbidden triple VI. By forbidden triples IV and V,
 ′
if u = v
 1
cuv if (u, v) ∈ E, for some c ∈ {r, b}
λ(x, y) =

g
otherwise

Hence the map ∗ : N1 \ {z} → V which maps y ∈ N1 \ {z} to v ∈ V iﬀ λ(z, y) = pv
is a well-deﬁned injection. Since each atom pv is witnessed in the network ∗ is
surjective, hence a bijection from N1 onto V . Deﬁne a function ρ : E → {r, b} by
letting ρ(u∗ , v ∗ ) = c if λ(u, v) = cuv , for c ∈ {r, b}. Since ruv˘ = rvu and buv˘ = bvu
this colouring function is symmetric. By forbidden triple VII, ρ is a valid colouring
of the graph.

7. Axiomatisability

THEOREM 19. If K is a class of algebras containing all strongly representable
relation algebras and contained in the class of all feebly representable non-associative
algebras, then K has no finite axiomatisation in first order logic.
Proof. An n-colouring of a set S is a symmetric function ρ mapping pairs of distinct
elements of S to a set of n colours, avoiding monochromatic triangles. Let n ≥ 3,
let k(n) be the smallest integer such that there is no n-colouring on a set with k(n)
elements (the Ramsey number) and let αn be the atom structure with atoms


k(n)(k(n) − 1)
∪ {ai : 0 < i < n}
{1′ } ∪ ak0 : k <
2
All atoms are self-converse. All triples of atoms are consistent except those of
the form (1′ , x, y) for x 6= y (and Peircean transforms of these) and triples of
′
∗
atoms with the same subscript, i.e. (ai , ai , ai ) for 0 < i < n or (ak0 , ak0 , ak0 ), for
k(n)(k(n)−1)
k, k ′ , k ∗ <
. Let An be the complex algebra of αn (sometimes called a
2
Monk Algebra, see [HH02, Deﬁnition 15.2]). Then An has no feeble representation
distinct
because any atomic network witnessing all atoms has at least k(n)(k(n)−1)
2
edges (one for each atom ak0 ) hence k(n) distinct points, but no such network can
be consistent since there is no n-colouring of a set with
Q this many elements.
Now consider a non-principal ultraproduct α = n∈ω αn /U of the αn , where
U is a non-principal ultraﬁlter over ω. The atoms of α are (up to isomorphism)
{1′ } ∪ {ak0 : k < κ} ∪ {ai : 0 < i < η} where κ, η are inﬁnite ordinals, κ is the nonprincipal ultraproduct of the k(n)s and η is the non-principal ultraproduct of the ns.
All atoms are self converse and the consistent triples of atoms are as in the deﬁnition
of αn . We claim that the complex algebra Cm(α) is a strongly representable relation
algebra. Since RRA is a variety, it suﬃces to prove that every ﬁnitely generated
subalgebra of Cm(α) is representable. For this, observe that an element a ≥ ai + aj ,
for any distinct i, j > 0 is flexible in that a; x ≥ 1 − 1′ for any atom x 6= 1′ . So
a ﬁnite subset S of the elements of A generates a ﬁnite boolean subalgebra of the
boolean part of A, this ﬁnite boolean subalgebra generates (using 1′ , ˘ and ;) a ﬁnite
subalgebra of A and this ﬁnite subalgebra contains at least one ﬂexible atom. It is
known that every relation algebra with a ﬂexible atom is representable [Com84] or
[Mad82, Theorem 5.19], this proves the claim. (For a proof in a more complicated
but similar case, see [HH01a, Theorem 24, Proposition 26, Theorem 27].) Observe
that the ultraproduct Πn∈ω An /U is a subalgebra of the complex algebra of α,
so it is also strongly representable. Thus, none of the algebras An has a feeble

ALGEBRAIC FOUNDATIONS FOR QUALITATIVE CALCULI AND NETWORKS

25

representation so An 6∈ K (for n < ω) but an ultraproduct of them has a strong
representation and is in K. By Loś’ Theorem, K cannot be deﬁned by ﬁnitely many
axioms.

By this theorem, the following classes cannot be deﬁned by ﬁnitely many axioms:
the class of non-associative algebras with feeble representations; with qualitative
representations; with strong representations.
8. Conclusion
Let us review some of the advantages of qualitative representations. For many
applications in knowledge representation, it is natural to express that a certain
relation may be decomposed in a certain way without insisting that such a decomposition must always exist, for example if one asserts that y occurs strictly later
than x, it might be the case that there is a z occurring in between, but not necessarily. In order to model real world applications using relation-like algebras, it is often
necessary to consider a type of representation for our algebras that would be ruled
out if we were to restrict ourselves to strong representations. For relation algebras
such as RCC8 where we may wish to consider disconnected regions and regions with
holes it has been known for some time that strong relation algebra representations
are problematic. So the fact that qualitative representations include along with
strong representations a very wide class of diﬀerent representations, signiﬁcantly
extends our ability to model various situations.
Moreover, if a ﬁnite algebra has a qualitative representation then it has a qualitative representation on a ﬁnite base. This means, in general, that the network
satisfaction problem is much easier for qualitative representations than the corresponding problem for strong representations, although for certain well-known relation algebras the two versions of the problem turn out to be equivalent. We have
seen that several representation problems become computationally much easier in
the context of qualitative representations compared to the corresponding strong
representation problem.
In a subsequent paper we intend to investigate the universal algebra of QRA in
more depth, by providing a recursive (but necessariliy inﬁnite) axiomatisation of
it, by considering complete qualitative representations and by showing that QRA
generates a discriminator variety.
Acknowledgement
The authors wish to thank Dr. Todd Niven for his essential input in the early
development of this work.
References
[All83]

James Allen. Maintaining knowledge about temporal intervals. Communications of the
ACM, 26:832–843, 1983.
[Aristotle, prior analytics] Aristotle. Prior Analytics. English translation available at
http://classics.mit.edu/Aristotle/prior.mb.txt . 350 BCE.
[BW11]
Manuel Bodirsky and Stefan Wöfl. RCC8 is polynomial on networks of bounded
treewidth. Proceeding of the twenty-second international joint conference on Artificial Intelligence, 2: 756–761, 2011.
[CCL+ 15] Juan Chen, Anthony G. Cohn, Dayou Liu, Shengsheng Wang, Jihong Ouyang, and
Qiangyuan Yu. A survey of qualitative spatial representations. The Knowledge Engineering Review, 30:106–136, 1 2015.

26

[Com84]

ROBIN HIRSCH, MARCEL JACKSON, AND TOMASZ KOWALSKI

Stephen D. Comer. Combinatorial aspects of relations. Algebra Universalis, 18:77–94,
1984.
[DWM01] Ivo Düntsch, Hui Wang, and Steve McLoskey. A relation-algebraic approach to the
region connected calculus. Theoretical Computer Science, 255:63–83, 2001.
[GJ79]
Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to
the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1979.
[HH01a] Robin Hirsch and Ian Hodkinson. Relation algebras from cylindric algebras, II. Ann.
Pure. Appl. Logic, 112:267–297, 2001.
[HH01b] Robin Hirsch and Ian Hodkinson. Representability is not decidable for finite relation
algebras. Trans. Amer. Math. Soc., 353:1403–1425, 2001.
[HH02]
Robin Hirsch and Ian Hodkinson. Relation algebras by games. North-Holland. Elsevier
Science, Amsterdam, 2002.
[Hir96]
Robin Hirsch. Relation Algebras of Intervals. Artificial Intelligence Journal, 83:1–29,
1996.
[Hir99]
Robin Hirsch. A relation algebra with undecidable network satisfaction problem. Bulletin of the Interest Group in Pure and Applied Logics, 7(4):547–554, 1999.
[JT51]
Bjarni Jónsson and Alfred Tarski. Boolean algebras with operators I. American Journal
of Mathematics, 73:891–939, 1951.
[KL91]
Henry Kautz and Peter Ladkin. Integrating metric and qualitative temporal reasoning.
AAAI’91, Proceedings of the ninth National conference on AI, 1:241–246, 1991.
[Koz97]
Dexter Kozen. Kleene algebra with tests. ACM Trans. Program. Lang. Syst., 19(3):427–
443, 1997.
[Lee14]
Jae Lee. The complexity of reasoning with relative directions. Frontiers in Artificial
Intelligence and Applications, ECAI: 507–512, 2014.
[Lig05]
Gérard Ligozat. Categorical methods in qualitative reasoning: The case for weak representations. In Spatial Information Theory, International Conference, COSIT 2005,
Ellicottville, NY, USA, September 14-18, 2005, Proceedings, pages 265–282, 2005.
[Lig11]
Gérard Ligozat. Qualitative spatial and temporal reasoning. Wiley-ISTE, 2011.
[LM88]
Peter Ladkin and Roger Maddux. On binary constraint networks. Technical Report
U.88.8, Kestrel Institute, 1988.
[LM94]
Peter Ladkin and Roger Maddux. Constraint problems. Journal of the Association of
Computing Machinery, 41:435–469, 1994.
[LMW]
Domink Lüke, Till Mossakowski and Diedrich Wolter. Qualitative reasoning about
convex relations.
[LR04]
Gérard Ligozat and Jochen Renz. What is a qualitative calculus? A general framework.
In Chengqi Zhang, Hans W. Guesgen, and Wai-Kiang Yeap, editors, PRICAI, volume
3157 of Lecture Notes in Computer Science, pages 53–64. Springer, 2004.
[LW06]
Sanjiang Li and Huaiqing Wang. RCC8 binary constraint network can be consistently
extended. Artificial Intelligence Journal, 170:1–18, 2006.
[Mad82] Roger Maddux. Some varieties containing relation algebras. Trans. Amer. Math. Soc.,
272(2)(2):501–526, 1982.
[Mad90] Roger Maddux. Necessary subalgebras of simple nonintegral semiassociative relation
algebras. Algebra Universalis, 27:544–558, 1990.
[Mad06] Roger Maddux. Relation algebras, volume 150 of Studies in Logic: the Foundations of
Mathematics. Elsevier, 2006.
[McK70] Ralph McKenzie. Representations of integral relation algebras. Michigan Math. J.,
17:279–287, 1970.
[Mei96]
Itay Meiri, Combining qualitative and quantitative constraints in temporal reasoning
Artificial Intelligence Journal, 87:343–385, 1996.
[MSW06] Till Mossakowski, Lutz Schröder, and Stefan Wölfl. A categorical perspective on qualitative constraint calculi. In Qualitative Constraint Calculi: Applications and Integration, pages 28–39, 2006.
[OW08]
Joël Ouaknine and James Worrell. Some recent results in metric temporal logic. In
LNCS, 5215:1–13,2008.
[PKS99] Arun Pujari, Vijaya Kumari and Abdul Sattar. INDu: An Interval and Duration Network. In Advanced topics and artificial intelligence, LNCS, 1747, 1999.

ALGEBRAIC FOUNDATIONS FOR QUALITATIVE CALCULI AND NETWORKS

[RCC92]

27

David A. Randell, Zhan Cui, and Anthony G. Cohn. A spatial logic based on regions
and connection. In Proceedings 3rd International Conference on Knowledge Representation and Reasoning. Morgan Kaufmann, 1992.
[Ren02]
Jochen Renz. The region connected calculus. In “Quantitative Spatial Reasoning with
Toplogical Information”: 41–50, 2002.
[RL05]
Jochen Renz and Gérard Ligozat. Weak composition for qualitative spatial and temporal reasoning. In Proceedings of Constraint Programming, volume 3709 of LNCS, page
534548, 2005.
[Tar41]
Alfred Tarski. On the calculus of relations. Journal of Symbolic Logic, 6:73–89, 1941.
[VKvB89] M Vilain, H Kautz, and P van Beek. Constraint propagation algorithms for temporal
reasoning — a revised report. In D S Weld and J de Kleer, editors, Readings in Qualitative Reasoning about Physical Systems, pages 373–381. Morgan Kaufmann, 1989.
[WHW14] Matthias Westphal, Julien Hué, and Stefan Wölfl. On the scope of qualitative constraint calculi. In KI 2014: Advances in Artificial Intelligence - 37th Annual German
Conference on AI, Stuttgart, Germany, September 22-26, 2014. Proceedings, pages
207–218, 2014.

