FREE ELECTRONIC LIBRARY - Abstracts, online materials

Pages:     | 1 ||

«Paraconsistent Reasoning for Expressive and Tractable Description Logics Yue Ma1, Pascal Hitzler2, and Zuoquan Lin1 Department of Information ...»

-- [ Page 2 ] --

– If C =≥ nR.D for D a concept and R a role, then π(C) =≥ nR.π(D);

– If C =≤ nR.D for D a concept and R a role, then π(C) =≤ nR.¬π(¬D);

– If C = ¬(≥ nR.D) for D a concept and R a role, then π(C) = nR.¬π(¬D);

– If C = ¬(≤ nR.D) for D a concept and R a role, then π(C) = nR.π(D);

Regarding both the extension of number restrictions and of nominals, the following theorem holds, which lays the theoretical foundation for the algorithm of four-valued semantics for expressive DLs.

Theorem 5 (Theorem 1 extended) For any ontology O in SHIQ, O is 4-valued unsatisfiable if and only if π(O) is unsatisfiable under the classical semantics of SHIQ.

4 Tractable DLs In this section, we will see that inconsistencies are also unavoidable in many tractable DLs. So we focus on discussing whether the four-valued semantics can preserve the tractability of these tractable DLs. That is, whether the reduction for computing the four-valued semantics transfers tractable DLs still into tractable DLs. If it does, then we can use the four-valued semantics to deal with inconsistency without having to worry about intractability. Our discussion is based on EL++, Horn-DLs, and DL-Lite.

4.1 EL++

We do not consider concrete domains. The syntax definition of EL++ knowledge bases is shown in Table 4. EL++ ontologies may also contain role inclusions (RI) of the form r1 ◦ · · · ◦ rk r, where ◦ denotes role composition.

It is easy to see that an EL++ knowledge base may be inconsistent if we consider the knowledge base {A ⊥, A(a)}. So we still hope that the 4-valued semantics can help us to handle inconsistency in EL++ knowledge bases. However, we will see that we don’t have as many choices of class inclusion as in ALC and SHIQ if we want to maintain the tractability of the 4-valued entailment relationship of EL++. The analysis is as follows.

Obviously, the concept transformation of Definition 1 performing on an EL++ concept produces an EL++ concept. For the transformation of internal inclusion, each EL++ axiom C D is transformed into π(C) π(D) where π(C) and π(D) are still EL++ concepts, so that π(C) π(D) is still an EL++ axiom. So internal class inclusion does not destroy the tractability of EL++. This property does not hold

for material and strong class inclusions as shown by the following counterexamples:

A A → B and A A → B. They will be transformed into ¬(A− A − ) B+ + + + − − − and {A A B,B (A A )} by Definition 2, which are not within the expressivity of EL++. This is mainly because of no negative constructor in EL++.

For role inclusions in EL++, since there is no negative role constructor which can cause inconsistency, we only need to use the classical interpretation for roles as what we do for ALC. So adaptation of 4-valued semantics does not effect the role inclusions axioms.

4.2 Horn-DLs We ground our discussion on Horn-SHOIQ◦ as defined in [7]. Then we will point out that the same conclusion holds for other Horn-DLs, like Horn-SHIQ [10], which has Table 4. EL++ and Horn-SHOIQ◦. The Horn-SHOIQ◦ normal form used is due to [7].

–  –  –

tractable data complexity [6]. We define Horn-SHOIQ◦ by means of a normal form given in [7], which can be found in Table 4 where A, A, B are concept names.

We can see that all of the Horn-SHOIQ◦ concept constructors preserve its form under π(·) operator except ≤ 1R.B, because π(≤ 1R.B) =≤ 1R.¬B − according to Definition 4. To still maintain the concept structure of ≤ 1R.B within Horn-SHOIQ◦, we redefine the π(·) operator on ≤ 1R.C as

π(≤ 1R.C) = {≤ 1R.C = }, where C = C− ⊥.

Then π(A ≤ 1R.C) = {A ≤ 1R.C =, C = C − ⊥} by the transformation definition of internal inclusion axiom.

However, not all of the axiom transformations in Definition 2 preserve the structures of Horn-DL axioms. As the analysis in last paragraph, internal inclusion preserves Horn-ness. As counterexamples for material inclusion and strong inclusion, just consider again the counterexample used in EL++ case. The transformed forms ¬(A− A −) B + and {A+ A + B+, B− (A− A − )} are not within the expressivity of Horn-SHOIQ◦. Since A A B is allowed in other Horn-DLs, the same conclusion as for Horn-SHOIQ◦ holds. This means that when we want ro preserve the structure of tractable Horn-DLs, we have to choose internal inclusion as the only inclusion form to perform paraconsistent reasoning.

