Report Number: CS-TR-90-1324
Institution: Stanford University, Department of Computer Science
Title: On the complexity of monotonic inheritance with roles
Author: Guerreiro, Ramiro A. de T.
Author: Hemerly, S.
Author: Shoham, Yoav
Date: July 1990
Abstract: We investigate the complexity of reasoning with monotonic
inheritance hierarchies that contain, beside ISA edges, also
ROLE (or FUNCTION) edges. A ROLE edge is an edge labelled
with a name such as spouse of or brother of. We call such
networks ISAR networks. Given a network with n vertices and m
edges, we consider two problems: ($P_1$) determining whether
the network implies an isa relation between two particular
nodes, and ($P_2$) determining all isa relations implied by
the network. As is well known, without ROLE edges the time
complexity of $P_1$, is O(m), and the time complexity of
$P_2$ is O($n^3$). Unfortunately, the results do not extend
naturally to ISAR networks, except in a very restricted case.
For general ISAR network we first give an polynomial
algorithm by an easy reduction to proposional Horn theory. As
the degree of the polynomial is quite high (O(m$n^4$) for
$P_1$, O(m$n^6$) for $P_2$), we then develop a more direct
algorithm. For both $P_1$ and $P_2$ its complexity is O($n^3
+ m^2$). Actually, a finer analysis of the algorithm reveals
a complexity of O(nr(log r) + $n^2$r+ $n^3), where r is the
number of different ROLE labels. One corolary is that if we
fix the number of ROLE labels, the complexity of our
algorithm drops back to O($n^3$).