FREE ELECTRONIC LIBRARY - Abstracts, online materials

Pages:   || 2 |

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

-- [ Page 1 ] --

Paraconsistent Reasoning for Expressive and Tractable

Description Logics

Yue Ma1, Pascal Hitzler2, and Zuoquan Lin1

Department of Information Science, Peking University, China

AIFB, Universit¨ t Karlsruhe, Germany


{mayue,lz}@is.pku.edu.cn, hitzler@aifb.uni-karlsruhe.de

Abstract. Four-valued description logic has been proposed to reason with description logic based inconsistent knowledge bases, mainly ALC. This approach

has a distinct advantage that it can be implemented by invoking classical reasoners to keep the same complexity as classical semantics. In this paper, we further study how to extend the four-valued semantics to more expressive description logics, such as SHIQ, and to more tractable description logics including EL++, DL-Lite, and Horn-DLs. The most effort we spend defining the four-valued semantics of expressive four-valued description logics is on keeping the reduction from four-valued semantics to classical semantics as in the case of ALC;

While for tractable description logics, we mainly focus on how to maintain their tractability when adopting four-valued semantics.

1 Introduction Expressive and tractable description logics have been well-studied in the field of semantic web applications [12, 13]. However, real knowledge bases and data for Semantic Web applications will rarely be perfect. They will be distributed and multi-authored.

They will be assembled from different sources and reused. It is unreasonable to expect such realistic knowledge bases to be always logically consistent, and it is therefore important to study ways of dealing with inconsistencies in both expressive and tractable description logic based ontologies, as classical description logics break down in the presence of inconsistent knowledge.

About inconsistency handling of ontologies based on description logics, two fundamentally different approaches can be distinguished. The first is based on the assumption that inconsistencies indicate erroneous data which is to be repaired in order to obtain a consistent knowledge base, e.g. by selecting consistent subsets for the reasoning process [14, 5, 4]. The other approach yields to the insight that inconsistencies are a natural phenomenon in realistic data which are to be handled by a logic which tolerates it [11, 15, 8]. Such logics are called paraconsistent, and the most prominent of them are based on the use of additional truth values standing for underdefined (i.e. neither true We acknowledge support by the German Federal Ministry of Education and Research (BMBF) under the SmartWeb project (grant 01 IMD01 B), by the EU under the IST project NeOn (ISThttp://www.neon-project.org/), andby the Deutsche Forschungsgemeinschaft (DFG) in the ReaSem project.

nor false) and overdefined (or contradictory, i.e. both true and false). Such logics are appropriately called four-valued logics [2, 1]. We believe that either of the approaches is useful, depending on the application scenario. Besides this, four-valued semantics proves useful for measuring inconsistency of ontologies [9], which can provide context information for facilitating inconsistency handling.

In this paper, based on our study of paraconsistent semantics for ALC in [8], we contribute to the inconsistency handling for DLs in terms of the four-valued semantics

for expressive and tractable DLs in following aspects:

– The extension of four-valued semantics to SHIQ is defined. Specially, we show that it still can be reduced to classical semantics regardless its high expressivity.

– The extension of four-valued semantics to tractable description logics EL++, HornDLs, DL-Lite family are studied one by one. We show that the internal inclusion axiom form is a safe way to maintain the tractability when adopting four-valued semantics.

– Compared with our existing work on four-valued semantics of ALC, in this paper, we do not impose four-valued semantics on roles for DLs except DL-Lite. The reasons are: 1) Negative roles are not used as concept constructors in ALC, SHIQ, EL++, or Horn-DLs such that contradiction caused directly by roles can be ignored.

2) We claim that the four-valued semantics should be defined as classically as possible. 3) Four-valued semantics is semantically weaker than classical semantics (the syllogism does not hold under four-valued entailment). So if we adopt four-valued semantics for roles, then we have {R S, R(a, b)} |=4 S(a.b) even though there is no contradiction in the precondition.

