Ramiro A. de T. Guerreiro, Andrea S. Hemerly, Yoav Shoham
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: (P1) determining whether the network implies an isa relation between two particular nodes, and (P2) determining all isa relations implied by the network. As is well known, without ROLE edges the time complexity of P1 is O(m), and the time complexity of P2 is O(n3). Unfortunately, the results do not extend naturally to ISAR networks, except in a very restricted case. For general ISAR network we frost give an polynomial algorithm by an easy reduction to proposional Horn theory. As the degree of the polynomial is quite high (O(mn4) for P1, O(mn6 ) for P2), we then develop a more direct algorithm. For both P1 and P2 its complexity is O(n3 + m2). Actually, a finer analysis of the algorithm reveals a complexity of O(nr(log r) + n2r + n3), 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(n3).