4.3 DL-Lite DL-Lite family includes DL-Litecore, DL-LiteF, and DL-LiteR. The logics of DL-Lite family are the maximal DLs supporting efficient query answering over large amounts of instances. In [3], the usual DL reasoning tasks on DL-Lite family are shown to be polynomial in the size of the TBox, and query answering is LOGSPACE in the size of the ABox. Moreover, DL-Lite family allows for separation between TBox and ABox reasoning during query evaluation: the part of the process requiring TBox reasoning is independent of the ABox, and the part of the process requiring to the ABox can be carried out by an SQL engine [3].

Concepts and roles of DL-Lite family are formed by the following syntax [3]:

–  –  –

It is also easy to construct an inconsistent knowledge base even for DL-Litecore. For instance, KB = {B ¬A, B(a), A(a)}. Moreover, conflictions about roles possibly occur on DL-LiteR, such as {P P, P ¬P, P (a, b)}.

In order to still adopt 4-valued semantics for DL-Lite family, we define the fourvalued semantics extension for roles. Just as the four-valued semantics for concepts, a pair RP, RN (RP, RN ⊆ (∆I )2 ) denotes the four-valued semantics of a role R under interpretation I, where RP stands for the set of pairs of individuals which are related via R and RN explicitly represents the set of pairs of individuals which are not related via R. Table 6 gives the formal definition.

–  –  –

necessary to hold under four-valued semantics. This also the key point why our fourvalued semantics can tolerant conflicts caused by role assertions, by allowing a, b both positively related and negatively related via R under a four-valued interpretation I. We give the following example to illustrate the four-valued semantics of ∃R.

Example 2 Note that the ontology O = {∃hasStud(Green), ¬∃hasStud(Green)} is inconsistent.

Consider the following 4-interpretation I = (∆I, ·I ), where ∆I = {a, b, Green}:

hasStudI = {(Green, a)}, {(Green, a), (Green, b), (Green, Green)} which says that we know that Green has a student a, and that Green doesn’t relate any of the individuals via the relation hasStudent. By checking the following formulae

we know that I is a 4-model of O:

–  –  –

Intuitively, this 4-model reflects the contradictory status of the ontology about whether Green has a student.

Now we turn to define the concept transformations for DL-Lite.

Definition 5 The concept and role transformations for DL-Lite concepts are dened on structure induction as follows.

– For E = R, then π(E) = R;

– For E = ¬R, then π(E) = R, where R is a new role;

– If C = ∃R, then π(C) = ∃R;

If C = ¬∃R, then π(C) = ¬∃R=, where R= is a new role name and R= – ¬R.

Consider the internal inclusion transformation, we have all the GCIs B C of DL-Lite will be transferred into form B C with at most an additional role inclu¬∃R=, R= sion because π(B ¬∃R) = {B ¬R }. For material inclusion and strong inclusion, because the negative concept is not allowed to occur on the left of a GCI, they do not preserve the DL-Lite structure. So only internal inclusion works under the reduction from four-valued semantics to classical semantics of DL-Lite family to keep tractability. We can see that the four-valued semantics of DL-Lites family can be reduced to the reasoning of classical DL-LiteR. The following theorem shows this.

Theorem 6 For any DL-Lite ontology O, O is 4-valued unsatisfiable if and only if π(O) is unsatisfiable under the classical semantics of DL-LiteR.

5 Conclusions In this paper, we further studied the four-valued semantics for description logics, specially for expressive DLs and tractable DLs. We formally defined their four-valued semantics and proper reductions to classical semantics, such that all the benefits from existing reasoners on these DLs can also be achieved by invoking classical reasoners after employing these reduction algorithms in a preprocessing manner. And the size of obtained ontology is linear as the size of original ontology. Unlike the four-valued semantics for ALC and SHIQ, we showed that in order to preserve the tractability of tractable DLs, only internal class inclusion among the three class inclusion forms is suitable to model class inclusion. Intuitively, this is because that the semantics of material and strong class inclusions needs the ability to represent negation in some complex form, which is not within the expressivity of tractable DLs. In the future, we will implement these extensions on our existing prototype ParOWL1 to support paraconsistent inconsistency handling on these DLs.


1. N. D. Belnap. How a computer should think. Comtemporary Aspects of Philosophy: Proceedings of the Oxford International Symposium, pages 30–56, 1977.

2. N. D. Belnap. A useful four-valued logic. Modern uses of multiple-valued logics, pages 7–73, 1977.

3. Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati. Tractable reasoning and efficient query answering in description logics: The l-lite family. J. Autom. Reasoning, 39(3):385–429, 2007.

