BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-90-1324
       ENTRY:: September 14, 1994
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: On the complexity of monotonic inheritance with roles
        TYPE:: Technical Report
      AUTHOR:: Guerreiro, Ramiro A. de T.
      AUTHOR:: Hemerly, S.
      AUTHOR:: Shoham, Yoav
        DATE:: July 1990
       PAGES:: 9
    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$).
       NOTES:: [Adminitrivia V1/RAM/19940914]
         END:: STAN//CS-TR-90-1324