Wyniki wyszukiwania - BazTech

1

Reasoning about Exceptions in Ontologies : from the Lexicographic Closure to the Skeptical Closure

Giordano Laura, Gliozzi Valentina

Fundamenta Informaticae

|

2020

|

Vol. 176, nr 3/4

235--269

EN

Reasoning about exceptions in ontologies is nowadays one of the challenges the description logics community is facing. The paper describes a preferential approach for dealing with exceptions in Description Logics, based on the rational closure. The rational closure has the merit of providing a simple and efficient approach for reasoning with exceptions, but it does not allow independent handling of the inheritance of different defeasible properties of concepts. In this work we outline a possible solution to this problem by introducing a weaker variant of the lexicographical closure, that we call skeptical closure, which requires to construct a single base. We develop a bi-preference semantics for defining a characterization of the skeptical closure.

2

A Set-theoretic Approach to Reasoning Services for the Description Logic DL4,xD

Cantone Domenico, Nicolosi-Asmundo Marianna, Santamaria Daniele Francesco

Fundamenta Informaticae

|

2020

|

Vol. 176, nr 3/4

349--384

EN

In this paper we consider the most common TBox and ABox reasoning services for the description logic 𝒟ℒ〈4LQSR,x 〉(D) (𝒟 ℒD 4,×, for short) and prove their decidability via a reduction to the satisfiability problem for the set-theoretic fragment 4LQSR. 𝒟 ℒD 4,× is a very expressive description logic. It combines the high scalability and efficiency of rule languages such as the Semantic Web Rule Language (SWRL) with the expressivity of description logics. In fact, among other features, it supports Boolean operations on concepts and roles, role constructs such as the product of concepts and role chains on the left-hand side of inclusion axioms, role properties such as transitivity, symmetry, reflexivity, and irreflexivity, and data types. We further provide a KE-tableau-based procedure that allows one to reason on the main TBox and ABox reasoning tasks for the description logic 𝒟 ℒ D 4,× . Our algorithm is based on a variant of the KE-tableau system for sets of universally quantified clauses, where the KE-elimination rule is generalized in such a way as to incorporate the γ-rule. The novel system, called KEγ -tableau, turns out to be an improvement of the system introduced in [1] and of standard first-order KE-tableaux [2]. Suitable benchmark test sets executed on C++ implementations of the three mentioned systems show that in several cases the performances of the KEγ -tableau-based reasoner are up to about 400% better than the ones of the other two systems.

3

Towards a Rational Closure for Expressive Description Logics : the Case of SHIQ

Giordano L., Gliozzi V., Olivetti N.

Fundamenta Informaticae

|

2018

|

Vol. 159, nr 1/2

95--122

EN

We explore the extension of the notion of rational closure to logics lacking the finite model property, considering the logic SHIQ. We provide a semantic characterization of rational closure in SHIQ in terms of a preferential semantics, based on a finite rank characterization of minimal models. We show that the rational closure of a KB can be computed in EXPTIME based on a polynomial encoding of the rational extension of SHIQ into entailment in SHIQ. We discuss the extension of rational closure to more expressive description logics.

4

Revision of Ontologies to Accommodate Exceptions : a Typicality-based Approach

Micalizio R., Pozzato G. L.

Fundamenta Informaticae

|

2018

|

Vol. 161, nr 1/2

163--189

EN

The paper presents a methodology to revise a Description Logic knowledge base when exceptions are detected. The approach exploits concepts and results from techniques developed for debugging Description Logic terminologies. Debugging an inconsistent terminology amounts to identifying a minimal subset of axioms responsible for the inconsistency (i.e., an error to be removed by a knowledge engineer). Exception handling, instead, requires to revise the axioms causing an inconsistency so that a new consistent knowledge base is obtained, encompassing the detected exception about an individual x. To this aim, we make use of a nonmonotonic extension of the Description Logic ALC based on the combination of a typicality operator and the well established nonmonotonic mechanism of rational closure, which allows one to deal with prototypical properties and defeasible inheritance.

5

Representation Theorems and Locality for Subsumption Testing and Interpolation in the Description Logics εL; εL+ and their Extensions with n-ary Roles and Numerical Domains

Sofronie-Stokkermans V.

Fundamenta Informaticae

|

2017

|

Vol. 156, nr 3/4

361--411

EN

