Module extraction is an important reasoning task, aiding in the design, reuse and maintenance of ontologies. Reasoning services such as subsumption testing and MinA extraction have been shown to bene t from module extraction methods. Though various syntactic traversal-based module extraction algorithms exist for extracting modules, many only consider the subsumee of a subsumption statement as a selection criterion for reducing the axioms in the module. In this dissertation we extend the bottom-up reachability-based module extraction heuristic for the inexpressive Description Logic EL, by introducing a top-down version of the heuristic which utilises the subsumer of a subsumption statement as a selection criterion to minimize the number of axioms in a module. Then a combined bidirectional heuristic is introduced which uses both operands of a subsumption statement in order to extract very small modules. We then investigate the relationship between MinA extraction and bidirectional reachabilitybased module extraction. We provide empirical evidence that bidirectional reachability-based module extraction for subsumption entailments in EL provides a signi cant reduction in the size of modules for almost no additional costs in the running time of the original algorithms. / Computer Science / M. Sc. (Computer Science)

Ο Παγκόσμιος Ιστός έχει αλλάξει τον τρόπο που οι άνθρωποι επικοινωνούν μεταξύ τους καθώς και τον τρόπο με τον οποίο οι επιχειρήσεις διευθύνονται. Ως επέκταση του παγκόσμιου ιστού εμφανίζεται ο Σημασιολογικός Ιστός. Ο Σημασιολογικός Ιστός είναι ειδικότερα, ένας Ιστός από πληροφορίες που είναι δυνατό να διαβαστούν από τις μηχανές και η έννοια των οποίων είναι σαφώς καθορισμένη από πρότυπα. Στόχος της διπλωματική αυτής είναι η επέκταση και η εμβάθυνση σε θεμελιώδεις έννοιες του Σημασιολογικού Ιστού και η σύνδεση του με τις ΤΠΕ στην εκπαίδευση. Στα παρακάτω κεφάλαια προσεγγίζεται αναλυτικά η έννοια του Σημασιολογικού Ιστού, καθώς επίσης και οι βασικές γλώσσες σήμανσης του οι οποίες είναι: 1. Η γλώσσα σήμανσης XML, μια γλώσσα που επιτρέπει τη γραφή δομημένων εγγράφων ιστού με ένα καθορισμένο από το χρήστη λεξιλόγιο. 2. Tο Resource Description Framework (RDF) που είναι ένα πλαίσιο για την αντιπροσώπευση των πληροφοριών στον Παγκόσμιο Ιστό, όπου αναλύονται οι βασικές έννοιες που χρησιμοποιεί όπως το γραφικό μοντέλο δεδομένων, λεξιλόγιο βασισμένο στο URI, τύποι δεδομένων κ.α. 3. Το λεξιλόγιο καθορισμού του RDF (RDF Schema), που καθορίζει τις κλάσεις και τις ιδιότητες που μπορούν να χρησιμοποιηθούν για να περιγράψουν κλάσεις, ιδιότητες και άλλες πηγές. Σε επόμενο κεφάλαιο εισάγουμε στον αναγνώστη τον όρο της οντολογίας. Αναλύουμε το τι είναι οντολογία, τις κύριες λειτουργίες των οντολογιών, και προτείνεται ένα περίγραμμα για την κατασκευή των οντολογιών. Ξεχωριστή αναφορά γίνεται στο Ontology Inference Layer OIL που είναι μια πρόταση για ένα βασισμένο στον Ιστό στρώμα αντιπροσώπευσης και συμπεράσματος των οντολογιών. Επίσης γίνεται αναφορά στη βασική ιδέα σχεδιασμού του OIL που είναι το onion model του. Ακολούθως, αναλύουμε τον τρόπο με τον οποίο συντάσσεται μια οντολογία στη γλώσσα OIL. Ως συνέχεια του παραπάνω εμφανίζεται η DAML+OIL, που είναι μια σημασιολογική γλώσσα για τις πηγές του Ιστού. Στηρίζεται στα πρότυπα του W3C όπως το RDF και το RDF Schema, και επεκτείνει αυτές τις γλώσσες με ακόμα πιο πλούσιες αρχές διαμόρφωσης. Στη συνέχεια προσεγγίζουμε εκτενώς την Web Ontology Language OWL που είναι μια σημασιολογική γλώσσα σήμανσης για την έκδοση και τη διανομή των οντολογιών στον Παγκόσμιο Ιστό. Η σύνδεση του σημασιολογικού ιστού με την εκπαίδευση είναι το θέμα που αναλύεται παρακάτω με τίτλο Εκπαιδευτικός Σημασιολογικός Ιστός και γίνεται εκτενής αναφορά στις προκλήσεις και τις προοπτικές που διαφαίνονται. Η σύνδεση αυτή γίνεται με το προσαρμοστικό WBES. Ακόμα, εξετάζουμε μερικά σενάρια εφαρμογής του εκπαιδευτικού Σημασιολογικού Ιστού όπως την βασισμένη στη σημασιολογία αναζήτηση για εκπαιδευτικό περιεχόμενο, την περιήγηση στη γνώση ή «προσωπικές πύλες», τα βασισμένα στη σημασιολογία μαθήματα και τις εκπαιδευτικές υπηρεσίες σημασιολογικού ιστού. Τέλος, αναφέρουμε με συντομία εφαρμογές εκπαίδευσης βασισμένες σε οντολογίες όπως το πρόγραμμα CIPHER, το πρόγραμμα Connexions κ.α. / -