4. Peter Haase, Frank van Harmelen, Zhisheng Huang, Heiner Stuckenschmidt, and York Sure.

A framework for handling inconsistency in changing ontologies. In Yolanda Gil, Enrico Motta, V. Richard Benjamins, and Mark A. Musen, editors, International Semantic Web Conference, volume 3729 of Lecture Notes in Computer Science, pages 353–367. Springer, 2005.

5. Zhisheng Huang, Frank van Harmelen, and Annette ten Teije. Reasoning with inconsistent ontologies. In Leslie Pack Kaelbling and Alessandro Saffiotti, editors, IJCAI, pages 454–

459. Professional Book Center, 2005.

6. Ullrich Hustadt, Boris Motik, and Ulrike Sattler. Data Complexity of Reasoning in Very Expressive Description Logics. In Proc. of the 19th Int. Joint Conference on Artificial Intelligence (IJCAI 2005), pages 466–471, Edinburgh, UK, July 30 – August 5 2005. Morgan Kaufmann Publishers.

7. Markus Kr¨ tzsch, Sebastian Rudolph, and Pascal Hitzler. Complexity boundaries for Horn o description logics. In AAAI, pages 452–457. AAAI Press, 2007.

8. Yue Ma, Pascal Hitzler, and Zuoquan Lin. Algorithms for paraconsistent reasoning with owl. In Enrico Franconi, Michael Kifer, and Wolfgang May, editors, ESWC, volume 4519 of Lecture Notes in Computer Science, pages 399–413. Springer, 2007.

9. Yue Ma, Guilin Qi, Pascal Hitzler, and Zuoquan Lin. Measuring inconsistency for description logics based on paraconsistent semantics. In Khaled Mellouli, editor, ECSQARU, volume 4724 of Lecture Notes in Computer Science, pages 30–41. Springer, 2007.

10. Boris Motik. Reasoning in description logics using resolution and deductive databases. PhD theis, University Karlsruhe, Germany, 2006.

11. Peter F. Patel-Schneider. A four-valued semantics for terminological logics. Artificial Intelligence, 38:319–351, 1989.

12. Peter F. Patel-Schneider and Horrocks Ian. OWL web ontology language semantics and


syntax. W3C Recommendation, 10 February, 2004.

13. Peter F. Patel-Schneider and Horrocks Ian. OWL 1.1 web ontology language overview. W3C Member Submssion, 19 December, 2006.

14. Stefan Schlobach and Ronald Cornet. Non-standard reasoning services for the debugging of description logic terminologies. In Georg Gottlob and Toby Walsh, editors, IJCAI, pages 355–362. Morgan Kaufmann, 2003.

15. Umberto Straccia. A sequent calculus for reasoning in four-valued description logics. In Didier Galmiche, editor, TABLEAUX, volume 1227 of Lecture Notes in Computer Science, pages 343–357. Springer, 1997.

Pages:     | 1 ||

Similar works:

«Carmel Valley Village Improvement Committee P.O. Box 2001 Carmel Valley, C A 93924 2014-2015 CV VIC Calendar Board Meetings are held at Village restaurants, usually on the first Thursday of each month (depending on holidays). General Membership Meetings are held quarterly on the second Friday of the last month of each quarter and include lunch and a speaker or program of interest. Visit cvvic.org for details. Monthly Board Meetings Quarterly General Meetings 1st (or 2nd) Thursday at Noon 2nd...»

«89 Fifth Avenue, 7th Floor New York, NY 10003 www.TheEdison.com @EdisonGroupInc 212.367.7400 White Paper Trading Smarter: How GPUs Improve Data Analytics and High Performance Computing in Financial Services Printed in the United States of America Copyright 2015 Edison Group, Inc. New York. Edison Group offers no warranty either expressed or implied on the information contained herein and shall be held harmless for errors resulting from its use. All products are trademarks of their respective...»

«LA EQUIDAD SOCIAL COMO EJE TRANSVERSAL EN LAS POLÍTICAS DE MOVILIDAD URBANA Lic. Dayana Mesa Martínez Socióloga, Universidad Central “Marta Abreu” de Las Villas, Cuba dmmartinez@uclv.edu.cu Msc. Darmis Machado Machado Socióloga, Universidad Central “Marta Abreu” de Las Villas, Cuba darmis@uclv.edu.cu RESUMEN Las políticas sociales juegan un papel protagonista en la generación de procesos de equidad social, como mecanismos de redistribución de riquezas, instrumento para cambiar la...»

