A normal form for hypergraph-based module extraction for S ROI Q

Abstract

Modularization is an important part of the modular design and maintenance of large scale ontologies. Syntactic locality modules, with their desirable model theoretic properties, play an ever increasing role in the design of algorithms for modularization, partitioning and reasoning tasks such as classi cation. It has been shown that, for the DL EL+, the syntactic locality module extraction problem is equivalent to the reachability problem for hypergraphs. In this paper we investigate and introduce a normal form for the DL SROIQ which allows us to map any SROIQ ontology to an equivalent hypergraph. We then show that standard hyperpath search algorithms can be used to extract modules similar to syntactic locality modules for SROIQ ontologies.

Introduction

The advent of the semantic web presupposes a signi cant increase in the size of ontologies, their distributive nature and the requirement for fast reasoning algorithms. Modularization techniques not only play an increasingly important role in the design and maintenance of large-scale distributed ontologies, but also in the design of algorithms that increase the e ciency of reasoning tasks such as subsumption testing and classi cation [ 11, 1 ].

Extracting minimal modules is computationally expensive and even undecidable for expressive DLs [ 2, 3 ]. Therefore, the use of approximation techniques and heuristics play an important role in the e ective design of algorithms. Syntactic locality [ 2, 3 ], because of its excellent model theoretic properties, has become an ideal heuristic and is widely used in a diverse set of algorithms [ 11, 1, 4 ].

Suntisrivaraporn [ 11 ] showed that, for the DL E L+, ?-locality module extraction is equivalent to the reachability problem in directed hypergraphs. Nortje et al. [ 9, 10 ] extended the reachability problem to include >-locality and introduced bidirectional reachability modules as a subset of ?> modules.

In this paper we introduce a normal form for the DL SROIQ, which allows us to map any SROIQ ontology to an equivalent syntactic locality preserving hypergraph. We show that, given this mapping, the extraction of ?-locality modules is equivalent to the extraction of all B-hyperpaths, >-locality is similar to extracting all F -hyperpaths and ?> modules to that of extracting frontier graphs. These similarities demonstrate a unique relationship between reasoning tasks, based on syntactic locality, for SROIQ ontologies, and standard well studied hypergraph algorithms. 2

Preliminaries

2.1

Hypergraphs Hypergraphs are a generalization of graphs and have been extensively studied since the 1970s as a powerful tool for modelling many problems in Discrete Mathematics. In this paper we adapt the de nitions of hypergraphs and hyperpaths from [ 8, 12 ].

A (directed) hypergraph is a pair H = hV; Ei, where V is a nite set of nodes, E 2V 2V is the set of hyperedges such that for every e = (T (e); H(e)) 2 E, T (e) 6= ;, H(e) 6= ;, and T (e) \ H(e) = ;. A hypergraph H0 = hV0; E0i is a subhypergraph of H if V0 V and E0 E. A hyperedge e is a B-hyperedge if jH(e)j = 1. A B-hypergraph is a hypergraph such that each hyperedge is a B-hyperedge. A hyperedge e is an F-hyperedge if jT (e)j = 1. An F-hypergraph is a hypergraph such that each hyperedge is an F-hyperedge. A BF-hypergraph is a hypergraph for which every edge is either a B- or an F-hyperedge.

Let e = (T (e); H(e)) be a hyperedge in some directed hypergraph H. Then, T (e) is known as the tail of e and H(e) is known as the head of e. Given a directed hypergraph H = (V; E), its symmetric image H is a directed hypergraph de ned as: V(H) = V(H) and E(H) = f(H; T ) j (T; H) 2 E(H)g. We denote by BS(v) = fe 2 E j v 2 H(e)g and F S(v) = fe 2 E j v 2 T (e)g respectively the backward star and forward star of a node v. Let n and m be the number of nodes and hyperedges in a hypergraph H. We de ne the size of H as size(H) = jVj + Pe2E (jT (e)j + jH(e)j).

A simple path Qst from s 2 V(H) to t 2 V(H) in H is a sequence (v1; e1; v2; e2; :::; vk; ek; vk+1) consisting of distinct nodes and hyperedges such that s = v1, t = vk+1 and for every 1 i k, vi 2 T (ei) and vi+1 2 H(ei). If in addition t 2 T (e1) then Qst is a simple cycle. A simple path is cycle free if it does not contain any subpath that is a simple cycle.