The paper is structured as follows. We first review briefly the four-valued semantics for ALC in Section 2. Then we study the four-valued semantics for expressive description logics in Section 3 and four-valued semantics for tractable description logics in Section 4, respectively. We conclude and discuss future work in Section 5.

2 Preliminaries

2.1 The Four-valued Semantics for ALC We describe the syntax and semantics of four-valued description logic ALC4 [8]. Syntactically, ALC4 hardly differs from ALC. Complex concepts and assertions are dened in exactly the same way. For class inclusion, however, significant effort has been devoted on the intuitions behind these different implications in [8]. We claim that various inclusion axioms provide flexible ways to model inconsistent ontologies. They are

as follows:

C → D (material inclusion axiom), C D (internal inclusion axiom), C → D (strong inclusion axiom).

Semantically, interpretations map individuals to elements of the domain of the interpretation, as usual. For concepts, however, modifications are made to the notion of interpretation in order to allow for reasoning with inconsistencies.

Table 1. Semantics of ALC4 Concepts

–  –  –

Intuitively, in four-valued logic we need to consider four situations which can occur in terms of containment of an individual in a concept: (1) we know it is contained, (2) we know it is not contained, (3) we have no knowledge whether or not the individual is contained, (4) we have contradictory information, namely that the individual is both contained in the concept and not contained in the concept. There are several equivalent ways how this intuition can be formalised, one of which is described in the following.

For a given domain ∆I and a concept C, an interpretation over ∆I assigns to C a pair P, N of (not necessarily disjoint) subsets of ∆I. Intuitively, P is the set of elements known to belong to the extension of C, while N is the set of elements known to be not contained in the extension of C. For simplicity of notation, we define functions proj+ (·) and proj− (·) by proj+ P, N = P and proj− P, N = N.

Formally, a four-valued interpretation is a pair I = (∆I, ·I ) with ∆I as domain, where ·I is a function assigning elements of ∆I to individuals, and subsets of (∆I )2 to concepts, such that the conditions in Table 1 are satisfied. Note that the semantics of roles here remains unchanged from the classical two-valued case. Intuitively, inconsistencies always rise on concepts, and not on roles, at least in the absence of role negation, which is often assumed when studying DLs. We will see in this paper that this approach can be used to tolerate inconsistency, not only for ALC but also for more expressive description logics. This is an improvement over [8] in the sense that we would like to make as few changes as possible when extending the classical semantics to a four-valued semantics for handling inconsistency.

The semantics of the three different types of inclusion axioms is formally defined in Table 2 (together with the semantics of concept assertions). we refer to [8] for details.

We say that a four-valued interpretation I satisfies a four-valued knowledge base O (i.e. is a model of it) iff it satisfies each assertion and each inclusion axiom in O. A knowledge base O is satisfiable (unsatisfiable) iff there exists (does not exist) such a model.

Table 2. Semantics of inclusion axioms in ALC4

–  –  –

2.2 Reduction from Four-valued Semantics of ALC to Classical Semantics It is a pleasing property of ALC4 that it can be translated easily into classical ALC, such that paraconsistent reasoning can be simulated by using standard ALC reasoning algorithms.

Definition 1 (Concept transformation) For any given concept C, its transformation π(C) is the concept obtained from C by the following inductively defined transformation.

= A for A an atomic concept, then π(C) = A+, where A+ is a new concept;

– If C – If C = ¬A for A an atomic concept, then π(C) = A, where A is a new concept;

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

– If C = ⊥, then π(C) = ⊥;

– If C = E D for concepts D, E, then π(C) = π(E) π(D);

– If C = E D for concepts D, E, then π(C) = π(E) π(D);

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

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

– If C = ¬¬D for a concept D, then π(C) = π(D);

– If C = ¬(E D) for concepts D, E, then π(C) = π(¬E) π(¬D);