Thesis (Ph. D.)--Mechanical Engineering, Georgia Institute of Technology, 2007. / Nelson Baker, Committee Member ; Charles Eastman, Committee Member ; Christiaan Paredis, Committee Member ; Janet Allen, Committee Member ; David Rosen, Committee Chair.

Module extraction is an important reasoning task, aiding in the design, reuse and maintenance of ontologies. Reasoning services such as subsumption testing and MinA extraction have been shown to bene t from module extraction methods. Though various syntactic traversal-based module extraction algorithms exist for extracting modules, many only consider the subsumee of a subsumption statement as a selection criterion for reducing the axioms in the module. In this dissertation we extend the bottom-up reachability-based module extraction heuristic for the inexpressive Description Logic EL, by introducing a top-down version of the heuristic which utilises the subsumer of a subsumption statement as a selection criterion to minimize the number of axioms in a module. Then a combined bidirectional heuristic is introduced which uses both operands of a subsumption statement in order to extract very small modules. We then investigate the relationship between MinA extraction and bidirectional reachabilitybased module extraction. We provide empirical evidence that bidirectional reachability-based module extraction for subsumption entailments in EL provides a signi cant reduction in the size of modules for almost no additional costs in the running time of the original algorithms. / Computer Science / M. Sc. (Computer Science)

The thesis investigates methods for uniform interpolation in expressive description logics. Description logics are formalisms commonly used to model ontologies. Ontologies store terminological information and are used in a wide range of applications, such as the semantic web, medicine, bio-informatics, software development, data bases and language processing. Uniform interpolation eliminates terms from an ontology such that logical entailments in the remaining language are preserved. The result, the uniform interpolant, is a restricted view of the ontology that can be used for a variety of tasks such as ontology analysis, ontology reuse, ontology evolution and information hiding. Uniform interpolation for description logics has only gained an interest in the research community in the last years, and theoretical results show that it is a hard problem requiring specialised reasoning approaches. We present a range of uniform interpolation methods that can deal with expressive description logics such as ALC and many of its extensions. For all these logics, these are the first methods that are able to compute uniform interpolants for all inputs. The methods are based a new family of saturation-based reasoning methods, which make it possible to eliminate symbols in a goal-oriented manner. The practicality of this approach is shown by an evaluation on realistic ontologies.

No description available.