A node s is B-connected to itself. If there is a hyperedge e such that all nodes vi 2 T (e) are B-connected to s, then every vj 2 H(e) is B-connected to s. A B-hyperpath from s 2 V(H) to t 2 V(H) is a minimal subhypergraph of H where t is B-connected to s. An F-hyperpath Qst from s 2 V(H) to t 2 V(H) in H is a subhyperpath of H such that Qst is a B-hyperpath from t to s in H. A BFhyperpath from s 2 V(H) to t 2 V(H) in H is a minimal (in the inclusion sense) subhyperpath of H such that it is simultaneously both a B-hyperpath and an Fhyperpath from s to t in H. We note that every hypergraph H can be transformed to a BF-hypergraph H0 by replacing each hyperedge e = (T (e); H(e)) with the two hyperedges e1 = (T (e); fnvg); e2 = (fnvg; H(e)) where nv is a new node. Algorithm 1 (Visiting a hypergraph [ 8 ]) Procedure Bvisit(s,H) Procedure Fvisit(t,H) 1 : for each u 2 V do blabel(u) := f alse; for each u 2 V do f label(u) := f alse; 2 : for each e 2 E do T (e) := 0; for each e 2 E do T (e) := 0; 3 : Q := fsg; blabel(s) := true; Q := ftg; f label(t) := true; 4 : while Q 6= ; do while Q 6= ; do 5 : select and remove u 2 Q; select and remove u 2 Q; 6 : for each e 2 F S(u) do for each e 2 BS(u) do 7 : T (e) := T (e) + 1; H(e) := H(e) + 1; 8 : if T (e) := jT ail(e)jthen if H(e) := jHead(e)jthen 9 : for each v 2 Head(e) do for each v 2 T ail(e) do 10 : if blabel(v) = f alse then if f label(v) = f alse then 11 : blabel(v) = true f label(v) = true 12 : Q := Q [ fvg Q := Q [ fvg

Given some node s, Algorithm 1 can be used to nd all B-connected or Fconnected nodes to s in O(size(H)) time. Here, the set of all B-hyperpaths from s and F-hyperpaths to t are respectively represented by all those nodes n such that blabel(n) = true or f label(n) = true, as well as the edges connecting those nodes.

De nition 1. Given a hypergraph H = (V; E), the frontier graph H0 = (V0; E0; s; t) of H, such that V0 V, E0 E, s; t 2 V, is the maximal (in the inclusion sense) BF -graph in which (1) s and t are the origin and destination nodes, (2) if v 2 V0 then v is B-connected to s, and t is F-connected to v in H0. Algorithm 2 (Frontier graph Extraction Algorithm [ 8 ]) Procedure frontier(H; H0; s; t) 1 : H0 := H; change := true 2 : while change = true do 3 : change = f alse 3 : H0 = Bvisit(s; H0); H0 = F visit(t; H0) 4 : for each v 2 V0 5 : if blabel(v) = f alse or f label(v) = f alse then 6 : change := true 7 : V0 = V0 fvg; E0 = E0 F S(v) BS(v) 8 : if s 62 V0 or t 62 V0 then 9 : H0 := ;; change := f alse;

Algorithm 2 can be used to extract a frontier graph for any source and destination nodes and runs in O(n size(H)) time. 2.2

The DL SROIQ In this section we give a brief introduction to the DL SROIQ [ 5, 7 ] with its syntax and semantics listed in Table 1. NC , NR and NI denote disjoint sets of atomic concept names, atomic roles names and individual names. The set NR includes the universal role. Well-formed formulas are created by combining concepts from the table by using the connectives :; u; t etc.

Given R1 : : : Rn v R, where n > 1 and Ri; R 2 NR, is a role inclusion axiom (RIA). A role hierarchy is a nite set of RIAs. Here R1 : : : Rn denotes a composition of roles where R; Ri may also be an inverse role R . A role R is simple if it: (1) does not appear on the right-hand side of a RIA; (2) is the inverse of a simple role; or (3) appears on the right-hand side of a RIA only if the left-hand side consists entirely of simple roles. Ref (R), Irr(R) and Dis(R; S), where R, S are roles other than U , are role assertions. A set of role assertions is simple w.r.t. a role-hierarchy H if each assertion Irr(R) and Dis(R; S) uses only simple roles w.r.t. H.

A strict partial order on NR is a regular order if, and only if, for all roles R and S: S R i S R. Let be a regular order on roles. A RIA w v R is -regular if, and only if, R 2 NR and w has one of the following forms: (1) R R, (2) R , (3) S1 : : : Sn, where each Si R, (4) R S1 : : : Sn, where each Si R and (5) S1 : : : Sn R, where each Si R. A role hierarchy H is regular if there exists a regular order such that each RIA in H is -regular.

An RBox is a nite, regular role hierarchy H together with a nite set of role assertions simple w.r.t. H. If a1; : : : ; an are in NI , then fa1; : : : ; ang is a nominal. No is the set of all nominals. The set of SROIQ concept descriptions is the smallest set such that: (1) ?,>, each C 2 NC , and each o 2 No is a concept description. (2) If C is a concept description, then :C is a concept description. (3) If C and D are concept descriptions, R is a role description, S is a simple role description, and n is a non-negative integer, then the following are all concept descriptions: (C u D); (C t D); 9R:C; 8R:C; 6 nS:C; > nS:C; 9S:Self .

If C and D are concept description then C v D is a general concept inclusion (GCI) axiom. A TBox is a nite set of GCIs. If C is a concept description, a; B 2 NI , R; S 2 NR with S a simple role description, then C(a), R(a; b), :S(a; b), and a 6= b, are individual assertions. An SROIQ ABox is a nite set of individual assertions. All GCIs, RIAs, role assertions, and individual assertions are referred to as axioms. A SROIQ-KB base is the union of a TBox, RBox and ABox.

De nition 2 is su ciently general so that any subset of an ontology preserving a statement of interest is considered a module, the entire ontology is therefore a module in itself. An important property of modules in terms of the modular reuse of ontologies is safety [ 2, 3 ]. Intuitively, a module conforms to a safety condition whenever an ontology T reuses concepts from an ontology T 0 in such a way so that it does not change the meaning of any of the concepts in T 0. This may be formalized in terms of the notion of conservative extensions: De nition 3. (Conservative extension [ 3 ]) Let T and T1 be two ontologies such that T1 T , and let S be a signature. Then (1) T is an S-conservative extension of T1 if, for every with Sig( ) S, we have T j= i T1 j= . (2) T is a conservative extension of T1 if T is an S-conservative extension of T1 for S = Sig(T1).

De nition 4. (Safety [ 3, 6 ]) An ontology T is safe for T 0 if T [ T 0 is a conservative extension of T 0. Further let S be a signature. We say that T is safe for S if, for every ontology T 0 with Sig(T ) \ Sig(T 0) S, we have that T [ T 0 is a conservative extension of T 0.

Intuitively, given a set of terms, or seed signature, S, a S-module M based on deductive-conservative extensions is a minimal subset of an ontology O such that for all axioms with terms only from S, we have that M j= if, and only if, O j= , i.e., O and M have the same entailments over S. Besides safety, reuse of modules requires two additional properties namely coverage and independence. De nition 5. (Module coverage [ 6 ]) Let S be a signature and T 0, T be ontologies with T 0 T such that S Sig(T 0). Then, T 0 guarantees coverage of S if T 0 is a module for S in T .

De nition 6. (Module Independence [ 6 ]) Given an ontology T and signatures S1, S2, we say that T guarantees module independence if, for all T1 with Sig(T ) \ Sig(T1) S1, it holds that T [ T1 is safe for S2.

Unfortunately, deciding whether or not a set of axioms is a minimal module is computationally hard or even impossible for expressive DLs [ 2, 3 ]. However, if the minimality requirement is dropped, good sized approximations can be de ned that are e ciently computable, as in the case of syntactic locality, which modules are extracted in polynomial time.

Algorithm 3 (Extract a locality module [ 2 ]) Procedure extract-module(T ; S; x) Inputs: Tbox T ; signature S; x 2 ?; >; Output x-module M 1 : M := ;; T 0 = T ; 2 : repeat 3 : change = f alse 4 : for each 2 T 0 5 : if not x-local w.r.t. S[Sig(M) then 6 : M = M + f g 7 : T 0 = T 0 n f g 8 : changed = true 9 : until changed = f alse De nition 7. (Syntactic locality [ 3 ]) Let S be a signature and O a SROIQ ontology. An axiom is ?-local w.r.t. S (>-local w.r.t S) if 2 Ax(S), as de ned in the grammar: ?-Locality Ax(S) ::= C? v CjC v C>jw? v RjDis(S?; S)jDis(S; S?) Con?(S) ::= A?j:C>jC? u CjC u C?jC1? t C2?j9R?:Cj9R:C?

j9R?:Self j > nR?:Cj > nR:C? Con>(S) ::= :C?jC1> u C2>jC> t CjC t C>j8R:C>j 6 nR:C>

j8R?:Cj 6 nR?:C >-Locality Ax(S) ::= C? v CjC v C>jw v R> Con?(S) ::= :C>jC? u CjC u C?jC1? t C2?j9R:C?j > nR:C?

j8R>:C?j 6 nR>:C? Con>(S) ::= A>j:C?jC1> u C2>jC> t CjC t C>j8R:C>j

9R>:C>j > nR>:C>j 6 nR:C>j8R?:Cj 6 nR?:C In the grammar, we have that A?; A> 62 S is an atomic concept, R?; R> (resp. S?,S>) is either an atomic role (resp. a simple atomic role) not in S or the inverse of an atomic role (resp. of a simple atomic role) not in S, C is any concept, R is any role, S is any simple role, and C? 2 Con?(S), C> 2 Con>(S). We also denote by w? a role chain w = R1 : : : Rn such that for some i with 1 i n, we have that Ri is (possibly inverse of ) an atomic role not in S. An ontology O is ?-local (>-local) w.r.t. S if is ?-local (>-local) w.r.t. S for all 2 O.

Algorithm 3 may be used to extract either >- or ?-locality modules. Alternating the algorithm between ?- and >-locality module extraction until a xed-point is reached results in ?> modules. 3

Normal form

In this section we will introduce a normal form for any SROIQ ontology. The normal form is required to facilitate the conversion process between a SROIQ ontology and a hypergraph.

De nition 8. Given Bi 2 NC n f?g, Ci 2 NC n f>g, D 2 f9R:B; nR:B; 9R:Self g, Ri; Si 2 NR and n > 1, a SROIQ ontology O is in normal form if every axiom 2 O is in one of the following forms: 1: B1 u : : : u Bn v C1 t : : : t Cm 2: 9R:B1 v C1 t : : : t Cm 3: B1 u : : : u Bn v 9R:Bn+1 4: B1 u : : : u Bn v 9R:Self 5: 9R:Self v C1 t : : : t Cm 6: > nR:B1 v C1 t : : : t Cm 7: B1 u : : : u Bn v> nR:Bn+1 8: R1 : : : Rn v Rn+1 9: D1 v D2

In order to normalize a SROIQ ontology O we repeatedly apply the normalization rules from Table 2. Each application of a rule rewrites an axiom into an equivalent normal form. Algorithm 4 illustrates the conversion process. Algorithm 4 Given any SROIQ axiom 1. Recursively apply rules NR7 - NR11 to eliminate all equivalences, universal restrictions, atmost restrictions and complex role llers. 2. Given that = ( L v R), recursively apply the following steps until L contains no disjunctions and R contains no conjunctions: (a) recursively apply rules NR1, NR3, NR6 to L, (b) recursively apply rules NR2, NR4, NR5 to R. 3. recursively apply any applicable rules from NR12 through NR21.

Theorem 1. Algorithm 4 converts any SROIQ ontology O to an ontology O0 in normal form, such that O0 is a conservative extension of O. The algorithm terminates in linear time and adds at most a linear number of axioms to O.

For every normalized ontology O0 the de nition of syntactic locality from De nition 7 may now be simpli ed to that of De nition 9. This is possible since for every axiom = ( L v R) 2 O0, ?-locality of is dependent solely on L and >-locality is dependent solely on R. De nition 9. (Normal form syntactic locality) Let S be a signature and O a normalized SROIQ ontology. Any axiom is ?-local w.r.t. S (>-local w.r.t S) if 2 Ax(S), as de ned in the grammar: ?-Locality Ax(S) ::= C? v C j w? v R j Dis(S?; S) j Dis(S; S?) Con?(S) ::= A? j C?u j C u C? j 9R?:C j 9R:C? j 9R?:Self j > nR?:C j> nR:C? >-Locality Ax(S) ::= C v C> j w v R> Con>(S) ::= A> j C> t C j C t C>j9R>:C> j> nR>:C> j

9R>:Self In the grammar, we have that A?; A> 62 S is an atomic concept, R?,R> (resp. S?,S>) is either an atomic role (resp. a simple atomic role) not in S or the inverse of an atomic role (resp. of a simple atomic role) not in S, C is any concept, R is any role, S is any simple role, and C? 2 Con?(S), C> 2 Con>(S). We also denote by w? a role chain w = R1 : : : Rn such that for some i with 1 i n, we have that Ri is (possibly inverse of ) an atomic role not in S. An ontology O is ?-local(>-local) w.r.t. S if is ?-local(>-local) w.r.t. S for all 2 O.

We note that we may denormalize a normalized ontology if we maintain a possibly many-to-many mapping from normalized axioms to their original source axioms. Formally, de ne a function denorm : O^ ! 2O, with O an SROIQ ontology and O^ its normal form. For brevity, we write denorm( ), with a set of normalized axioms, to denote S denorm( ).

2 4

SROI Q hypergraph Suntisrivaraporn [ 11 ] showed that for the DL E L+, extracting ?-locality modules are equivalent to the reachability problem in directed hypergraphs. This was extended in [ 9, 10 ] to include a reachability algorithm for >-locality modules. In this section we show that a SROIQ ontology O in normal form can be mapped to a hypergraph which preserves both ?-locality and >-locality. De nition 10. Let be a normalized axiom and ? a minimum set of symbols from Sig( ) required to ensure that is not ?-local, and let H = (V; E ) be a hypergraph. We say that an edge e 2 E preserves ?-locality i ? = T (e). Similarly, e 2 E preserves >-locality whenever > = H(e).

For each normal form axiom i in De nition 8 we show that i may be mapped to a set of hyperedges, with nodes denoting symbols from Sig( i), such that both ?-locality and >-locality are simultaneously preserved. { Given 1 : B1 u : : : u Bn v C1 t : : : t Cm we map it to the hyperedge e 1 = (fB1; : : : ; Bng; fC1; : : : ; Cmg). We transform the hyperedge e 1 to two new hyperedges eB1 = (fB1; : : : ; Bng; fH1g) a B-hyperedge, eF1 = (fH1g; fC1; : : : ; Cmg) an F-hyperedge and with H1 a new node. By de nition each Cj is B-connected to H1 if all Bi are B-connected to H1. From De nition 9 we know that this preserves ?-locality for 1 since it is ?-local, w.r.t. a signature S, exactly when any of the conjuncts Bi 62 S. In other words it is non ?-local exactly when all Bi 2 S. The same also holds for >locality, since eF1 requires every Ci 2 1 to be in S for H1 to be F-connected. From De nition 9 we see that, w.r.t. a signature S, eF1 is >-local exactly when any of the disjuncts Ci 62 S. { Given 2 : 9R:B1 v C1 t : : : t Cm or 6 : > nR:B1 v C1 t : : : t Cm we map it to the two hyperedges eB2=6 = (fB1; Rg; fH2g), eF2=6 = (fH2g; fC1; : : : ; Cmg) an F-hyperedge and with H2 a new node. This mapping preserves ?-locality for 2=6 since by De nition 9 it is ?-local, w.r.t. a signature S, exactly when either B1 or R is not in S. The argument for >-locality follows that of 1. { Given 3 : B1 u : : : u Bn v 9R:Bn+1 or 7 : B1 u : : : u Bn v> nR:Bn+1 we map it to the hyperedges eB3=7 = (fB1; B2; : : : ; Bn 1; Bng; fH3g), eF13=7 = (fH3g; fBn+1g), eF23=7 = (fH3g; fRg). This mapping preserves ?-locality for 3=7 similarly to eB1 for 1. From De nition 9 we know that >-locality for either of these axioms, w.r.t. a signature S, is dependent on neither R nor Bn+1 being elements of S. Therefore, they are non >-local exactly when either or both of these are in S. This is represented by the two edges eF13=7 and eF23=7 for which H3 becomes F-connected exactly when either R or Bn+1 is F-connected. { Given 4 : B1 u : : : u Bn v 9R:Self and 5 : 9R:Self v C1 t : : : t Cm we see that 9R:Self is both ? or > local exactly when R 62 S. Therefore we map 4 to the hyperedge eB4 = (fRg; fC1; : : : ; Cmg), and 5 to the hyperedge eF5 = (fB1; : : : ; Bng; fRg). { Given 8 : R1 : : : Rn v Rn+1, we see that 8 is ?-local exactly when any to the hypernedagnedeiBs8 >=-l(ofcRal1;e:x:a:c;tRlyngw;hfeRnn+R1ng+)1. 62 S. We therefore map 8 Ri 62 S; i { For 9 we have many forms, all variants of those discussed in the previous mappings. Therefore 9 is mapped to any of the following: eB91 = (fR; B1g; fH9gg), eF19 = (fH9g; fRg), eF29 = (fH9g; fBg), or e1 9 = (fR; B1g; fRg), or eF19 = (fR1g; fR2g), eF29 = (fR1g; fBg), or e1 9 = (fR1g; fR2g).

Given a SROIQ ontology O in normal form we may now map every axiom 2 O to its equivalent set of hyperedges. For each of these mappings there are at most three hyperedges introduced, therefore mapping the whole ontology O to an equivalent hypergraph HO will result in a hypergraph with the number of edges at most linear in the number of axioms in O. It is easy to show that the mapping process can be completed in linear time in the number of axioms in O.

We note that, similar to the normalization process, we may maintain a possibly many-to-many mapping from normalized axioms to their associated hyperedges. Formally, de ne a function deedge : HO ! 2O, with O a SROIQ ontology and HO its hypergraph. For brevity, we write deedge( ), with a set of hyperedges, to denote Se2 deedge(e).

Hypergraph module extraction

In this section we show that, given a hypergraph HO for a SROIQ ontology O, we may extract a frontier graph from HO which is a subset of a ?> module. We show that some of these modules guarantee safety, module coverage and module independence. The hypergraph algorithms presented require one start node s and a destination node t. In order to extend these algorithms to work with an arbitrary signature S, we introduce a new node s with with an edge esi = (s; si) for each si 2 S [ >, as well as a new node t with an edge eti = (si; t) for each si 2 S [ ?.

Theorem 2. Let O be a SROIQ ontology and HO its associated hypergraph B and S a signature. Algorithm 1 - Bvisit extracts a set of B-hyperpaths HO corresponding to the ?-locality module for S in O. Therefore, these modules also guarantees safety, module coverage and module independence.

Theorem 3. Let O be a SROIQ ontology and HO its associated hypergraph F and S a signature. Algorithm 1 - F visit extracts a set of F -hyperpaths HO corresponding to a subset of the >-locality module for S in O.

Theorem 4. Let O be a SROIQ ontology and HO its associated hypergraph BF corresponding to and S a signature. Algorithm 2 extracts a frontier graph HO a subset of the ?> -locality module for S in O.

The module extracted in Theorem 3 is a subset of the >-locality module for a given seed signature. It is as yet unclear whether or not these modules provide all the model-theoretic properties associated with >-locality modules. However, from the previous work done for the DL E L+ [ 10 ], it is evident that these modules preserve all entailments for a given seed signature S. Further, they also preserve and contain all justi cations for any given entailment. Similarly, the exact module theoretic properties of modules associated with frontier graphs is something we are currently looking into. 6

Conclusion

We have introduced a normal form for any SROIQ ontology, as well as the necessary algorithms in order to map any SROIQ ontology to a syntactic locality preserving hypergraph. This mapping process can be accomplished in linear time in the number of axioms with at most a linear increase in the number of hyperedges in the hypergraph.

Standard path searching algorithms for hypergraphs may now be used to nd: (1) sets of B-hyperpaths | this is equivalent to nding ?-syntactical locality modules; (2) sets of F -hyperpaths | these are subsets of >-locality modules, and (3) frontier graphs | these are subsets of ?> modules. Whilst the modules associated with B-hyperpaths share all the module theoretic properties of ?locality modules, it is unclear at this point which module-theoretic properties modules associated with F -hyperpaths and frontier graphs possess.

The ability to map SROIQ ontologies to hypergraphs, such that hyperedges preserve syntactic locality conditions, allows us to investigate the relationship between DL reasoning algorithms and the vast body of standard hypergraph algorithms in greater depth.

Our primary focus for future research is to investigate and de ne the moduletheoretic properties of modules associated with F -hyperpaths and frontier graphs as well as their relative performance with respect to existing locality methods. Thereafter, we aim to expand our research and investigate other hypergraph algorithms and how they may be applied to DL reasoning problems.

References

1. Cuenca Grau , B. , Halaschek-Wiener , C. , Kazakov , Y. , Suntisrivaraporn , B. : Incremental classi cation of description logic ontologies . Tech. rep. ( 2012 )

2. Cuenca Grau , B. , Horrocks , I. , Kazakov , Y. , Sattler , U. : Just the right amount: extracting modules from ontologies . In: Williamson, C. , Zurko , M. (eds.) Proceedings of the 16th International Conference on World Wide Web (WWW '07) . pp. 717 { 726 . ACM , New York, NY, USA ( 2007 )

3. Cuenca Grau , B. , Horrocks , I. , Kazakov , Y. , Sattler , U. : Modular reuse of ontologies: Theory and practice . Journal of Arti cial Intelligence Research (JAIR) 31 , 273 { 318 ( 2008 )

4. Del Vescovo , C. , Parsia , B. , Sattler , U. , Schneider , T. : The modular structure of an ontology: atomic decomposition and module count . In: O. Kutz , T.S. (ed.) Proc. of WoMO-11. Frontiers in AI and Appl. , vol. 230 , pp. 25 { 39 . IOS Press ( 2011 )

5. Horrocks , I. , Kutz , O. , Sattler , U. : The even more irresistable SROIQ . In: Doherty, P. , Mylopoulos , J. , Welty , C. (eds.) Proceedings of the Tenth International Conference on Princleples of Knowledge Representation and Reasoning . pp. 57 { 67 . AAAI Press ( 2006 )

6. Jimenez-Ruiz , E. , Cuenca Grau , B. , Sattler , U. , Schneider , T. , Berlanga , R.: Safe and economic re-use of ontologies: A logic-based methodology and tool support . In: Proceedings of ESWC-08 . vol. 5021 of LNCS, pp. 185 { 199 ( 2008 )

7. Maier , F. , Ma , Y. , Hitzler , P. : Paraconsistent OWL and related logics . In: Janowicz, K . (ed.) Semantic Web 2012 . pp. 1 { 33 . IOS Press ( 2012 )

8. Nguyen , S. , Pretolani , D. , Markenzon , L. : On some path problems on oriented hypergraphs . Theoretical Informatics and Applications 32 ( 1-2 -3), 1 { 20 ( 1998 )

9. Nortje , R.: Module extraction for inexpressive description logics . Master's thesis , University of South Africa ( 2011 )

10. Nortje , R. , Britz , K. , Meyer, T.: Bidirectional reachability-based modules . In: Proceedings of the 2011 International Workshop on Description Logics (DL2011) . CEUR Workshop Proceedings , CEUR-WS ( 2011 ), http://ceur-ws.org/

11. Suntisrivaraporn , B. : Polynomial-Time Reasoning Support for Design and Maintenance of Large-Scale Biomedical Ontologies . Ph.D. thesis , Technical University of Dresden ( 2009 )

12. Thakur , M. , Tripathi , R.: Complexity of linear connectivity problems in directed hypergraphs . Linear Connectivity Conference pp. 1 { 12 ( 2001 )