– If C = ¬(E D) for concepts D, E, then π(C) = π(¬E) π(¬D);

– If C = ¬(∃R.D) for D a concept and R is a role, then π(C) = ∀R.π(¬D);

– If C = ¬(∀R.D) for D a concept and R is a role, then π(C) = ∃R.π(¬D);

Based on this, axioms are transformed as follows.

Definition 2 (Axiom Transformations) For any ontology O, π(O) is defined as the set {π(α) | α is an axiom of O}, where π(α) is the transformation performed on each

axiom defined as follows:

– π(α) = ¬π(¬C1 ) π(C2 ), if α = C1 → C2 ;

– π(α) = π(C1 ) π(C2 ), if α = C1 C2 ;

– π(α) = {π(C1 ) π(C2 ), π(¬C2 ) π(¬C1 )}, if α = C1 → C2 ;.

– π(C(a)) = π(C)(a), π(R)(a, b) = R(a, b), where a, b are individuals, C1, C2, C are concepts, R a role.

We note two issues. First of all, the transformation algorithm is linear in the size of the ontology. Secondly, for any ALC ontology O, π(O) is still an ALC ontology.

Based on these two observations as well as the following theorem, we can see that paraconsistent reasoning of ALC can indeed be simulated on standard reasoners by means of the transformation just given.

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

Definition 3 Given a knowledge base O, the satisfiable form of O, written SF(O), is a knowledge base obtained by replacing each occurrence of ⊥ in O with Anew ¬Anew, and replacing each occurrence of in (O) with with Anew ¬Anew, where Anew is a new atomic concept.

3 Paraconsistent Semantics for Expressive DLs In this section, we study how to extend four-valued semantics to SHIQ.

For the conflicting assertion set {≥ (n + 1)R.C(a), ≤ nR.C(a)}, intuitively, it is caused by the contradiction that there should be less than n different individuals related to a via the R relation, and also there should be more than n + 1 different individuals related to a via R. That is, the contradiction is from the set of individuals of concept C which relate a via R. By this idea, we extend the four-valued semantics to the constructors for number restrictions in Table 3. We remark that the semantics of roles is just the classical semantics. So the semantics for role inclusion and transitive role axiom are still classical.

Table 3. Four-valued Semantics Extension to Number Restrictions and Nominals

–  –  –

Example 1 Consider {≥ 2hasStu.P hD(Green), ≤ 1hasStu.P hD(Green)} which says the conflicting facts that Green has at least two and at most one PhD student. Consider a 4-interpretation: I = (∆I, ·I ) where ∆I = {a1, a2, b1, b2, Green}, P hDI = {a1, b1 }, {b1, b2, a2 }, and hasStuI = {(Green, a1 ), (Green, a2 ), (Green, b1 ), (Green, b2 )}.

