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$).
http://i.stanford.edu/pub/cstr/reports/cs/tr/90/1324/CS-TR-90-1324.pdf