Combining OWL ontologies using -Connections

The standardization of the Web Ontology Language (OWL) leaves (at least) two crucial issues for Web-based ontologies unsatisfactorily resolved, namely how to represent and reason with multiple distinct, but linked ontologies, and how to enable effective knowledge reuse and sharing on the Semantic Web.In this paper, we present a solution for these fundamental problems based on -Connections. We aim to use -Connections to provide modelers with suitable means for developing Web ontologies in a modular way and to provide an alternative to the owl:imports construct.With such motivation, we present in this paper a syntactic and semantic extension of the Web Ontology language that covers -Connections of OWL-DL ontologies. We show how to use such an extension as an alternative to the owl:imports construct in many modeling situations. We investigate different combinations of the logics , and for which it is possible to design and implement reasoning algorithms, well-suited for optimization.Finally, we provide support for -Connections in both an ontology editor, SWOOP, and an OWL reasoner, Pellet.     

A combinatorial algorithm for max csp

We consider the problem max csp over multi-valued domains with variables ranging over sets of size s_i?s and constraints involving k_j?k variables. We study two algorithms with approximation ratios A and B, respectively, so we obtain a solution with approximation ratio max(A,B).The first algorithm is based on the linear programming algorithm of Serna, Trevisan, and Xhafa [Proc. 15th Annual Symp. on Theoret. Aspects of Comput. Sci., 1998, pp. 488-498] and gives ratio A which is bounded below by s^1−k. For k=2, our bound in terms of the individual set sizes is the minimum over all constraints involving two variables of , where s₁ and s₂ are the set sizes for the two variables.We then give a simple combinatorial algorithm which has approximation ratio B, with B>A/e. The bound is greater than s^1−k/e in general, and greater than s^1−k(1−(s−1)/2(k−1)) for s?k−1, thus close to the s^1−k linear programming bound for large k. For k=2, the bound is if s=2, 1/2(s−1) if s?3, and in general greater than the minimum of 1/4s₁+1/4s₂ over constraints with set sizes s₁ and s₂, thus within a factor of two of the linear programming bound.For the case of k=2 and s=2 we prove an integrality gap of . This shows that our analysis is tight for any method that uses the linear programming upper bound.