According to Table 3, we can see that I is a 4-model because (≥ 2hasStu.P hD(Green))I = (≤ 1hasStu.P hD(Green))I = B by checking Green ∈ {x | #(y.(x, y) ∈ hasStuI ∧ y ∈ proj+ (P hDI )) ≥ 2}, Green ∈ {x | #(y.(x, y) ∈ hasStuI ∧ y ∈ proj− (P hDI )) 2}.

That is, the conflicting assertions are assigned the contradictory truth value B under their 4-model I.

For the extended four-valued semantics defined in Table 3, we have following properties hold as under classical semantics.

Proposition 2 Let C be a concept and R be an object role name. For any fourvalued interpretation I defined satisfying Table 3, we have

–  –  –

Proposition 2 and Proposition 3 show that many intuitive relations between different concept constructors still hold under the four-valued semantics, which is one of nice properties of our four-valued semantics for handling inconsistency.

Next proposition shows that our definition of four-valued semantics for SHIQ is enough to handle inconsistencies in an SHIQ knowledge base.

Proposition 4 For any SHIQ knowledge base O, SF(O) always has at least one 4-valued model, where SF(·) operator is defined in Definition 3.

Note that unqualified number restrictions, ≥ n.R and ≤ n.R are special forms of number restrictions because of the equations ≤ n.R =2 ≤ nR. and ≥ n.R =2 ≥ nR.. However, if we defined the four-valued semantics of ≤ n.R(≥ n.R) by the fourvalued semantics of ≤ nR. (≥ nR. ) defined in Table 3 and Table 1, we would find that {≤ n.R(a), ≥ n+1.R(a)} is still an unsatisfiable set. This is because #(y.(a, y) ∈ proj(RI ) ∧ y ∈ proj+ ( I )) ≥ n + 1 and #(y.(a, y) ∈ proj(RI ) ∧ y ∈ proj− ( I )) ≤ n cannot hold simultaneously since I = ∆I, ∅.

To address this problem, we also adopt the substitution defined by Definition 3. By substituting by Anew ¬Anew in ≥ (n + 1)R. and ≤ nR., we can see that {≤ n.R(a), ≥ n + 1.R(a)} has a four-valued model with ∆I = {a, b1,..., bn+1 }, (a, bi ) ∈ RI for 1 ≤ i ≤ n + 1, and AI = ∆I, ∆I. By doing this, we get a four-valued new model I which pushes the contraction onto the new atomic concept Anew.

Next we study how to extend the reduction algorithm to the case of four-valued semantics of SHIQ.

Definition 4 (Definition 1 extended) For any given concept C, its transformation π(C) is the concept obtained from C by the following inductively defined transformation.

Pages:   || 2 |

Similar works:

«ERPA 2015 International Congress on Education AthensGreece, 04-07 June, 2015 BOOKS OF ABSTRACTS All rights reserved. The ideas published in the book belong to the authors ERPA International Congresses on Education 2015 i Message from the President of the Congress Dear Colleagues, Welcome to the ERPA International Congresses on Educaton 2015 which is held in Athens. This privileged scientific event aims to contribute to the field of educational research. It has created the opportunutiy to bring...»

«Introduction Employer’s Statement Pertaining to a Member’s Application for Disability Retirement Updated August, 2003 Who should prepare this form? In accordance with 840 CMR 10.07 (Code of Massachusetts Regulations), the Employer’s Statement should be prepared by the head of the department that employs the disability retiree applicant. However, if the department head does not supervise the applicant, the applicant’s direct supervisor should prepare and sign this statement and it should...»

«April 2016    Paw Print Greetings!. Happy Spring!!     The Neenah Animal Shelter will be holding our annual Garden Party on May 21st and May 22nd.  Believe it or not, the weather will improve and we'll soon be working in our gardens.  As you thin out last year's perennials and bulbs please don't discard them.  We would appreciate you donating those perennials and/or bulbs to us for...»

«Newsview 1 NEWSVIEW: SOUTH AFRICA Brian Oswin BODY COUNT, NATAL Nationalism and the Reign of Terror Over 600 Africans were killed in the Pietermaritzburg district in the Natal midlands between September 1987 and October 1988, and the carnage continues with weekly, if not daily, reports of more deaths. These murders were (and are) perpetrated, not by police and not by whites, but by blacks on blacks. By any standards, the death of so many people (and this excludes those assaulted, maimed,...»

«Department of Pacific Areas Minutes of the 50th Annual Convention Chiang Mai, Thailand 5-9 June 2016 OPENING CEREMONIES The opening ceremonies of the 50th Annual Convention were held beginning 1000 hours on Monday, June 6, 2016. Department Commander Homer Kemper asked everyone to be seated after the Salute to the Colors, and officially opened the convention.Adjutant Hudson introduced the following VIPs: VFW Senior Vice Commander in Chief Brian Duffy Deputy Chief of Mission, Amembassy Thailand,...»

«Logistics Cluster Global Meeting NOTE FOR THE RECORD 6 – 8 June 2016 Hosted by Save the Children, London 1 CONTENTS PAGE BACKGROUND AND INTRODUCTION...3 GLOBAL MEETING AGENDA...4 DAY ONE....5 DAY TWO....10 DAY THREE....14 GLOBAL MEETING ACTION POINTS...16 ATTENDANCE LIST...17 ANNEXES....18 2 LOGISTICS CLUSTER GLOBAL MEETING 6 – 8 JUNE 2016 HOSTED BY SAVE THE CHILDREN, LONDON BACKGROUND The Logistics Cluster Global Meetings are held twice a year, and bring together Logistics Cluster...»

«Regularization and nonlinearities for neural language models: when are they needed? Marius Pachitariu Maneesh Sahani Gatsby Computational Neuroscience Unit Gatsby Computational Neuroscience Unit University College London, UK University College London, UK arXiv:1301.5650v2 [stat.ML] 20 Jun 2013 marius@gatsby.ucl.ac.uk maneesh@gatsby.ucl.ac.uk Abstract Neural language models (LMs) based on recurrent neural networks (RNN) are some of the most successful word and character-level LMs. Why do they...»

«GM12.15 STAFF REPORT ACTION REQUIRED Semi-annual Treasurer’s Report on activities of the Accounting Services and the Purchasing & Materials Management Divisions – December 31, 2015 April 22, 2016 Date: Government Management Committee To: Treasurer From: All Wards: Reference P:\2016\Internal Services\acc\gm16002acc (AFS 22013) Number: SUMMARY This report provides a summary of the activities and performance indicators for the Accounting Services (AS) Division and the Purchasing and Materials...»

«Gina Says Adventures in the Blogosphere's String War Selected and edited by: Gil Kalai Debates portrayed in books, are the worst sort of readings, Jonathan Swift. Preface In the summer of 2006 two books attacking string theory, a prominent theory in physics, appeared. One by Peter Woit called Not even wrong and the other by Lee Smolin called The trouble with Physics. A fierce public debate, much of it on weblogs, ensued. Gina is very curious about science blogs. Can they be useful for learning...»

«Europhysics Letters 57, 368 (2002) Symmetries and physical properties of polar columnar phases in materials composed of achiral molecules Helmut R. Brand 1, P.E. Cladis 2, and Harald Pleiner 3 Theoretische Physik III, Universit¨t Bayreuth, 95440 Bayreuth, Germany a Advanced Liquid Crystal Technologies, PO Box 1314, Summit, NJ 07902 Max-Planck-Institute for Polymer Research, PO Box 3148, 55021 Mainz, Germany PACS. 61.30.Gd – Orientational order of liquid crystals; electric and magnetic...»

«Waverley Council PO Box 9, Bondi Junction, NSW 1355 DX 12006 Bondi Junction. Telephone: 9369 8000 Fax: 9387 1820 TTY: 9389 9827 (For hearing impaired) 9 July 2013 A meeting of COUNCIL will be held at Waverley Council Chambers, Bondi Road, Bondi Junction at: 7.00PM, TUESDAY, 16 JULY 2013 QUORUM: Seven Councillors APOLOGIES: E-mail the General Manager or Governance Manager Late notice by telephone or through a Councillor attending the meeting Tony Reed GENERAL MANAGER MEETING DATES FOR AUGUST...»

«Regarding Beelzebub’s Tales Letters to C. S. Nott and Louis Pauwels Dennis Saurat In his Journey Through This World: the second journal of a pupil (Further Teachings of Gurdjief 1969). C. S. Nott recounts how he became a publisher and issued some work by Denis Saurat: J. W. D. “I published Denis Saurat's Three Conventions, which brought about a close friendship. He had met Gurdjieff at the Prieuré at Orage's suggestion and had been profoundly impressed. Saurat, a son of peasants, had a...»

<<  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.