In this paper we show that subsumption problems in lightweight description logics (such as εL and εL+) can be expressed as uniform word problems in classes of semilattices with monotone operators. We use possibilities of efficient local reasoning in such classes of algebras, to obtain uniform PTIME decision procedures for CBox subsumption in εL, εL+ and extensions thereof. These locality considerations allow us to present a new family of (possibly many-sorted) logics which extend εL and εL+ with n-ary roles and/or numerical domains. As a by-product, this allows us to show that the algebraic models of εL and εL+ have ground interpolation and thus that εL, εL+, and their extensions studied in this paper have interpolation.

6

ExpTime Tableaux with Global Caching for Graded Propositional Dynamic Logic

Nguyen L. A.

Fundamenta Informaticae

|

2016

|

Vol. 147, nr 2/3

261--288

EN

We present the first direct tableau decision procedure for graded PDL, which uses global caching and has ExpTime (optimal) complexity when numbers are encoded in unary. It shows how to combine checking fulfillment of existential star modalities with integer linear feasibility checking for tableaux with global caching. As graded PDL can be used as a description logic for representing and reasoning about terminological knowledge, our procedure is useful for practical applications.

7

A Tractable Rule Language in the Modal and Description Logic that Combines CPDL with Regular Grammar Logic

Nguyen L. A.

Fundamenta Informaticae

|

2016

|

Vol. 143, nr 1/2

113--139

EN

Combining CPDL (Propositional Dynamic Logic with Converse) and regular grammar logic results in an expressive modal logic denoted by CPDLreg. This logic covers TEAMLOG, a logical formalism used to express properties of agents’ cooperation in terms of beliefs, goals and intentions. It can also be used as a description logic for expressing terminological knowledge, in which both regular role inclusion axioms and CPDL-like role constructors are allowed. In this paper, we develop an expressive and tractable rule language called Horn-CPDLreg. As a special property, this rule language allows the concept constructor “universal restriction” to appear on the left hand side of general concept inclusion axioms. We use a special semantics for Horn-CPDLreg that is based on pseudo-interpretations. It is called the constructive semantics and coincides with the traditional semantics when the concept constructor “universal restriction” is disallowed on the left hand side of concept inclusion axioms or when the language is used as an epistemic formalism and the accessibility relations are serial. We provide an algorithm with PTIME data complexity for checking whether a knowledge base in Horn-CPDLreg has a pseudo-model. This shows that the instance checking problem in Horn-CPDLreg with respect to the constructive semantics has PTIME data complexity.

8

Bisimulation-Based Concept Learning in Description Logics

Tran T.-L., Ha Q.-T., Hoang T.-L.-G., Nguyen L. A., Nguyen H. S.

Fundamenta Informaticae

|

2014

|

Vol. 133, nr 2/3

287--303

EN

Concept learning in description logics (DLs) is similar to binary classification in traditional machine learning. The difference is that in DLs objects are described not only by attributes but also by binary relationships between objects. In this paper, we develop the first bisimulation-based method of concept learning in DLs for the following setting: given a knowledge base KB in a DL, a set of objects standing for positive examples and a set of objects standing for negative examples, learn a concept C in that DL such that the positive examples are instances of C w.r.t. KB, while the negative examples are not instances of C w.r.t. KB. We also prove soundness of our method and investigate its C-learnability.

9

An ExpTime Tableau Method for Dealing with Nominals and Qualified Number Restrictions in Deciding the Description Logic SHOQ

Nguyen L. A., Golińska-Pilarek J.

Fundamenta Informaticae

|

2014

|

Vol. 135, nr 4

433--449

EN

We present the first tableau method with an EXPTIME (optimal) complexity for checking satisfiability of a knowledge base in the description logic SHOQ, which extends ALC with transitive roles, hierarchies of roles, nominals and qualified number restrictions. The complexity is measured using unary representation for numbers (in number restrictions). Our procedure is based on global caching and integer linear feasibility checking.

10

Wnioskowanie z różnych źródeł osobników w systemie RKaSeA

Goczyła K., Waloszek A., Waloszek W., Zawadzka T.

Studia Informatica

|

2010

|

Vol. 31, nr 2A

89-103

PL

Niniejszy artykuł prezentuje koncepcję zarządzania wiedzą asercjonalną zastosowaną w systemie zarządzania wiedzą RKASEA. Koncepcja ta traktuje opis świata jako zbiór źródeł osobników. Dzięki temu udało się objąć nią również mechanizm obsługi reguł oraz mechanizm pozyskiwania wiedzy z zewnętrznych źródeł danych. Mechanizmy te są traktowane jako dodatkowe typy źródeł osobników.

EN