«Policy on Philanthropic Donations and non-commercial Sponsorship 1/10 Content THE ROCHE APPROACH 1. SCOPE 2. GUIDING PRINCIPLES FOR PHILANTHROPIC DONATIONS AND NON-COMMERCIAL SPONSORSHIP. 4 3. 3.1 EMPHASIS ON IMPACT 3.2 COMMITMENT AND FOCUS PRIORITY GIVING AREAS 4. 4.1 HUMANITARIAN AND SOCIAL PROJECTS 4.1.1 Clear and transparent policies for product donations 4.1.2 Clear and transparent policies for emergency assistance 4.2 SCIENCE AND EDUCATION PROJECTS 4.3 CULTURE AND ARTS PROJECTS 4.4...»

«IFRS Interpretations Agenda reference Committee Meeting March 2011 Date Staff Paper Tentative agenda decision Project IFRIC 15 Agreements for the Construction of Real Estate – Meaning of continuous transfer Topic Introduction 1. The IFRS Interpretations Committee (the Interpretations Committee) received a request asking for clarification on the meaning of the term ‘continuous transfer’ in paragraph 17 of IFRIC 15 Agreements for the Construction of Real Estate. 2. For ease of reference,...»

«SECONDARY HANDBILLING: THE NEED FOR A NEW RESPONSE by MACK** HEATHER BRIGGS* AND CURTIS L. INTRODUCTION S ECTION 8(b)(4)1 OF THE National Labor Relations Act (Act or NLRA) prohibits secondary boycotts. The publicity proviso contained in that section, however, clearly exempts from that prohibition the dissemination to the public of information that a product is generated by an employer with whom it is engaged in a labor dispute.' Because of this proviso, unions engaged in labor disputes have,...»

«NOT PRECEDENTIAL UNITED STATES COURT OF APPEALS THIRD CIRCUIT _ No. 15-1433 _ FILOMENA RANIERA WARD, MICHELLE McCANDLESS, GERMAN PARODI, DAVID WITTIE, RANDY ALEXANDER, CAROL MARFISI, individually and on behalf of similarly situated persons, DISABLED IN ACTION, a nonprofit corporation v. PHILADELPHIA PARKING AUTHORITY, and VINCE FENERTY, in his official capacity as the Executive Director of the Philadelphia Parking Authority, and TAXICAB AND LIMOUSINE DIVIDION of the PHILADELPHIA PARKING...»

«P.O. Box 1593 • Green Bay, WI 54305-1593 • Phone: 920-432-3393 www.browncountyunitedway.org Brown County United Way Special Event and Fundraising Ideas EMPLOYEE COOKBOOK 1. Ask employees to bring in their favorite recipes from home.2. Research publishing companies to print the collected recipes in a book format, or do it in-house.3. Plan on a two to six month time period for the preparation and printing of the project. 4. Take pre-orders after determining price per copy with the publishing...»

«Table of Contents User manual part II: running the POSaM Platform Overview Slide Surface Preparation In-House Epoxysilane Slide Preparation Materials: Methods: Commercial Slide Alternatives Reagent Preparation Overview: Solvent Preparation Materials: Methods: Phosphoramidites and Tetrazole Materials: Methods: Base Deprotection Solution Materials: Methods: Acetonitrile Wash Solvent Materials: Methods: Oxidizer and Deprotection Acid Materials: Methods: Arrayer Operation Overview Loading the...»

«Mother Teresa is known throughout the world as having started multiple ministries to the homeless and impoverished of India. I once knew a girl who was taken in by one of her orphanages and adopted by an American couple. Writing about her early days as a Nun, Mother Teresa says, I was traveling to Darjeeling by train, when I heard the voice of God.” It is with this line she begins the story of how God called her to minister to the poor of Calcutta India. What most people don’t know, and...»

«Palm Print Recognition Introduction Palm print recognition inherently implements many of the same matching characteristics that have allowed fingerprint recognition to be one of the most well-known and best publicized biometrics. Both palm and finger biometrics are represented by the information presented in a friction ridge impression. This information combines ridge flow, ridge characteristics, and ridge structure of the raised portion of the epidermis. The data represented by these friction...»

«GEOTECHNICAL CONSIDERATIONS IN UNDERGROUND MINES GUIDELINE MOSHAB Approved December 1997 Document No: ZME723QT Department of Industry and Resources Geotechnical Considerations in Underground Mines Document No.: ZME723QT Guideline CONTENTS Page FOREWORD 1.0 INTRODUCTION 2.0 LEGISLATIVE REQUIREMENTS (WA) 3.0 GEOTECHNICAL CONCEPTS 3.1 Introduction 3.2 Geotechnical aspects 3.3 Geological structure 3.4 Geotechnical domain 3.5 Ground 3.6 Ground control 3.7 Ground conditions 3.7.1 Soft rock conditions...»

<<  HOME   |    CONTACTS
2017 www.abstract.dislib.info - Abstracts, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.