Diplomarbeiten und Masterarbeiten

Description logics (DLs) are a family of formal knowl- edge representation languages used in artificial intelligence to describe and reason about the concepts of an application domain. In particular, they are providing formalization for ontologies and the semantic web. The most specific concept (msc) is an inference task that can support the bottom-up construction of knowledge bases in description logics. The most specific concept of an individual is the least concept that has this individual as an instance. In description logics which contain existential restrictions, the most specific concept does not always exist in the case of acyclic ABoxes. However, the latest results show that the existence of the msc w.r.t. an individual can be decided in polynomial time. Also, the role-depth of these most specific generalizations is polynomially bounded by the size of the input, which yields a decision procedure for the existence problem. The polynomial bound can be used to compute the msc if it exists. Otherwise, the computed concept can still serve as an approximation. However, computing the msc could take at least exponential time if the msc is exponentially large. Also, the previous approach does not make it clear how to compute the most specific concept in practice. First, we revisit the previous approach for constructing the msc of an individual w.r.t. a general EL-TBox. We present a new method for tree unravelling of an interpretation and introduce a characteristic concept w.r.t. the least tree unravelling. Moreover, we provide a new approach and an algorithm to decide the existence of the msc in polynomial time without relying on computing the concept. Then, one can compute the actual msc in exponential time. Finally, we provide an experimental evaluation to state that the concept constructed from the new approach has a smaller bound than the bound of the concept constructed from the previous approach.

@thesis{ Nad-22,
  address = {Dresden, Germany},
  author = {Mohamed {Nadeem}},
  school = {Technische Universit{\"a}t Dresden},
  title = {A Polynomial Approach for Finding Most Specific Concepts w.r.t General {$\mathcal{EL}$}-TBoxes},
  type = {Master's Thesis},
  year = {2022},
}

In the research field of Description Logics (DLs) checking satisfiability of ALCQ has been investigated thoroughly and is therefore well-known. The DL ALCSCC extends ALCQ with constraints over role successors using quantifier-free fragments (QF) of Boolean Algebra (BA) and Presburger Arithmetics (PA). Checking satisfiability of this DL has been proven to be decidable and PSpace-complete. In this work we provide a tableau algorithm to check satisfiability of ALCSCC concepts and prove its correctness.

@thesis{ Khy-21,
  address = {Dresden, Germany},
  author = {Ryny {Khy}},
  school = {Technische Universit{\"a}t Dresden},
  title = {A Tableau Algorithm for the Numerical Description Logic {$\mathcal{ALCSCC}$}},
  type = {Master's Thesis},
  year = {2021},
}

Recent research in the field of Description Logic (DL) investigated the complexity of the satisfiability problem for description logics that are obtained by enriching the well-known DL ALCQ with more complex set and cardinality constraints over role successors. The algorithms that have been proposed so far, despite providing worst-case optimal decision procedures for the concept satisfiability problem (both without and with a terminology) lack the efficiency needed to obtain usable implementations. In particular, the algorithm for the case without terminology is non-deterministic and the one for the case with a terminology is also best-case exponential. The goal of this thesis is to use well-established techniques from the field of numerical optimization, such as column generation, in order to obtain more practical algorithms. As a starting point, efficient approaches for dealing with counting quantifiers over unary predicates based on SAT-based column generation should be considered.

@thesis{ DeBo-Mas-19,
  address = {Dresden, Germany},
  author = {Filippo {De Bortoli}},
  school = {Technische Universit\"{a}t Dresden},
  title = {Integrating Reasoning Services for Description Logics with Cardinality Constraints with Numerical Optimization Techniques},
  type = {Master's Thesis},
  year = {2019},
}

@thesis{ Schramm-18,
  address = {Dresden, Germany},
  author = {Falk {Schramm}},
  school = {Technische Universit{\"a}t Dresden},
  title = {Simulation von P-Systemen},
  type = {Master's Thesis},
  year = {2018},
}

Generalizations of a collection of concepts can be computed by the least common subsumer (lcs) which is a useful inference for building knowledge bases. For general FL0-TBoxes the lcs need not exist. In this thesis, we devise a condition to check whether a concept is the lcs of two concepts w.r.t. a general FL0-TBox. We also define the characterizations for the existence of the lcs. Last, we show that if the lcs exists, then we can compute the lcs and the upper bound for the role-depth of the lcs.

@thesis{ Nur-Mas-16,
  address = {Dresden, Germany},
  author = {Adrian {Nuradiansyah}},
  school = {Technische Universit\"{a}t Dresden},
  title = {Algorithms for Computing Least Common Subsumers w.r.t. General FL0-TBoxes},
  type = {Master's Thesis},
  year = {2016},
}