The paper presents the concept of managing assertional knowledge in a novel knowledge management system RKASEA. According to this concept the description of the world is handled as a set of sources of individuals. This concept turned out to be flexible enough to cover the mechanism for inferring with rules and the mechanism for acquiring the data from external data sources. In the presented framework the both mechanisms are recognized as additional types of sources of individuals.

11

Wewnętrzna reprezentacja konglomeratowej bazy wiedzy w systemie RKaSeA

Goczyła K., Waloszek A., Waloszek W., Zawadzka T.

Studia Informatica

|

2010

|

Vol. 31, nr 2A

105-120

PL

Niniejszy artykuł prezentuje koncepcję wewnętrznej reprezentacji wiedzy ontologicznej zastosowaną w nowo opracowanym systemie zarządzania wiedzą ontologiczno-regułową RKASEA. Reprezentacja ta stanowi praktyczne wdrożenie opublikowanej wcześniej koncepcji modularyzacji bazy wiedzy polegającej na jej podziale na semantyczne jednostki – konglomeraty. Opracowana metoda reprezentacji stanowi zarazem rozwinięcie wprowadzonej wcześniej metody kartograficznej.

EN

This article presents a novel method of internal knowledge representation. The method has been exploited in newly created RKASEA system and is a practical implementation of the recently published concept of s-modular knowledge bases. The method is also a development of earlier idea of knowledge cartography.

12

Horn Knowledge Bases in Regular Description Logics with PTIME Data Complexity

Nguyen L.A. L.A.

Fundamenta Informaticae

|

2010

|

Vol. 104, nr 4

349-384

EN

Developing a good formalism and an efficient decision procedure for the instance checking problem is desirable for practical application of description logics. The data complexity of the instance checking problem is coNP-complete even for Horn knowledge bases in the basic descriptionn logic ALC. In this paper, we present and study weakenings with PTIME data complexity of the instance checking problem for Horn knowledge bases in regular description logics. We also study cases when the weakenings are an exact approximation. In contrast to previous related work of other authors, our approach deals with the case when the constructor ∀ is allowed in premises of program clauses that are used as terminological axioms.

13

Fuzzy Clustering for Semantic Knowledge Bases

Esposito F., d’Amato C., Fanizzi N.

Fundamenta Informaticae

|

2010

|

Vol. 99, nr 2

187-205

EN

This work focusses on the problem of clustering resources contained in knowledge bases represented throughmulti-relational standard languages that are typical for the context of the SemanticWeb, and ultimately founded in Description Logics. The proposed solution relies on effective and language-independent dissimilarity measures that are based on a finite number of dimensions corresponding to a committee of discriminating features, that stands for a context, represented by concept descriptions in Description Logics. The proposed clustering algorithm expresses the possible clusterings in tuples of central elements: in this categorical setting, we resort to the notion of medoid, w.r.t. the given metric. These centers are iteratively adjusted following the rationale of fuzzy clustering approach, i.e. one where the membership to each cluster is not deterministic but graded, ranging in the unit interval. This better copes with the inherent uncertainty of the knowledge bases expressed in Description Logics which adopt an open-world semantics. An extensive experimentation with a number of ontologies proves the feasibility of our method and its effectiveness in terms of major clustering validity indices.

14

An Efficient Tableau Prover using Global Caching for the Description Logic ALC

Nguyen L.A. L.A.

Fundamenta Informaticae

|

2009

|

Vol. 93, nr 1-3

273-288

EN

We report on our implementation of a tableau prover for the description logic ALC, which is based on the EXPTIME tableau algorithm using global caching for ALC that was developed jointly by us and Gor´e [9]. The prover, called TGC for "Tableaux with Global Caching", checks satisfiability of a set of concepts w.r.t. a set of global assumptions by constructing an and-or graph, using tableau rules for expanding nodes. We have implemented for TGC a special set of optimizations which co-operates very well with global caching and various search strategies. The test results on the test set T98-sat of DL'98 Systems Comparison indicate that TGC is an efficient prover for ALC. This suggests that global caching together with the set of optimizations used for TGC is worth implementing and experimenting also for other modal/description logics.

15

ALC + T: a Preferential Extension of Description Logics

Giordano L., Gliozzi V., Olivetti N., Pozzato G.L.

Fundamenta Informaticae

|

2009

|

Vol. 96, nr 3

341-372

EN

