O domínio de grades computacionais é fortemente associado ao compartilhamento de recursos para a resolução de problemas em ambientes dinâmicos e heterogê- neos. Reutilizar aplicações armazenadas na grade e alocar recursos para atender os requisitos das aplicações são tarefas essenciais na grade e dependem da qualidade das informações disponíveis. O presente trabalho propõe uma abordagem semântica para a construção de um serviço de metadados sobre grades e sobre as aplicações nelas disponibilizadas. A abordagem proposta explora a realização de inferência sobre ontologias de aplicações e recursos computacionais da grade e a realização de consultas sobre a base inferida para promover a realização de tarefas, tais como escalonamento de recursos para execução de aplicações na grade, de modo e_ciente. O middleware para Grades oportunistas, InteGrade, foi a base a para o desenvolvimento desse projeto. / The grid computing domain is strongly related to resource sharing for problem resolution in dynamic and heterogeneous environments. The reuse of applications stored on grids and the allocation of resources to meet application requirements are essential grid tasks. These tasks depend on the quality of available information. This work proposes a semantic approach to build a metadata service about grid models, resources and applications. This approach explores inference and queries on ontologies about applications and grid computational resources aiming to enhance the execution of grid tasks, such as resource scheduling on grids. We used InteGrade, an opportunistic grid middleware, as the ground for the development of our project. The metadata integration will contribute to promote the e_cient usage of grid resources and applications.

O domínio de grades computacionais é fortemente associado ao compartilhamento de recursos para a resolução de problemas em ambientes dinâmicos e heterogê- neos. Reutilizar aplicações armazenadas na grade e alocar recursos para atender os requisitos das aplicações são tarefas essenciais na grade e dependem da qualidade das informações disponíveis. O presente trabalho propõe uma abordagem semântica para a construção de um serviço de metadados sobre grades e sobre as aplicações nelas disponibilizadas. A abordagem proposta explora a realização de inferência sobre ontologias de aplicações e recursos computacionais da grade e a realização de consultas sobre a base inferida para promover a realização de tarefas, tais como escalonamento de recursos para execução de aplicações na grade, de modo e_ciente. O middleware para Grades oportunistas, InteGrade, foi a base a para o desenvolvimento desse projeto. / The grid computing domain is strongly related to resource sharing for problem resolution in dynamic and heterogeneous environments. The reuse of applications stored on grids and the allocation of resources to meet application requirements are essential grid tasks. These tasks depend on the quality of available information. This work proposes a semantic approach to build a metadata service about grid models, resources and applications. This approach explores inference and queries on ontologies about applications and grid computational resources aiming to enhance the execution of grid tasks, such as resource scheduling on grids. We used InteGrade, an opportunistic grid middleware, as the ground for the development of our project. The metadata integration will contribute to promote the e_cient usage of grid resources and applications.

