Carbotta, D. (2010). A practical automata-based technique for reasoning in expressive description logics [Diploma Thesis, Technische Universität Wien]. reposiTUm. http://hdl.handle.net/20.500.12708/160856
Description Logics are a well-established family of languages designed for knowledge representation and reasoning. Thanks to the balance they provide between expressivity and computational efficiency, they have gained acceptance in several areas, such as information integration, bioinformatics, software engineering. The reasoning requirements arising in these different scenarios have stimulated many paths of research. In this work we will take advantage of specific properties of a wide range of Description Logics, the tree model property.This property makes it possible to reduce DL reasoning problems to verifying certain properties of an automaton over infinite trees. Many worst-case optimal algorithms have been obtained using this technique; however, their practicality is questioned because they usually involve costly computations on very large objects. The goal of this thesis is to help overcome these hurdles, designing and implementing a new automata-based procedure for reasoning over expressive Description Logics that is worst-case optimal and lends itself to an efficient implementation. In order to show the feasibility of the approach, we have realized a working prototype of a reasoner based upon these techniques. An experimental evaluation of this prototype shows encouraging results.