Problem: The process planning task for a given design problem in additive manufacturing can be greatly enhanced by referencing previously developed process plans. However, identifying appropriate process plans for the given design problem requires appropriate mapping between the design domain and the process planning domain. Hence, the objective of this research is to establish mathematical mapping between the design domain and the process planning domain such that the previously developed appropriate process plans can be identified for the given design task. Further more, identification of an appropriate mathematical theory that enables computational mapping between the two domains is of interest. Through such computational mapping, previously developed process plans are expected to be shared in a distributed environment using an open repository. Approach: The design requirements and process plans are discretized using empirical models that compute exact values of process variables for the given design requirements. Through this discretization, subsumption relations among the discretized design requirements and process plans are identified. Appropriate process plans for a given design requirement are identified by subsumption relations in the design requirements. Also, the design requirements that can be satisfied by the given process plans are identified by subsumption relations among the process plans. To computationally realize such mapping, a description logic (ALE) is identified and justified to represent and compute subsumption relation. Based on this investigation, a retrieval method (DFM framework) is realized that enables storage and retrieval of process plans. Validation: Theoretical and empirical validations are performed using the validation square method. For the theoretical validation, an appropriate description logic (ALE) is identified and justified. Also, subsumption utilization in mapping two domains and realizing the DFM framework is justified. For the empirical validation, the storing and retrieval performance of the DFM framework is tested to demonstrate its theoretical validity. Contribution: In this research, two areas of contributions are identified: DFM and engineering information management. In DFM, the retrieval method that relates the design problem to appropriate process plans through mathematical mapping between design and process planning domain is the major contribution. In engineering information management, the major contributions are the development of information models and the identification of their characteristics. Based on this investigation, an appropriate description logic (ALE) is selected and justified. Also, corresponding computational feasibility (non deterministic polynomial time) of subsumption is identified.

Description Logics (DLs) are a family of logic-based knowledge representation languages used to describe the knowledge of an application domain and reason about it in formally well-defined way. They allow users to describe the important notions and classes of the knowledge domain as concepts, which formalize the necessary and sufficient conditions for individual objects to belong to that concept. A variety of different DLs exist, differing in the set of properties one can use to express concepts, the so-called concept constructors, as well as the set of axioms available to describe the relations between concepts or individuals. However, all classical DLs have in common that they can only express exact knowledge, and correspondingly only allow exact inferences. Either we can infer that some individual belongs to a concept, or we can't, there is no in-between. In practice though, knowledge is rarely exact. Many definitions have their exceptions or are vaguely formulated in the first place, and people might not only be interested in exact answers, but also in alternatives that are "close enough". This thesis is aimed at tackling how to express that something "close enough", and how to integrate this notion into the formalism of Description Logics. To this end, we will use the notion of similarity and dissimilarity measures as a way to quantify how close exactly two concepts are. We will look at how useful measures can be defined in the context of DLs, and how they can be incorporated into the formal framework in order to generalize it. In particular, we will look closer at two applications of thus measures to DLs: Relaxed instance queries will incorporate a similarity measure in order to not just give the exact answer to some query, but all answers that are reasonably similar. Prototypical definitions on the other hand use a measure of dissimilarity or distance between concepts in order to allow the definitions of and reasoning with concepts that capture not just those individuals that satisfy exactly the stated properties, but also those that are "close enough".

Description logics (DLs) are knowledge representation languages that provide the theoretical underpinning for modern ontology languages such as OWL and serve as the basis for the development of ontology reasoners and tools. Most modern ontology reasoners are based on optimized tableau algorithms, which perform reasoning by trying to build counter-models. More recently, another kind of reasoning algorithms has been introduced that, instead of building counter-models, directly derive logical consequences of axioms in the ontology using inference rules. Such consequence-based algorithms were first introduced for the EL family of DLs, and later extended to more expressive Horn DLs. However, up until now, consequence-based algorithms could not handle non-Horn features such as disjunctions. We consider several complementary aspects of consequence-based reasoning in this thesis. Firstly, we describe the parallelized consequence-based reasoner ELK, which is currently the fastest reasoner for EL ontologies. Secondly, we demonstrate how consequence-based algorithms can be extended to handle disjunctions using inference rules reminiscent of ordered resolution. Finally, we combine our consequence-based framework with methods based on tree decompositions, and thus obtain what we believe are the first fixed-parameter tractability results for subsumption reasoning in DLs.

We consider the overlap between reasoning involved in <em>conjunctive query optimization</em> (CQO) and in tableaux-based approaches to reasoning about subsumption in <em>description logics</em> (DLs). In both cases, an underlying graph is created, searched and modified. This process is determined by a given <em>query</em> and <em>database schema</em> in the first case and by a given <em>description</em> and <em>terminology</em> in the second. The opportunities for overlap derive from an abundance of reductions of various schema languages to terminologies for common DL dialects, and from the fact that descriptions can in turn be viewed as queries that compute a single column. <br /><br /> Our main contributions are as follows. We present the design and implementation of a common graph utility that integrates the requirements for both CQO and DL reasoning. We then verify this model by also presenting the design and implementation for two drivers, one that implements a query optimizer for a conjunctive query language extended with descriptions, and one that implements a complete DL reasoner for a feature based DL dialect.