OLIVEIRA, Henrique Viana. Refinamento de Consultas em Lógicas de Descrição Utilizando Teoria dos Rough Sets. 2012. 111 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2012. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-07-01T17:23:02Z No. of bitstreams: 1 2012_dis_hvoliveira.pdf: 789598 bytes, checksum: d75ef093adc56cc930f52c1e486ead5a (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-07-01T17:23:47Z (GMT) No. of bitstreams: 1 2012_dis_hvoliveira.pdf: 789598 bytes, checksum: d75ef093adc56cc930f52c1e486ead5a (MD5) / Made available in DSpace on 2016-07-01T17:23:47Z (GMT). No. of bitstreams: 1 2012_dis_hvoliveira.pdf: 789598 bytes, checksum: d75ef093adc56cc930f52c1e486ead5a (MD5) Previous issue date: 2012 / Query Refinement consists of methods that modify the terms of a consult aiming the change of its result obtained previously. Refinements can be done of several ways and different approaches can be applied to it. This work proposes to apply methods of Query Refinement based on Rough Set theory, using it as an alternative for the refinement problem. The proposed methods will be grounded in the languages of Description Logics, which are commonly used on problems involving knowledge bases or ontologies representation. Two extensions of Description Logics with the Rough Set theory are introduced in this dissertation. We will prove the complexity of satisfiability of these logics, as well as the complexities of the query refinement methods applied to these logics. Finally, we will show quality measures which will aid to choose the results of the refinements obtained. / Refinamento de consulta consiste de técnicas que modificam os termos de uma consulta com o objetivo de alterar os resultados obtidos inicialmente. Para a realização de tal fim, diversas abordagens podem ser aplicadas e diferentes tipos de refinamentos podem ser considerados. Este trabalho propõe aplicar a teoria dos Rough Sets como uma nova alternativa de solução para o problema. Através das noções presentes nessa teoria, iremos desenvolver técnicas que serão aplicadas nas linguagens de Lógicas de Descrição, que são comumente utilizadas em problemas de representação de bases de conhecimento ou ontologias. Além disso, introduziremos duas extensões de Lógicas de Descrição capazes de representar as operações da teoria dos Rough Sets. Provaremos os resultados de complexidade de decisão dessas duas lógicas, assim como os resultados de complexidade das técnicas de refinamentos desenvolvidas. Por fim, mostraremos métricas de qualidade que poderão ser usadas para melhorar o resultado dos refinamentos obtidos.

The work in this paper is motivated by a privacy scenario in which the identity of certain persons (represented as anonymous individuals) should be hidden.We assume that factual information about known individuals (i.e., individuals whose identity is known) and anonymous individuals is stored in an ABox and general background information is expressed in a TBox, where both the TBox and the ABox are publicly accessible. The identity problem then asks whether one can deduce from the TBox and the ABox that a given anonymous individual is equal to a known one. Since this would reveal the identity of the anonymous individual, such a situation needs to be avoided. We first observe that not all Description Logics (DLs) are able to derive any such equalities between individuals, and thus the identity problem is trivial in these DLs. We then consider DLs with nominals, number restrictions, or function dependencies, in which the identity problem is non-trivial. We show that in these DLs the identity problem has the same complexity as the instance problem. Finally, we consider an extended scenario in which users with different rôles can access different parts of the TBox and ABox, and we want to check whether, by a sequence of rôle changes and queries asked in each rôle, one can deduce the identity of an anonymous individual.

We examine the complexity and expressivity of the combination of the Description Logic ALCQI with a terminological formalism based on cardinality restrictions on concepts. This combination can naturally be embedded into C², the two variable fragment of predicate logic with counting quantifiers. We prove that ALCQI has the same complexity as C² but does not reach its expressive power. / An abriged version of this paper has been submitted to CSL'99

Matching of concepts with variables (concept patterns) is a relatively new operation that has been introduced in the context of description logics, originally to help filter out unimportant aspects of large concepts appearing in industrial-strength knowledge bases. Previous work has concentrated on (sub-)languages of CLASSIC, which in particular do not allow for existential restrictions. In this work, we present sound and complete decision algorithms for the solvability of matching problems and for computing sets of matchers for matching problems in description logics with existential restrictions.

The description logic ALCQI extends the 'standard' description logic ALC by qualifying number restrictions and converse roles. We show that conept satisfiability for this DL is still decidable in polynomial space. The presented algorithm combines techniques from [Tob99a] to deal with qualifying number restrictions and from [HST99] to deal with converse roles. Additionally, we extend the result to ALCQIR, which extends ALCQI by role intersections. This solves an open problem from [DLNN97]. The result for ALCQI has already been presented in the seperate technical report [Tob99b]. In this report we use the same techniques to obtain the stronger result for ALCQIR.

This paper compares two approaches for deriving subsumption algorithms for the description logic ALN: structural subsumption and an automata-theoretic characterization of subsumption. It turns out that structural subsumption algorithms can be seen as special implementations of the automata-theoretic characterization.

We extend different Description Logics by concrete domains (such as integers and reals) and by aggregation functions over these domains (such as min,max,count,sum), which are usually available in database systems. We present decision procedures for the inference problems satisfiability for these Logics-provided that the concrete domain is not too expressive. An example of such a concrete domain is the set of (nonnegative) integers with comparisons (=,≤, ≤n, ...) and the aggregation functions min, max, count. / This is a new, extended version of a report with the same number. An abridged version has appeared in the Proceedings of the European Conference on Artificial Intelligence, Brighton, UK, 1998.

Aus der Einleitung: „In this paper, we reuse the representation formalism `description graph' in order to characterize subsumption of ALN-concepts. The description logic ALN allows for conjunction, valuerestrictions, number restrictions, and primitive negation. Since Classic allows for more constructors than ALN, e.g., equality restrictions an attribute chains by the constructor SAME-AS,we can confine the notion of description graphs from [BP94]. On the other hand, ALN explicitly allows for primitive negation which yields another possibility { besides conflicting number restrictions { to express inconsistency. Thus, we have to modify the notion of canonical description graphs in order to cope with inconsistent concepts in the structural characterization of subsumption. It turns out that the description graphs obtained from ALN-concepts are in fact trees. A canonical graph is a deterministic tree. The conditions required by the structural characterization of subsumption on these trees can be tested by an eficient algorithm, i.e., we obtain an algorithm deciding subsumption of C and D in time polynomial in the size of C and D. The report is structured as follows. In the preliminaries, we define syntax and semantics of the description logic ALN as well as the inference problem of subsumption. In Section 3, we introduce description graphs, the data structure our structural subsumption algorithm is working on. Besides syntax and semantics also an algorithm for translating ALN-concepts into description graphs is given. Thereafter, we present the main result of this report in Section 6, a characterization of subsumption of ALN-concepts by a structural comparison of corresponding description graphs. Furthermore, a structural subsumption algorithm can be found in Section 6.2. In the last section we summarize our results and give an outlook to further applications of structural subsumption in terminological knowledge representation systems.