We extend the Description Logic ALC with a "typicality" operator T that allows us to reason about the prototypical properties and inheritance with exceptions. The resulting logic is called ALC + T. The typicality operator is intended to select the “most normal” or "most typical" instances of a concept. In our framework, knowledge bases may then contain, in addition to ordinary ABoxes and TBoxes, subsumption relations of the form "T(C) is subsumed by P", expressing that typical C-members have the property P. The semantics of a typicality operator is defined by a set of postulates that are strongly related to Kraus-Lehmann-Magidor axioms of preferential logic P. We first show that T enjoys a simple semantics provided by ordinary structures equipped with a preference relation. This allows us to obtain a modal interpretation of the typicality operator. We show that the satisfiability of an ALC+Tknowledge base is decidable and it is precisely EXPTIME. We then present a tableau calculus for deciding satisfiability of ALC + T knowledge bases. Our calculus gives a (suboptimal) nondeterministic-exponential time decision procedure for ALC + T. We finally discuss how to extend ALC + T in order to infer defeasible properties of (explicit or implicit) individuals. We propose two alternatives: (i) a nonmonotonic completion of a knowledge base; (ii) a "minimal model" semantics for ALC + T whose intuition is that minimal models are those that maximise typical instances of concepts.

16

A Semantic Model for Matchmaking of Web Services Based on Description Logics

Shen G., Huang Z., Zhang Y., Zhu X., Yang J.

Fundamenta Informaticae

|

2009

|

Vol. 96, nr 1/2

211-226

EN

Matchmaking plays an important role in Web services interactions. The matchmaking based on keywords easily leads to low precision, Meanwhile, the current semantic service discovery methods perform service I/O based profile matching, there exists no matchmaker that performs an integrated service matching by additional reasoning on logically defined preconditions, effects, Qos and so on. In this paper, the semantic web services are described based on Description Logics, and the services description model is designed, which describes the various aspects (such as IOPEs, Qos and so on) of the web services. So the services matchmaking is transformed into the match of concepts. The service match algorithm is proposed and the description logics reasoner RacerPro is adopted for Web services discovery. We show how the semantic matching between providers and a requester is performed by a case study.

17

Ontologie w sieci semantycznej

Goczyła K., Zawadzka T.

Studia Informatica

|

2006

|

Vol. 27, nr 2

65-92

PL

Wraz z nastaniem ery Internetu i jego gwałtownym rozwoje, zasadniczym problemem dla współczesnej informatyki stała się automatyzacja pozyskiwania olbrzymich zasobów wiedzy ludzkiej w nim zgromadzonych. Wiedza ta ma bardzo zróżnicowany charakter z uwagi na wielkość formatów zapisu danych, a przede wszystkim z uwagi na różny stopień jej ustrukturalizowania. Jedną z najbardziej popularnych idei, dążących do systematycznego podejścia do pozyskiwania wiedzy z Internatu stała się, tzw. "inicjatywa Semantic Web". Zgodnie z tą ideą, wiedza ludzka powinna być strukturalizowana w formie ontologii publikowanych w Internecie, w powszechnie zaakceptowanym, precyzyjnym i możliwym do przetwarzania przez komputery, formacie. W tym artykule bliżej prezentujemy problemy, związane z budową ontologii i ich wykorzystaniem w ramach Semantic Web (Sieci Sematycznej). Problemy te przedstawione są na szerszym tle różnych metod maszynowej reprezentacji wiedzy. Prezentujemy także podejście alternatywne, polegające na automatycznym tworzeniu "ontologii wszystkiego", na podstawie analizy tekstu stron WWW w języku naturalnym.

EN

One the major and most challenging tasks for modern Information Technology is development of methods aimed at automatically acquiring and processing knowledge stored in the biggest information repository tha man has ever created - the Internet. This knowledge is of miscellaneous nature, mainly due to the fact that it is stored in many languages and in numerous formats with different levels of structuring. The "Semantic Web initiative" strives to achieve this goal by structuring the contents of Internet into publicly available and shared ontologies formulated in a commonly accepted, machine readable format. In this paper we discuss problems of building ontologies and using them throughout Semantic Web. Relevant topics are presented in the broader contexts of knowledge representation methods. We also present an alternative approach based on processin textual Web contents, extracting semantics from them and creating a "general ontology" to be used to present knowledge to user.

18

From Tableaux to Automata for Description Logics

Baader F., Hladik J., Lutz C., Wolter F.

Fundamenta Informaticae

|

2003

|

Vol. 57, nr 2-4

247--279

EN

This paper investigates the relationship between automata- and tableau-based inference procedures for description logics. To be more precise, we develop an abstract notion of what a tableau-based algorithm is, and then show, on this abstract level, how tableau-based algorithms can be converted into automata-based algorithms. In particular, this allows us to characterize a large class of tableau-based algorithms that imply an ExpTime upper-bound for reasoning in the description logics for which such an algorithm exists.