Research projects

The application of automated reasoning approaches to Description Logic (DL) ontologies may produce certain consequences that either are deemed to be wrong or should be hidden for privacy reasons. The question is then how to repair the ontology such that the unwanted consequences can no longer be deduced. An optimal repair is one where the least amount of other consequences is removed. Most of the previous approaches to ontology repair are of a syntactic nature in that they remove or weaken the axioms explicitly present in the ontology, and thus cannot achieve semantic optimality. In previous work, we have addressed the problem of computing optimal repairs of (quantified) ABoxes, where the unwanted consequences are described by concept assertions of the light-weight DL \(\mathcal{EL}\). In the present paper, we improve on the results achieved so far in two ways. First, we allow for the presence of terminological knowledge in the form of an \(\mathcal{EL}\) TBox. This TBox is assumed to be static in the sense that it cannot be changed in the repair process. Second, the construction of optimal repairs described in our previous work is best case exponential. We introduce an optimized construction that is exponential only in the worst case. First experimental results indicate that this reduces the size of the computed optimal repairs considerably.

@techreport{ BaKoKrNu-LTCS-21-01,
  address = {Dresden, Germany},
  author = {Franz {Baader} and Patrick {Koopmann} and Francesco {Kriegel} and Adrian {Nuradiansyah}},
  institution = {Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universit{\"a}t Dresden},
  number = {21-01},
  title = {Computing Optimal Repairs of Quantified ABoxes w.r.t. Static {$\mathcal{EL}$} TBoxes (Extended Version)},
  type = {LTCS-Report},
  year = {2021},
}

In recent work, we have shown how to compute compliant anonymizations of quantified ABoxes w.r.t. \(\mathcal{E\!L}\) policies. In this setting, quantified ABoxes can be used to publish information about individuals, some of which are anonymized. The policy is given by concepts of the Description Logic (DL) \(\mathcal{E\!L}\), and compliance means that one cannot derive from the ABox that some non-anonymized individual is an instance of a policy concept. If one assumes that a possible attacker could have additional knowledge about some of the involved non-anonymized individuals, then compliance with a policy is not sufficient. One wants to ensure that the quantified ABox is safe in the sense that none of the secret instance information is revealed, even if the attacker has additional compliant knowledge. In the present paper, we show that safety can be decided in polynomial time, and that the unique optimal safe anonymization of a non-safe quantified ABox can be computed in exponential time, provided that the policy consists of a single \(\mathcal{E\!L}\) concept.

@inproceedings{ BaKrNuPe-SAC2021,
  author = {Franz {Baader} and Francesco {Kriegel} and Adrian {Nuradiansyah} and Rafael {Pe{\~n}aloza}},
  booktitle = {Proceedings of the 36th ACM/SIGAPP Symposium on Applied Computing (SAC 2021)},
  doi = {https://doi.org/10.1145/3412841.3441961},
  note = {To appear.},
  title = {{Safety of Quantified ABoxes w.r.t.\ Singleton $\mathcal{E\!L}$ Policies}},
  year = {2021},
}

We adapt existing approaches for privacy-preserving publishing of linked data to a setting where the data are given as Description Logic (DL) ABoxes with possibly anonymised (formally: existentially quantified) individuals and the privacy policies are expressed using sets of concepts of the DL \(\mathcal{E\!L}\). We provide a chacterization of compliance of such ABoxes w.r.t. \(\mathcal{E\!L}\) policies, and show how optimal compliant anonymisations of ABoxes that are non-compliant can be computed. This work extends previous work on privacy-preserving ontology publishing, in which a very restricted form of ABoxes, called instance stores, had been considered, but restricts the attention to compliance. The approach developed here can easily be adapted to the problem of computing optimal repairs of quantified ABoxes.

@techreport{ BaKrNuPe-LTCS-20-08,
  address = {Dresden, Germany},
  author = {Franz {Baader} and Francesco {Kriegel} and Adrian {Nuradiansyah} and Rafael {Pe\~{n}aloza}},
  institution = {Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universit{\"a}t Dresden},
  number = {20-08},
  title = {Computing Compliant Anonymisations of Quantified ABoxes w.r.t. $\mathcal{E\!L}$ Policies (Extended Version)},
  type = {LTCS-Report},
  year = {2020},
}

In recent work, we have shown how to compute compliant anonymizations of quantified ABoxes w.r.t. \(\mathcal{E\!L}\) policies. In this setting, quantified ABoxes can be used to publish information about individuals, some of which are anonymized. The policy is given by concepts of the Description Logic (DL) \(\mathcal{E\!L}\), and compliance means that one cannot derive from the ABox that some non-anonymized individual is an instance of a policy concept. If one assumes that a possible attacker could have additional knowledge about some of the involved non-anonymized individuals, then compliance with a policy is not sufficient. One wants to ensure that the quantified ABox is safe in the sense that none of the secret instance information is revealed, even if the attacker has additional compliant knowledge. In the present paper, we show that safety can be decided in polynomial time, and that the unique optimal safe anonymization of a non-safe quantified ABox can be computed in exponential time, provided that the policy consists of a single \(\mathcal{E\!L}\) concept.

@techreport{ BaKrNuPe-LTCS-20-09,
  address = {Dresden, Germany},
  author = {Franz {Baader} and Francesco {Kriegel} and Adrian {Nuradiansyah} and Rafael {Pe\~{n}aloza}},
  institution = {Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universit{\"a}t Dresden},
  number = {20-09},
  title = {Computing Safe Anonymisations of Quantified ABoxes w.r.t.\ $\mathcal{E\!L}$ Policies (Extended Version)},
  type = {LTCS-Report},
  year = {2020},
}

We adapt existing approaches for privacy-preserving publishing of linked data to a setting where the data are given as Description Logic (DL) ABoxes with possibly anonymised (formally: existentially quantified) individuals and the privacy policies are expressed using sets of concepts of the DL \(\mathcal{E\!L}\). We provide a chacterization of compliance of such ABoxes w.r.t. \(\mathcal{E\!L}\) policies, and show how optimal compliant anonymisations of ABoxes that are non-compliant can be computed. This work extends previous work on privacy-preserving ontology publishing, in which a very restricted form of ABoxes, called instance stores, had been considered, but restricts the attention to compliance. The approach developed here can easily be adapted to the problem of computing optimal repairs of quantified ABoxes.

@inproceedings{ BaKrNuPe-ISWC2020,
  author = {Franz {Baader} and Francesco {Kriegel} and Adrian {Nuradiansyah} and Rafael {Pe{\~n}aloza}},
  booktitle = {Proceedings of the 19th International Semantic Web Conference (ISWC 2020), Part {I}, Athens, Greece, November 2-6, 2020},
  doi = {https://doi.org/10.1007/978-3-030-62419-4_1},
  editor = {Jeff Z. {Pan} and Valentina A. M. {Tamma} and Claudia {d'Amato} and Krzysztof {Janowicz} and Bo {Fu} and Axel {Polleres} and Oshani {Seneviratne} and Lalana {Kagal}},
  pages = {3--20},
  publisher = {Springer},
  series = {Lecture Notes in Computer Science},
  title = {{Computing Compliant Anonymisations of Quantified ABoxes w.r.t. $\mathcal{E\!L}$ Policies}},
  volume = {12506},
  year = {2020},
}

We make a first step towards adapting an existing approach for privacy-preserving publishing of linked data to Description Logic (DL) ontologies. We consider the case where both the knowledge about individuals and the privacy policies are expressed using concepts of the DL \(\mathcal{EL}\), which corresponds to the setting where the ontology is an \(\mathcal{EL}\) instance store. We introduce the notions of compliance of a concept with a policy and of safety of a concept for a policy, and show how optimal compliant (safe) generalizations of a given \(\mathcal{EL}\) concept can be computed. In addition, we investigate the complexity of the optimality problem.

@techreport{ BaKrNu-LTCS-19-01,
  address = {Dresden, Germany},
  author = {Franz {Baader} and Francesco {Kriegel} and Adrian {Nuradiansyah}},
  institution = {Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universit{\"a}t Dresden},
  note = {\url{https://tu-dresden.de/inf/lat/reports#BaKrNu-LTCS-19-01}},
  number = {19-01},
  title = {{Privacy-Preserving Ontology Publishing for $\mathcal{EL}$ Instance Stores (Extended Version)}},
  type = {LTCS-Report},
  year = {2019},
}

We make a first step towards adapting an existing approach for privacy-preserving publishing of linked data to Description Logic (DL) ontologies. We consider the case where both the knowledge about individuals and the privacy policies are expressed using concepts of the DL \(\mathcal{EL}\), which corresponds to the setting where the ontology is an \(\mathcal{EL}\) instance store. We introduce the notions of compliance of a concept with a policy and of safety of a concept for a policy, and show how optimal compliant (safe) generalizations of a given \(\mathcal{EL}\) concept can be computed. In addition, we investigate the complexity of the optimality problem.

@inproceedings{ BaKrNu-JELIA19,
  author = {Franz {Baader} and Francesco {Kriegel} and Adrian {Nuradiansyah}},
  booktitle = {16th European Conference on Logics in Artificial Intelligence, {JELIA} 2019, Rende, Italy, May 7-11, 2019, Proceedings},
  doi = {https://dx.doi.org/10.1007/978-3-030-19570-0_21},
  editor = {Francesco {Calimeri} and Nicola {Leone} and Marco {Manna}},
  pages = {323--338},
  publisher = {Springer},
  series = {Lecture Notes in Computer Science},
  title = {{Privacy-Preserving Ontology Publishing for $\mathcal{EL}$ Instance Stores}},
  volume = {11468},
  year = {2019},
}

In previous work, we have investigated privacy-preserving publishing of Description Logic (DL) ontologies in a setting where the knowledge about individuals to be published is an \(\mathcal{EL}\) instance store, and both the privacy policy and the possible background knowledge of an attacker are represented by concepts of the DL \(\mathcal{EL}\). We have introduced the notions of compliance of a concept with a policy and of safety of a concept for a policy, and have shown how, in the context mentioned above, optimal compliant (safe) generalizations of a given \(\mathcal{EL}\) concept can be computed. In the present paper, we consider a modified setting where we assume that the background knowledge of the attacker is given by a DL different from the one in which the knowledge to be published and the safety policies are formulated. In particular, we investigate the situations where the attacker’s knowledge is given by an \(\mathcal{FL}_0\) or an \(\mathcal{FLE}\) concept. In both cases, we show how optimal safe generalizations can be computed. Whereas the complexity of this computation is the same (ExpTime) as in our previous results for the case of \(\mathcal{FL}_0\), it turns out to be actually lower (polynomial) for the more expressive DL \(\mathcal{FLE}\).

@inproceedings{ BaNu-KI19,
  author = {Franz {Baader} and Adrian {Nuradiansyah}},
  booktitle = {KI 2019: Advances in Artificial Intelligence - 42nd German Conference on AI, Kassel, Germany, September 23 - 26, 2019, Proceedings},
  doi = {https://dx.doi.org/10.1007/978-3-030-30179-8_7},
  editor = {Christoph {Benzm{\"u}ller} and Heiner {Stuckenschmidt}},
  pages = {87--100},
  publisher = {Springer},
  series = {Lecture Notes in Computer Science},
  title = {Mixing Description Logics in Privacy-Preserving Ontology Publishing},
  volume = {11793},
  year = {2019},
}

@inproceedings{ BaKrNuPe-DL2018,
  author = {Franz {Baader} and Francesco {Kriegel} and Adrian {Nuradiansyah} and Rafael {Pe{\~n}aloza}},
  booktitle = {Proceedings of the 31st International Workshop on Description Logics, Tempe, Arizona, October 27-29, 2018},
  editor = {Magdalena {Ortiz} and Thomas {Schneider}},
  publisher = {CEUR-WS.org},
  series = {{CEUR} Workshop Proceedings},
  title = {{Making Repairs in Description Logics More Gentle (Extended Abstract)}},
  volume = {2211},
  year = {2018},
}

The classical approach for repairing a Description Logic ontology \(\mathfrak{O}\) in the sense of removing an unwanted consequence \(\alpha\) is to delete a minimal number of axioms from \(\mathfrak{O}\) such that the resulting ontology \(\mathfrak{O}'\) does not have the consequence \(\alpha\). However, the complete deletion of axioms may be too rough, in the sense that it may also remove consequences that are actually wanted. To alleviate this problem, we propose a more gentle notion of repair in which axioms are not deleted, but only weakened. On the one hand, we investigate general properties of this gentle repair method. On the other hand, we propose and analyze concrete approaches for weakening axioms expressed in the Description Logic \(\mathcal{E\mkern-1.618mu L}\).

@inproceedings{ BaKrNuPe-KR2018,
  address = {USA},
  author = {Franz {Baader} and Francesco {Kriegel} and Adrian {Nuradiansyah} and Rafael {Pe{\~n}aloza}},
  booktitle = {Principles of Knowledge Representation and Reasoning: Proceedings of the Sixteenth International Conference, {KR} 2018, Tempe, Arizona, 30 October - 2 November 2018},
  editor = {Frank {Wolter} and Michael {Thielscher} and Francesca {Toni}},
  pages = {319--328},
  publisher = {{AAAI} Press},
  title = {{Making Repairs in Description Logics More Gentle}},
  year = {2018},
}

The classical approach for repairing a Description Logic ontology \(\mathfrak{O}\) in the sense of removing an unwanted consequence \(\alpha\) is to delete a minimal number of axioms from \(\mathfrak{O}\) such that the resulting ontology \(\mathfrak{O}'\) does not have the consequence \(\alpha\). However, the complete deletion of axioms may be too rough, in the sense that it may also remove consequences that are actually wanted. To alleviate this problem, we propose a more gentle way of repair in which axioms are not necessarily deleted, but only weakened. On the one hand, we investigate general properties of this gentle repair method. On the other hand, we propose and analyze concrete approaches for weakening axioms expressed in the Description Logic \(\mathcal{E\mkern-1.618mu L}\).

@techreport{ BaKrNuPe-LTCS-18-01,
  address = {Dresden, Germany},
  author = {Franz {Baader} and Francesco {Kriegel} and Adrian {Nuradiansyah} and Rafael {Pe\~{n}aloza}},
  institution = {Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universit{\"a}t Dresden},
  note = {\url{https://tu-dresden.de/inf/lat/reports#BaKrNuPe-LTCS-18-01}},
  number = {18-01},
  title = {{Repairing Description Logic Ontologies by Weakening Axioms}},
  type = {LTCS-Report},
  year = {2018},
}

We make a first step towards adapting the approach of Cuenca Grau and Kostylev for privacy-preserving publishing of linked data to Description Logic ontologies. We consider the case where both the knowledge about individuals and the privacy policies are expressed using EL concepts. We introduce the notions of compliance of a concept with a policy and of safety of a concept for a policy, and show how optimal compliant (safe) generalizations of a given EL concept can be computed.

@inproceedings{ BaNu-DL2018,
  author = {Franz {Baader} and Adrian {Nuradiansyah}},
  booktitle = {Proceedings of the 31st International Workshop on Description Logics, Tempe, Arizona, October 27-29, 2018},
  editor = {Magdalena {Ortiz} and Thomas {Schneider}},
  note = {},
  publisher = {CEUR-WS.org},
  series = {{CEUR} Workshop Proceedings},
  title = {{Towards Privacy-Preserving Ontology Publishing}},
  year = {2018},
}

Classical regular path queries (RPQs) can be too restrictive for some applications and answering such queries under approximate semantics to relax the query is desirable. While for answering regular path queries over graph databases under approximate semantics algorithms are available, such algorithms are scarce for the ontology-mediated setting. In this paper we extend an approach for answering RPQs over graph databases that uses weighted transducers to approximate paths from the query in two ways. The first extension is to answering approximate conjunctive 2-way regular path queries (C2RPQs) over graph databases and the second is to answering C2RPQs such queries over ELH and DL-LiteR ontologies. We provide results on the computational complexity of the underlying reasoning problems and devise approximate query answering algorithms.

@techreport{ FeAt-LTCS-20-05,
  address = {Dresden, Germany},
  author = {Oliver {Fern{\'a}ndez Gil} and Anni-Yasmin {Turhan}},
  institution = {Chair for Automata Theory, Institute for Theoretical Computer Science, Technische Universit{\"a}t Dresden},
  note = {See http://lat.inf.tu-dresden.de/research/reports.html},
  number = {20-05},
  title = {Answering Regular Path Queries Under Approximate Semantics in Lightweight Description Logics},
  type = {LTCS-Report},
  year = {2020},
}

Matching concept descriptions against concept patterns was introduced as a new inference task in Description Logics two decades ago, motivated by applications in the Classic system. Shortly afterwards, a polynomial-time matching algorithm was developed for the DL FL0. However, this algorithm cannot deal with general TBoxes (i.e., finite sets of general concept inclusions). Here we show that matching in FL0 w.r.t. general TBoxes is in ExpTime, which is the best possible complexity for this problem since already subsumption w.r.t. general TBoxes is ExpTime-hard in FL0. We also show that, w.r.t. a restricted form of TBoxes, the complexity of matching in FL0 can be lowered to PSpace.

@inproceedings{ BaFeMa-DL19,
  author = {Franz {Baader} and Oliver {Fern\'andez Gil} and Pavlos {Marantidis}},
  booktitle = {Proceedings of the 32nd International Workshop on Description Logics (DL'19)},
  editor = {Mantas {Simkus} and Grant {Weddell}},
  publisher = {CEUR-WS},
  series = {CEUR Workshop Proceedings},
  title = {Matching in the Description Logic {FL0} with respect to General TBoxes (Extended abstract)},
  volume = {2373},
  year = {2019},
}

Unification in description logics (DLs) has been introduced as a novel inference service that can be used to detect redundancies in ontologies, by finding different concepts that may potentially stand for the same intuitive notion. Together with the special case of matching, they were first investigated in detail for the DL FL0, where these problems can be reduced to solving certain language equations. In this thesis, we extend this service in two directions. In order to increase the recall of this method for finding redundancies, we introduce and investigate the notion of approximate unification, which basically finds pairs of concepts that “almost” unify, in order to account for potential small modelling errors. The meaning of “almost” is formalized using distance measures between concepts. We show that approximate unification in FL0 can be reduced to approximately solving language equations, and devise algorithms for solving the latter problem for particular distance measures. Furthermore, we make a first step towards integrating background knowledge, formulated in so-called TBoxes, by investigating the special case of matching in the presence of TBoxes of different forms. We acquire a tight complexity bound for the general case, while we prove that the problem becomes easier in a restricted setting. To achieve these bounds, we take advantage of an equivalence characterization of FL0 concepts that is based on formal languages. In addition, we incorporate TBoxes in computing concept distances. Even though our results on the approximate setting cannot deal with TBoxes yet, we prepare the framework that future research can build on. Before we journey to the technical details of the above investigations, we showcase our program in the simpler setting of the equational theory ACUI, where we are able to also combine the two extensions. In the course of studying the above problems, we make heavy use of automata theory, where we also derive novel results that could be of independent interest.

@thesis{ Marantidis-Diss-2019,
  address = {Dresden, Germany},
  author = {Pavlos {Marantidis}},
  school = {Technische Universit\"{a}t Dresden},
  title = {Quantitative Variants of Language Equations and their Applications to Description Logics},
  type = {Doctoral Thesis},
  year = {2019},
}

Matching concept descriptions against concept patterns was introduced as a new inference task in Description Logics two decades ago, motivated by applications in the Classic system. Shortly afterwards, a polynomial-time matching algorithm was developed for the DL FL0. However, this algorithm cannot deal with general TBoxes (i.e., finite sets of general concept inclusions). Here we show that matching in FL0 w.r.t. general TBoxes is in ExpTime, which is the best possible complexity for this problem since already subsumption w.r.t. general TBoxes is ExpTime-hard in FL0. We also show that, w.r.t. a restricted form of TBoxes, the complexity of matching in FL0 can be lowered to PSpace.

@inproceedings{ BaFeMa18-LPAR,
  author = {Franz {Baader} and Oliver {Fern\'andez Gil} and Pavlos {Marantidis}},
  booktitle = {LPAR-22. 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning},
  doi = {https://dx.doi.org/10.29007/q74p},
  editor = {Gilles {Barthe} and Geoff {Sutcliffe} and Margus {Veanes}},
  pages = {76--94},
  publisher = {EasyChair},
  series = {EPiC Series in Computing},
  title = {Matching in the Description Logic $\mathcal{FL}_0$ with respect to General TBoxes},
  volume = {57},
  year = {2018},
}

In contrast to qualitative linear temporal logics, which can be used to state that some property will eventually be satisfied, metric temporal logics allow us to formulate constraints on how long it may take until the property is satisfied. While most of the work on combining description logics (DLs) with temporal logics has concentrated on qualitative temporal logics, there is a growing interest in extending this work to the quantitative case. In this article, we complement existing results on the combination of DLs with metric temporal logics by introducing interval-rigid concept and role names. Elements included in an interval-rigid concept or role name are required to stay in it for some specified amount of time. We investigate several combinations of (metric) temporal logics with ALC by either allowing temporal operators only on the level of axioms or also applying them to concepts. In contrast to most existing work on the topic, we consider a timeline based on the integers and also allow assertional axioms. We show that the worst-case complexity does not increase beyond the previously known bound of 2-ExpSpace and investigate in detail how this complexity can be reduced by restricting the temporal logic and the occurrences of interval-rigid names.

@article{ BaBoKoOzTh-TOCL20,
  author = {Franz {Baader} and Stefan {Borgwardt} and Patrick {Koopmann} and Ana {Ozaki} and Veronika {Thost}},
  doi = {https://dx.doi.org/10.1145/3399443},
  journal = {ACM Transactions on Computational Logic},
  month = {August},
  number = {4},
  pages = {30:1--30:46},
  title = {Metric Temporal Description Logics with Interval-Rigid Names},
  volume = {21},
  year = {2020},
}

Ontology-mediated query answering is a popular paradigm for enriching answers to user queries with background knowledge. For querying the absence of information, however, there exist only few ontology-based approaches. Moreover, these proposals conflate the closed-domain and closed-world assumption, and therefore are not suited to deal with the anonymous objects that are common in ontological reasoning. Many real-world applications, like processing electronic health records (EHRs), also contain a temporal dimension, and require efficient reasoning algorithms. Moreover, since medical data is not recorded on a regular basis, reasoners must deal with sparse data with potentially large temporal gaps. Our contribution consists of three main parts: Firstly, we introduce a new closed-world semantics for answering conjunctive queries with negation over ontologies formulated in the description logic ELH⊥, which is based on the minimal universal model. We propose a rewriting strategy for dealing with negated query atoms, which shows that query answering is possible in polynomial time in data complexity. Secondly, we introduce a new temporal variant of ELH⊥ that features a convexity operator. We extend this minimal-world semantics for answering metric temporal conjunctive queries with negation over the logic and obtain similar rewritability and complexity results. Thirdly, apart from the theoretical results, we evaluate minimal-world semantics in practice by selecting patients, based on their EHRs, that match given criteria.

@thesis{ Forkel-Diss-20,
  address = {Dresden, Germany},
  author = {Walter {Forkel}},
  school = {Technische Universit\"{a}t Dresden},
  title = {Closed-World Semantics for Query Answering in Temporal Description Logics},
  type = {Doctoral Thesis},
  year = {2020},
}

Selecting patients for clinical trials is very labor-intensive. Our goal is to design (semi-)automated techniques that can support clinical researchers in this task. In this paper we summarize our recent advances towards such a system: First, we present the challenges involved when representing electronic health records and eligibility criteria for clinical trials in a formal language. Second, we introduce temporal conjunctive queries with negation as a formal language suitable to represent clinical trials. Third, we describe our methodology for automatic translation of clinical trial eligibility criteria from natural language into our query language. The evaluation of our prototypical implementation shows promising results. Finally, we talk about the parts we are currently working on and the challenges involved.

@inproceedings{ BBFKXZHQA19,
  address = {Marina del Rey, USA},
  author = {Franz {Baader} and Stefan {Borgwardt} and Walter {Forkel} and Alisa {Kovtunova} and Chao {Xu} and Beihai {Zhou}},
  booktitle = {2nd International Workshop on Hybrid Question Answering with Structured and Unstructured Knowledge (HQA'19)},
  editor = {Franz {Baader} and Brigitte {Grau} and Yue {Ma}},
  title = {Temporalized Ontology-Mediated Query Answering under Minimal-World Semantics},
  year = {2019},
}

Large-scale knowledge bases are at the heart of modern information systems. Their knowledge is inherently uncertain, and hence they are often materialized as probabilistic databases. However, probabilistic database management systems typically lack the capability to incorporate implicit background knowledge and, consequently, fail to capture some intuitive query answers. Ontology-mediated query answering is a popular paradigm for encoding commonsense knowledge, which can provide more complete answers to user queries. We propose a new data model that integrates the paradigm of ontology-mediated query answering with probabilistic databases, employing a log-linear probability model. We compare our approach to existing proposals, and provide supporting computational results.

@inproceedings{ BoCL-AAAI19,
  address = {Honolulu, USA},
  author = {Stefan {Borgwardt} and Ismail Ilkan {Ceylan} and Thomas {Lukasiewicz}},
  booktitle = {Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI'19)},
  doi = {https://doi.org/10.1609/aaai.v33i01.33012711},
  editor = {Pascal Van {Hentenryck} and Zhi-Hua {Zhou}},
  pages = {2711--2718},
  publisher = {AAAI Press},
  title = {Ontology-Mediated Query Answering over Log-linear Probabilistic Data},
  year = {2019},
}

Large-scale knowledge bases are at the heart of modern information systems. Their knowledge is inherently uncertain, and hence they are often materialized as probabilistic databases. However, probabilistic database management systems typically lack the capability to incorporate implicit background knowledge and, consequently, fail to capture some intuitive query answers. Ontology-mediated query answering is a popular paradigm for encoding commonsense knowledge, which can provide more complete answers to user queries. We propose a new data model that integrates the paradigm of ontology-mediated query answering with probabilistic databases, employing a log-linear probability model. We compare our approach to existing proposals, and provide supporting computational results.

@inproceedings{ BoCL-DL19,
  address = {Oslo, Norway},
  author = {Stefan {Borgwardt} and Ismail Ilkan {Ceylan} and Thomas {Lukasiewicz}},
  booktitle = {Proceedings of the 32nd International Workshop on Description Logics (DL'19)},
  editor = {Mantas {Simkus} and Grant {Weddell}},
  publisher = {CEUR-WS},
  series = {CEUR Workshop Proceedings},
  title = {Ontology-Mediated Query Answering over Log-linear Probabilistic Data (Abstract)},
  volume = {2373},
  year = {2019},
}

@inproceedings{ BoFo-IJCAI19,
  address = {Macao, China},
  author = {Stefan {Borgwardt} and Walter {Forkel}},
  booktitle = {Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI'19)},
  doi = {https://doi.org/10.24963/ijcai.2019/849},
  editor = {Sarit {Kraus}},
  note = {Invited contribution to Sister Conference Best Paper Track.},
  pages = {6131--6135},
  publisher = {IJCAI},
  title = {Closed-World Semantics for Conjunctive Queries with Negation over {$\mathcal{ELH}_\bot$} Ontologies},
  year = {2019},
}

Ontology-mediated query answering is a popular paradigm for enriching answers to user queries with background knowledge. For querying the absence of information, however, there exist only few ontology-based approaches. Moreover, these proposals conflate the closed-domain and closed-world assumption, and therefore are not suited to deal with the anonymous objects that are common in ontological reasoning. We propose a new closed-world semantics for answering conjunctive queries with negation over ontologies formulated in the description logic \(\mathcal{ELH}_\bot\), which is based on the minimal canonical model. We propose a rewriting strategy for dealing with negated query atoms, which shows that query answering is possible in polynomial time in data complexity.

@inproceedings{ BoFo-JELIA19,
  address = {Rende, Italy},
  author = {Stefan {Borgwardt} and Walter {Forkel}},
  booktitle = {Proc.\ of the 16th European Conf.\ on Logics in Artificial Intelligence (JELIA'19)},
  doi = {https://doi.org/10.1007/978-3-030-19570-0_24},
  editor = {Francesco {Calimeri} and Nicola {Leone} and Marco {Manna}},
  pages = {371--386},
  publisher = {Springer},
  series = {Lecture Notes in Artificial Intelligence},
  title = {Closed-World Semantics for Conjunctive Queries with Negation over {$\mathcal{ELH}_\bot$} Ontologies},
  volume = {11468},
  year = {2019},
}

Ontology-mediated-query-answering is a popular paradigm for enriching answers to user queries with background knowledge. For querying the absence of information, however, there exist only few ontology-based approaches. Moreover, these proposals conflate the closed-domain and closed-world assumption, and therefore are not suited to deal with the anonymous objects that are common in ontological reasoning. We propose a new closed-world semantics for answering conjunctive queries with negation over ontologies formulated in the description logic \(\mathcal{ELH}_\bot\), which is based on the minimal canonical model. We propose a rewriting strategy for dealing with negated query atoms, which shows that query answering is possible in polynomial time in data complexity.

@inproceedings{ BoFo-DL19,
  address = {Oslo, Norway},
  author = {Stefan {Borgwardt} and Walter {Forkel}},
  booktitle = {Proceedings of the 32nd International Workshop on Description Logics (DL'19)},
  editor = {Mantas {Simkus} and Grant {Weddell}},
  publisher = {CEUR-WS},
  series = {CEUR Workshop Proceedings},
  title = {Closed-World Semantics for Conjunctive Queries with Negation over {$\mathcal{ELH}_\bot$} Ontologies (Extended Abstract)},
  volume = {2373},
  year = {2019},
}

Lightweight temporal ontology languages have become a very active field of research in recent years. Many real-world applications, like processing electronic health records (EHRs), inherently contain a temporal dimension, and require efficient reasoning algorithms. Moreover, since medical data is not recorded on a regular basis, reasoners must deal with sparse data with potentially large temporal gaps. In this paper, we introduce a temporal extension of the tractable language ELH bottom, which features a new class of convex diamond operators that can be used to bridge temporal gaps. We develop a completion algorithm for our logic, which shows that entailment remains tractable. Based on this, we develop a minimal-world semantics for answering metric temporal conjunctive queries with negation. We show that query answering is combined first-order rewritable, and hence in polynomial time in data complexity.

@inproceedings{ BoFoKo-RRML,
  address = {Bolzano, Italy},
  author = {Stefan {Borgwardt} and Walter {Forkel} and Alisa {Kovtunova}},
  booktitle = {Proc.\ of the 3rd International Joint Conference on Rules and Reasoning (RuleML+RR'19)},
  doi = {https://dx.doi.org/10.1007/978-3-030-31095-0_1},
  editor = {Paul {Fodor} and Marco {Montali} and Diego {Calvanese} and Dumitru {Roman}},
  pages = {3--18},
  publisher = {Springer},
  series = {Lecture Notes in Computer Science},
  title = {Finding New Diamonds: {T}emporal Minimal- World Query Answering over Sparse {AB}oxes},
  volume = {11784},
  year = {2019},
}

Selecting patients for clinical trials is very labor-intensive. Our goal is to develop an automated system that can support doctors in this task. This paper describes a major step towards such a system: the automatic translation of clinical trial eligibility criteria from natural language into formal, logic-based queries. First, we develop a semantic annotation process that can capture many types of clinical trial criteria. Then, we map the annotated criteria to the formal query language. We have built a prototype system based on state-of-the-art NLP tools such as Word2Vec, Stanford NLP tools, and the MetaMap Tagger, and have evaluated the quality of the produced queries on a number of criteria from clinicaltrials.gov. Finally, we discuss some criteria that were hard to translate, and give suggestions for how to formulate eligibility criteria to make them easier to translate automatically.

@inproceedings{ XFB-ODLS15,
  address = {Graz, Austria},
  author = {Chao {Xu} and Walter {Forkel} and Stefan {Borgwardt} and Franz {Baader} and Beihai {Zhou}},
  booktitle = {Proc.\ of the 9th Workshop on Ontologies and Data in Life Sciences (ODLS'19), part of The Joint Ontology Workshops (JOWO'19)},
  editor = {Martin {Boeker} and Ludger {Jansen} and Frank {Loebe} and Stefan {Schulz}},
  series = {CEUR Workshop Proceedings},
  title = {Automatic Translation of Clinical Trial Eligibility Criteria into Formal Queries},
  volume = {2518},
  year = {2019},
}

Finding suitable candidates for clinical trials is a labor-intensive task that requires expert medical knowledge. Our goal is to design (semi-)automated techniques that can support clinical researchers in this task. We investigate the issues involved in designing formal query languages for selecting patients that are eligible for a given clinical trial, leveraging existing ontology-based query answering techniques. In particular, we propose to use a temporal extension of existing approaches for accessing data through ontologies written in Description Logics. We sketch how such a query answering system could work and show that eligibility criteria and patient data can be adequately modeled in our formalism.

@inproceedings{ BaBF-HQA18,
  author = {Franz {Baader} and Stefan {Borgwardt} and Walter {Forkel}},
  booktitle = {Proc.\ of the 1st Int.\ Workshop on Hybrid Question Answering with Structured and Unstructured Knowledge (HQA'18), Companion of the The Web Conference 2018},
  doi = {https://dx.doi.org/10.1145/3184558.3191538},
  pages = {1069--1074},
  publisher = {ACM},
  title = {Patient Selection for Clinical Trials Using Temporalized Ontology-Mediated Query Answering},
  year = {2018},
}

We give a survey on recent advances at the forefront of research on probabilistic knowledge bases for representing and querying large-scale automatically extracted data. We concentrate especially on increasing the semantic expressivity of formalisms for representing and querying probabilistic knowledge (i) by giving up the closed-world assumption, (ii) by allowing for commonsense knowledge (and in parallel giving up the tuple-independence assumption), and (iii) by giving up the closed-domain assumption, while preserving some computational properties of query answering in such formalisms.

@inproceedings{ BoCL-IJCAI18,
  address = {Stockholm, Sweden},
  author = {Stefan {Borgwardt} and Ismail Ilkan {Ceylan} and Thomas {Lukasiewicz}},
  booktitle = {Proceedings of the 27th International Joint Conferences on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence (IJCAI-ECAI'18)},
  editor = {J{\'e}r{\^o}me {Lang}},
  note = {Survey paper.},
  pages = {5420--5426},
  publisher = {IJCAI},
  title = {Recent Advances in Querying Probabilistic Knowledge Bases},
  year = {2018},
}

In contrast to qualitative linear temporal logics, which can be used to state that some property will eventually be satisfied, metric temporal logics allow to formulate constraints on how long it may take until the property is satisfied. While most of the work on combining Description Logics (DLs) with temporal logics has concentrated on qualitative temporal logics, there has recently been a growing interest in extending this work to the quantitative case. In this paper, we complement existing results on the combination of DLs with metric temporal logics over the natural numbers by introducing interval-rigid names. This allows to state that elements in the extension of certain names stay in this extension for at least some specified amount of time.

@inproceedings{ BaBoKoOzTh-FroCoS17,
  address = {Bras{\'i}lia, Brazil},
  author = {Franz {Baader} and Stefan {Borgwardt} and Patrick {Koopmann} and Ana {Ozaki} and Veronika {Thost}},
  booktitle = {Proceedings of the 11th International Symposium on Frontiers of Combining Systems (FroCoS'17)},
  editor = {Clare {Dixon} and Marcelo {Finger}},
  pages = {60--76},
  series = {Lecture Notes in Computer Science},
  title = {Metric Temporal Description Logics with Interval-Rigid Names},
  volume = {10483},
  year = {2017},
}

We investigate ontology-based query answering (OBQA) in a setting where both the ontology and the query can refer to concrete values such as numbers and strings. In contrast to previous work on this topic, the built-in predicates used to compare values are not restricted to being unary. We introduce restrictions on these predicates and on the ontology language that allow us to reduce OBQA to query answering in databases using the so-called combined rewriting approach. Though at first sight our restrictions are different from the ones used in previous work, we show that our results strictly subsume some of the existing first-order rewritability results for unary predicates.

@inproceedings{ BaBL-IJCAI17,
  address = {Melbourne, Australia},
  author = {Franz {Baader} and Stefan {Borgwardt} and Marcel {Lippmann}},
  booktitle = {Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI'17)},
  editor = {Carles {Sierra}},
  pages = {786--792},
  title = {Query Rewriting for \textit{{DL-Lite}} with {$n$}-ary Concrete Domains},
  year = {2017},
}

My thesis describes how methods from Formal Concept Analysis can be used for constructing and extending description logic ontologies. In particular, it is shown how concept inclusions can be axiomatized from data in the description logics \(\mathcal{E\mkern-1.618mu L}\), \(\mathcal{M}\), \(\textsf{Horn-}\mathcal{M}\), and \(\textsf{Prob-}\mathcal{E\mkern-1.618mu L}\). All proposed methods are not only sound but also complete, i.e., the result not only consists of valid concept inclusions but also entails each valid concept inclusion. Moreover, a lattice-theoretic view on the description logic \(\mathcal{E\mkern-1.618mu L}\) is provided. For instance, it is shown how upper and lower neighbors of \(\mathcal{E\mkern-1.618mu L}\) concept descriptions can be computed and further it is proven that the set of \(\mathcal{E\mkern-1.618mu L}\) concept descriptions forms a graded lattice with a non-elementary rank function.

@article{ Kr-KI20,
  author = {Francesco {Kriegel}},
  doi = {https://doi.org/10.1007/s13218-020-00673-8},
  journal = {KI - K{\"{u}}nstliche Intelligenz},
  note = {This is a post-peer-review, pre-copyedit version of an article published in KI - K{\"{u}}nstliche Intelligenz. The final authenticated version is available online.},
  pages = {399--403},
  title = {{Constructing and Extending Description Logic Ontologies using Methods of Formal Concept Analysis: A Dissertation Summary}},
  volume = {34},
  year = {2020},
}

The notion of a most specific consequence with respect to some terminological box is introduced, conditions for its existence in the description logic \(\mathcal{E\mkern-1.618mu L}\) and its variants are provided, and means for its computation are developed. Algebraic properties of most specific consequences are explored. Furthermore, several applications that make use of this new notion are proposed and, in particular, it is shown how given terminological knowledge can be incorporated in existing approaches for the axiomatization of observations. For instance, a procedure for an incremental learning of concept inclusions from sequences of interpretations is developed.

@article{ Kr-DAM20,
  author = {Francesco {Kriegel}},
  doi = {https://doi.org/10.1016/j.dam.2019.01.029},
  journal = {Discrete Applied Mathematics},
  pages = {172--204},
  title = {{Most Specific Consequences in the Description Logic $\mathcal{E\mkern-1.618mu L}$}},
  volume = {273},
  year = {2020},
}

Description Logic (abbrv. DL) belongs to the field of knowledge representation and reasoning. DL researchers have developed a large family of logic-based languages, so-called description logics (abbrv. DLs). These logics allow their users to explicitly represent knowledge as ontologies, which are finite sets of (human- and machine-readable) axioms, and provide them with automated inference services to derive implicit knowledge. The landscape of decidability and computational complexity of common reasoning tasks for various description logics has been explored in large parts: there is always a trade-off between expressibility and reasoning costs. It is therefore not surprising that DLs are nowadays applied in a large variety of domains: agriculture, astronomy, biology, defense, education, energy management, geography, geoscience, medicine, oceanography, and oil and gas. Furthermore, the most notable success of DLs is that these constitute the logical underpinning of the Web Ontology Language (abbrv. OWL) in the Semantic Web.

Formal Concept Analysis (abbrv. FCA) is a subfield of lattice theory that allows to analyze data-sets that can be represented as formal contexts. Put simply, such a formal context binds a set of objects to a set of attributes by specifying which objects have which attributes. There are two major techniques that can be applied in various ways for purposes of conceptual clustering, data mining, machine learning, knowledge management, knowledge visualization, etc. On the one hand, it is possible to describe the hierarchical structure of such a data-set in form of a formal concept lattice. On the other hand, the theory of implications (dependencies between attributes) valid in a given formal context can be axiomatized in a sound and complete manner by the so-called canonical base, which furthermore contains a minimal number of implications w.r.t. the properties of soundness and completeness.

In spite of the different notions used in FCA and in DLs, there has been a very fruitful interaction between these two research areas. My thesis continues this line of research and, more specifically, I will describe how methods from FCA can be used to support the automatic construction and extension of DL ontologies from data.

@thesis{ Kriegel-Diss-2019,
  address = {Dresden, Germany},
  author = {Francesco {Kriegel}},
  school = {Technische Universit\"{a}t Dresden},
  title = {Constructing and Extending Description Logic Ontologies using Methods of Formal Concept Analysis},
  type = {Doctoral Thesis},
  year = {2019},
}

A joining implication is a restricted form of an implication where it is explicitly specified which attributes may occur in the premise and in the conclusion, respectively. A technique for sound and complete axiomatization of joining implications valid in a given formal context is provided. In particular, a canonical base for the joining implications valid in a given formal context is proposed, which enjoys the property of being of minimal cardinality among all such bases. Background knowledge in form of a set of valid joining implications can be incorporated. Furthermore, an application to inductive learning in a Horn description logic is proposed, that is, a procedure for sound and complete axiomatization of \(\textsf{Horn-}\mathcal{M}\) concept inclusions from a given interpretation is developed. A complexity analysis shows that this procedure runs in deterministic exponential time.

@techreport{ Kr-LTCS-19-02,
  address = {Dresden, Germany},
  author = {Francesco {Kriegel}},
  institution = {Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universit{\"a}t Dresden},
  note = {\url{https://tu-dresden.de/inf/lat/reports#Kr-LTCS-19-02}},
  number = {19-02},
  title = {{Joining Implications in Formal Contexts and Inductive Learning in a Horn Description Logic (Extended Version)}},
  type = {LTCS-Report},
  year = {2019},
}

A joining implication is a restricted form of an implication where it is explicitly specified which attributes may occur in the premise and in the conclusion, respectively. A technique for sound and complete axiomatization of joining implications valid in a given formal context is provided. In particular, a canonical base for the joining implications valid in a given formal context is proposed, which enjoys the property of being of minimal cardinality among all such bases. Background knowledge in form of a set of valid joining implications can be incorporated. Furthermore, an application to inductive learning in a Horn description logic is proposed, that is, a procedure for sound and complete axiomatization of \(\textsf{Horn-}\mathcal{M}\) concept inclusions from a given interpretation is developed. A complexity analysis shows that this procedure runs in deterministic exponential time.

@inproceedings{ Kr-ICFCA19,
  author = {Francesco {Kriegel}},
  booktitle = {15th International Conference on Formal Concept Analysis, {ICFCA} 2019, Frankfurt, Germany, June 25-28, 2019, Proceedings},
  doi = {https://dx.doi.org/10.1007/978-3-030-21462-3_9},
  editor = {Diana {Cristea} and Florence {Le Ber} and Bar\i{}\c{s} {Sertkaya}},
  pages = {110--129},
  publisher = {Springer},
  series = {Lecture Notes in Computer Science},
  title = {{Joining Implications in Formal Contexts and Inductive Learning in a Horn Description Logic}},
  volume = {11511},
  year = {2019},
}

Description logics in their standard setting only allow for representing and reasoning with crisp knowledge without any degree of uncertainty. Of course, this is a serious shortcoming for use cases where it is impossible to perfectly determine the truth of a statement. For resolving this expressivity restriction, probabilistic variants of description logics have been introduced. Their model-theoretic semantics is built upon so-called probabilistic interpretations, that is, families of directed graphs the vertices and edges of which are labeled and for which there exists a probability measure on this graph family.

Results of scientific experiments, e.g., in medicine, psychology, or biology, that are repeated several times can induce probabilistic interpretations in a natural way. In this document, we shall develop a suitable axiomatization technique for deducing terminological knowledge from the assertional data given in such probabilistic interpretations. More specifically, we consider a probabilistic variant of the description logic \(\mathcal{E\mkern-1.618mu L}^{\!\bot}\), and provide a method for constructing a set of rules, so-called concept inclusions, from probabilistic interpretations in a sound and complete manner.

@inproceedings{ Kr-JELIA19,
  author = {Francesco {Kriegel}},
  booktitle = {16th European Conference on Logics in Artificial Intelligence, {JELIA} 2019, Rende, Italy, May 7-11, 2019, Proceedings},
  doi = {https://dx.doi.org/10.1007/978-3-030-19570-0_26},
  editor = {Francesco {Calimeri} and Nicola {Leone} and Marco {Manna}},
  pages = {399--417},
  publisher = {Springer},
  series = {Lecture Notes in Computer Science},
  title = {{Learning Description Logic Axioms from Discrete Probability Distributions over Description Graphs}},
  volume = {11468},
  year = {2019},
}

For a probabilistic extension of the description logic \(\mathcal{E\mkern-1.618mu L}^{\bot}\), we consider the task of automatic acquisition of terminological knowledge from a given probabilistic interpretation. Basically, such a probabilistic interpretation is a family of directed graphs the vertices and edges of which are labeled, and where a discrete probability measure on this graph family is present. The goal is to derive so-called concept inclusions which are expressible in the considered probabilistic description logic and which hold true in the given probabilistic interpretation. A procedure for an appropriate axiomatization of such graph families is proposed and its soundness and completeness is justified.

@inproceedings{ Kr-KI18,
  address = {Berlin, Germany},
  author = {Francesco {Kriegel}},
  booktitle = {{{KI} 2018: Advances in Artificial Intelligence - 41st German Conference on AI, Berlin, Germany, September 24-28, 2018, Proceedings}},
  doi = {https://doi.org/10.1007/978-3-030-00111-7_5},
  editor = {Frank {Trollmann} and Anni-Yasmin {Turhan}},
  pages = {46--53},
  publisher = {Springer},
  series = {Lecture Notes in Computer Science},
  title = {{Acquisition of Terminological Knowledge in Probabilistic Description Logic}},
  volume = {11117},
  year = {2018},
}

Description logics in their standard setting only allow for representing and reasoning with crisp knowledge without any degree of uncertainty. Of course, this is a serious shortcoming for use cases where it is impossible to perfectly determine the truth of a statement. For resolving this expressivity restriction, probabilistic variants of description logics have been introduced. Their model-theoretic semantics is built upon so-called probabilistic interpretations, that is, families of directed graphs the vertices and edges of which are labeled and for which there exists a probability measure on this graph family.

Results of scientific experiments, e.g., in medicine, psychology, or biology, that are repeated several times can induce probabilistic interpretations in a natural way. In this document, we shall develop a suitable axiomatization technique for deducing terminological knowledge from the assertional data given in such probabilistic interpretations. More specifically, we consider a probabilistic variant of the description logic \(\mathcal{E\mkern-1.618mu L}^{\!\bot}\), and provide a method for constructing a set of rules, so-called concept inclusions, from probabilistic interpretations in a sound and complete manner.

@techreport{ Kr-LTCS-18-12,
  address = {Dresden, Germany},
  author = {Francesco {Kriegel}},
  institution = {Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universit{\"a}t Dresden},
  note = {\url{https://tu-dresden.de/inf/lat/reports#Kr-LTCS-18-12}},
  number = {18-12},
  title = {{Learning Description Logic Axioms from Discrete Probability Distributions over Description Graphs (Extended Version)}},
  type = {LTCS-Report},
  year = {2018},
}

The notion of a most specific consequence with respect to some terminological box is introduced, conditions for its existence in the description logic \(\mathcal{E\mkern-1.618mu L}\) and its variants are provided, and means for its computation are developed. Algebraic properties of most specific consequences are explored. Furthermore, several applications that make use of this new notion are proposed and, in particular, it is shown how given terminological knowledge can be incorporated in existing approaches for the axiomatization of observations. For instance, a procedure for an incremental learning of concept inclusions from sequences of interpretations is developed.

@techreport{ Kr-LTCS-18-11,
  address = {Dresden, Germany},
  author = {Francesco {Kriegel}},
  institution = {Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universit{\"a}t Dresden},
  note = {\url{https://tu-dresden.de/inf/lat/reports#Kr-LTCS-18-11}, accepted for publication in {Discrete Applied Mathematics}},
  number = {18-11},
  title = {{Most Specific Consequences in the Description Logic $\mathcal{E\mkern-1.618mu L}$}},
  type = {LTCS-Report},
  year = {2018},
}

For a probabilistic extension of the description logic \(\mathcal{E\mkern-1.618mu L}^{\bot}\), we consider the task of automatic acquisition of terminological knowledge from a given probabilistic interpretation. Basically, such a probabilistic interpretation is a family of directed graphs the vertices and edges of which are labeled, and where a discrete probability measure on this graph family is present. The goal is to derive so-called concept inclusions which are expressible in the considered probabilistic description logic and which hold true in the given probabilistic interpretation. A procedure for an appropriate axiomatization of such graph families is proposed and its soundness and completeness is justified.

@techreport{ Kr-LTCS-18-03,
  address = {Dresden, Germany},
  author = {Francesco {Kriegel}},
  institution = {Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universit{\"a}t Dresden},
  note = {\url{https://tu-dresden.de/inf/lat/reports#Kr-LTCS-18-03}},
  number = {18-03},
  title = {{Terminological Knowledge Acquisition in Probabilistic Description Logic}},
  type = {LTCS-Report},
  year = {2018},
}

For the description logic \(\mathcal{E\mkern-1.618mu L}\), we consider the neighborhood relation which is induced by the subsumption order, and we show that the corresponding lattice of \(\mathcal{E\mkern-1.618mu L}\) concept descriptions is distributive, modular, graded, and metric. In particular, this implies the existence of a rank function as well as the existence of a distance function.

@techreport{ Kr-LTCS-18-10,
  address = {Dresden, Germany},
  author = {Francesco {Kriegel}},
  institution = {Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universit{\"a}t Dresden},
  note = {\url{https://tu-dresden.de/inf/lat/reports#Kr-LTCS-18-10}},
  number = {18-10},
  title = {{The Distributive, Graded Lattice of $\mathcal{E\mkern-1.618mu L}$ Concept Descriptions and its Neighborhood Relation (Extended Version)}},
  type = {LTCS-Report},
  year = {2018},
}

For the description logic \(\mathcal{E\mkern-1.618mu L}\), we consider the neighborhood relation which is induced by the subsumption order, and we show that the corresponding lattice of \(\mathcal{E\mkern-1.618mu L}\) concept descriptions is distributive, modular, graded, and metric. In particular, this implies the existence of a rank function as well as the existence of a distance function.

@inproceedings{ Kr-CLA18,
  address = {Olomouc, Czech Republic},
  author = {Francesco {Kriegel}},
  booktitle = {{Proceedings of the 14th International Conference on Concept Lattices and Their Applications ({CLA 2018})}},
  editor = {Dmitry I. {Ignatov} and Lhouari {Nourine}},
  pages = {267--278},
  publisher = {CEUR-WS.org},
  series = {{CEUR} Workshop Proceedings},
  title = {{The Distributive, Graded Lattice of $\mathcal{E\mkern-1.618mu L}$ Concept Descriptions and its Neighborhood Relation}},
  volume = {2123},
  year = {2018},
}

The Web Ontology Language (OWL) has gained serious attraction since its foundation in 2004, and it is heavily used in applications requiring representation of as well as reasoning with knowledge. It is the language of the Semantic Web, and it has a strong logical underpinning by means of so-called Description Logics (DLs). DLs are a family of conceptual languages suitable for knowledge representation and reasoning due to their strong logical foundation, and for which the decidability and complexity of common reasoning problems are widely explored. In particular, the reasoning tasks allow for the deduction of implicit knowledge from explicitly stated facts and axioms, and plenty of appropriate algorithms were developed, optimized, and implemented, e.g., tableaux algorithms and completion algorithms. In this document, we present a technique for the acquisition of terminological knowledge from social networks. More specifically, we show how OWL axioms, i.e., concept inclusions and role inclusions in DLs, can be obtained from social graphs in a sound and complete manner. A social graph is simply a directed graph, the vertices of which describe the entities, e.g., persons, events, messages, etc.; and the edges of which describe the relationships between the entities, e.g., friendship between persons, attendance of a person to an event, a person liking a message, etc. Furthermore, the vertices of social graphs are labeled, e.g., to describe properties of the entities, and also the edges are labeled to specify the concrete relationships. As an exemplary social network we consider Facebook, and show that it fits our use case.

@incollection{ Kr-FCAoSN17,
  address = {Cham},
  author = {Francesco {Kriegel}},
  booktitle = {Formal Concept Analysis of Social Networks},
  doi = {https://dx.doi.org/10.1007/978-3-319-64167-6_5},
  editor = {Rokia {Missaoui} and Sergei O. {Kuznetsov} and Sergei {Obiedkov}},
  pages = {97--142},
  publisher = {Springer International Publishing},
  series = {Lecture Notes in Social Networks ({LNSN})},
  title = {Acquisition of Terminological Knowledge from Social Networks in Description Logic},
  year = {2017},
}

Entropy is a measure for the uninformativeness or randomness of a data set, i.e., the higher the entropy is, the lower is the amount of information. In the field of propositional logic it has proven to constitute a suitable measure to be maximized when dealing with models of probabilistic propositional theories. More specifically, it was shown that the model of a probabilistic propositional theory with maximal entropy allows for the deduction of other formulae which are somehow expected by humans, i.e., allows for some kind of common sense reasoning. In order to pull the technique of maximum entropy entailment to the field of Formal Concept Analysis, we define the notion of entropy of a formal context with respect to the frequency of its object intents, and then define maximum entropy entailment for quantified implication sets, i.e., for sets of partial implications where each implication has an assigned degree of confidence. Furthermore, then this entailment technique is utilized to define so-called maximum entropy implicational bases (ME-bases), and a first general example of such a ME-base is provided.

@inproceedings{ Kr-ICFCA17b,
  address = {Rennes, France},
  author = {Francesco {Kriegel}},
  booktitle = {Proceedings of the 14th International Conference on Formal Concept Analysis ({ICFCA} 2017)},
  doi = {https://doi.org/10.1007/978-3-319-59271-8_10},
  editor = {Karell {Bertet} and Daniel {Borchmann} and Peggy {Cellier} and S\'{e}bastien {Ferr\'{e}}},
  pages = {155--167},
  publisher = {Springer Verlag},
  series = {Lecture Notes in Computer Science ({LNCS})},
  title = {First Notes on Maximum Entropy Entailment for Quantified Implications},
  volume = {10308},
  year = {2017},
}

We consider the task of acquisition of terminological knowledge from given assertional data. However, when evaluating data of real-world applications we often encounter situations where it is impractical to deduce only crisp knowledge, due to the presence of exceptions or errors. It is rather appropriate to allow for degrees of uncertainty within the derived knowledge. Consequently, suitable methods for knowledge acquisition in a probabilistic framework should be developed. In particular, we consider data which is given as a probabilistic formal context, i.e., as a triadic incidence relation between objects, attributes, and worlds, which is furthermore equipped with a probability measure on the set of worlds. We define the notion of a probabilistic attribute as a probabilistically quantified set of attributes, and define the notion of validity of implications over probabilistic attributes in a probabilistic formal context. Finally, a technique for the axiomatization of such implications from probabilistic formal contexts is developed. This is done is a sound and complete manner, i.e., all derived implications are valid, and all valid implications are deducible from the derived implications. In case of finiteness of the input data to be analyzed, the constructed axiomatization is finite, too, and can be computed in finite time.

@inproceedings{ Kr-ICFCA17a,
  address = {Rennes, France},
  author = {Francesco {Kriegel}},
  booktitle = {Proceedings of the 14th International Conference on Formal Concept Analysis ({ICFCA} 2017)},
  doi = {https://doi.org/10.1007/978-3-319-59271-8_11},
  editor = {Karell {Bertet} and Daniel {Borchmann} and Peggy {Cellier} and S\'{e}bastien {Ferr\'{e}}},
  pages = {168--183},
  publisher = {Springer Verlag},
  series = {Lecture Notes in Computer Science ({LNCS})},
  title = {Implications over Probabilistic Attributes},
  volume = {10308},
  year = {2017},
}

A probabilistic formal context is a triadic context the third dimension of which is a set of worlds equipped with a probability measure. After a formal definition of this notion, this document introduces probability of implications with respect to probabilistic formal contexts, and provides a construction for a base of implications the probabilities of which exceed a given lower threshold. A comparison between confidence and probability of implications is drawn, which yields the fact that both measures do not coincide. Furthermore, the results are extended towards the lightweight description logic \(\mathcal{E\mkern-1.618mu L}^{\bot}\) with probabilistic interpretations, and a method for computing a base of general concept inclusions the probabilities of which are greater than a pre-defined lower bound is proposed. Additionally, we consider so-called probabilistic attributes over probabilistic formal contexts, and provide a method for the axiomatization of implications over probabilistic attributes.

@article{ Kr-IJGS17,
  author = {Francesco {Kriegel}},
  doi = {https://doi.org/10.1080/03081079.2017.1349575},
  journal = {International Journal of General Systems},
  number = {5},
  pages = {511--546},
  title = {Probabilistic Implication Bases in {FCA} and Probabilistic Bases of GCIs in $\mathcal{E\mkern-1.618mu L}^{\bot}$},
  volume = {46},
  year = {2017},
}

The canonical base of a formal context plays a distinguished role in Formal Concept Analysis, as it is the only minimal implicational base known so far that can be described explicitly. Consequently, several algorithms for the computation of this base have been proposed. However, all those algorithms work sequentially by computing only one pseudo-intent at a time – a fact that heavily impairs the practicability in real-world applications. In this paper, we shall introduce an approach that remedies this deficit by allowing the canonical base to be computed in a parallel manner with respect to arbitrary implicational background knowledge. First experimental evaluations show that for sufficiently large data sets the speed-up is proportional to the number of available CPU cores.

@article{ KrBo-IJGS17,
  author = {Francesco {Kriegel} and Daniel {Borchmann}},
  doi = {https://doi.org/10.1080/03081079.2017.1349570},
  journal = {International Journal of General Systems},
  number = {5},
  pages = {490--510},
  title = {NextClosures: Parallel Computation of the Canonical Base with Background Knowledge},
  volume = {46},
  year = {2017},
}

Description logic knowledge bases can be used to represent knowledge about a particular domain in a formal and unambiguous manner. Their practical relevance has been shown in many research areas, especially in biology and the Semantic Web. However, the tasks of constructing knowledge bases itself, often performed by human experts, is difficult, time-consuming and expensive. In particular the synthesis of terminological knowledge is a challenge every expert has to face. Because human experts cannot be omitted completely from the construction of knowledge bases, it would therefore be desirable to at least get some support from machines during this process. To this end, we shall investigate in this work an approach which shall allow us to extract terminological knowledge in the form of general concept inclusions from factual data, where the data is given in the form of vertex and edge labeled graphs. As such graphs appear naturally within the scope of the Semantic Web in the form of sets of RDF triples, the presented approach opens up another possibility to extract terminological knowledge from the Linked Open Data Cloud.

@article{ BoDiKr-JANCL16,
  author = {Daniel {Borchmann} and Felix {Distel} and Francesco {Kriegel}},
  doi = {https://dx.doi.org/10.1080/11663081.2016.1168230},
  journal = {Journal of Applied Non-Classical Logics},
  number = {1},
  pages = {1--46},
  title = {Axiomatisation of General Concept Inclusions from Finite Interpretations},
  volume = {26},
  year = {2016},
}

We propose applications that utilize the infimum and the supremum of closure operators that are induced by structures occuring in the field of Description Logics. More specifically, we consider the closure operators induced by interpretations as well as closure operators induced by TBoxes, and show how we can learn GCIs from streams of interpretations, and how an error-tolerant axiomatization of GCIs from an interpretation guided by a hand-crafted TBox can be achieved.

@inproceedings{ Kr-FCA4AI16,
  address = {The Hague, The Netherlands},
  author = {Francesco {Kriegel}},
  booktitle = {Proceedings of the 5th International Workshop "What can {FCA} do for Artificial Intelligence?" ({FCA4AI} 2016) co-located with the European Conference on Artificial Intelligence ({ECAI} 2016)},
  editor = {Sergei {Kuznetsov} and Amedeo {Napoli} and Sebastian {Rudolph}},
  pages = {9--16},
  publisher = {CEUR-WS.org},
  series = {{CEUR} Workshop Proceedings},
  title = {Axiomatization of General Concept Inclusions from Streams of Interpretations with Optional Error Tolerance},
  volume = {1703},
  year = {2016},
}

In a former paper, the algorithm NextClosures for computing the set of all formal concepts as well as the canonical base for a given formal context has been introduced. Here, this algorithm shall be generalized to a setting where the data-set is described by means of a closure operator in a complete lattice, and furthermore it shall be extended with the possibility to handle constraints that are given in form of a second closure operator. As a special case, constraints may be predefined as implicational background knowledge. Additionally, we show how the algorithm can be modified in order to do parallel Attribute Exploration for unconstrained closure operators, as well as give a reason for the impossibility of (parallel) Attribute Exploration for constrained closure operators if the constraint is not compatible with the data-set.

@inproceedings{ Kr-CLA16,
  address = {Moscow, Russia},
  author = {Francesco {Kriegel}},
  booktitle = {Proceedings of the 13th International Conference on Concept Lattices and Their Applications ({CLA 2016})},
  editor = {Marianne {Huchard} and Sergei {Kuznetsov}},
  pages = {231--243},
  publisher = {CEUR-WS.org},
  series = {{CEUR} Workshop Proceedings},
  title = {NextClosures with Constraints},
  volume = {1624},
  year = {2016},
}

The canonical base of a formal context is a minimal set of implications that is sound and complete. A recent paper has provided a new algorithm for the parallel computation of canonical bases. An important extension is the integration of expert interaction for Attribute Exploration in order to explore implicational bases of inaccessible formal contexts. This paper presents and analyzes an algorithm that allows for Parallel Attribute Exploration.

@inproceedings{ Kr-ICCS16,
  address = {Annecy, France},
  author = {Francesco {Kriegel}},
  booktitle = {Proceedings of the 22nd International Conference on Conceptual Structures ({ICCS 2016})},
  doi = {http://dx.doi.org/10.1007/978-3-319-40985-6_8},
  editor = {Ollivier {Haemmerl{\'{e}}} and Gem {Stapleton} and Catherine {Faron{-}Zucker}},
  pages = {91--106},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Parallel Attribute Exploration},
  volume = {9717},
  year = {2016},
}

Description logic knowledge bases can be used to represent knowledge about a particular domain in a formal and unambiguous manner. Their practical relevance has been shown in many research areas, especially in biology and the semantic web. However, the tasks of constructing knowledge bases itself, often performed by human experts, is difficult, time-consuming and expensive. In particular the synthesis of terminological knowledge is a challenge every expert has to face. Because human experts cannot be omitted completely from the construction of knowledge bases, it would therefore be desirable to at least get some support from machines during this process. To this end, we shall investigate in this work an approach which shall allow us to extract terminological knowledge in the form of general concept inclusions from factual data, where the data is given in the form of vertex and edge labeled graphs. As such graphs appear naturally within the scope of the Semantic Web in the form of sets of RDF triples, the presented approach opens up the possibility to extract terminological knowledge from the Linked Open Data Cloud. We shall also present first experimental results showing that our approach has the potential to be useful for practical applications.

@techreport{ BoDiKr-LTCS-15-13,
  address = {Dresden, Germany},
  author = {Daniel {Borchmann} and Felix {Distel} and Francesco {Kriegel}},
  institution = {Chair for Automata Theory, Institute for Theoretical Computer Science, Technische Universit{\"a}t Dresden},
  note = {\url{https://tu-dresden.de/inf/lat/reports#BoDiKr-LTCS-15-13}},
  number = {15-13},
  title = {{Axiomatization of General Concept Inclusions from Finite Interpretations}},
  type = {LTCS-Report},
  year = {2015},
}

Probabilistic interpretations consist of a set of interpretations with a shared domain and a measure assigning a probability to each interpretation. Such structures can be obtained as results of repeated experiments, e.g., in biology, psychology, medicine, etc. A translation between probabilistic and crisp description logics is introduced, and then utilized to reduce the construction of a base of general concept inclusions of a probabilistic interpretation to the crisp case for which a method for the axiomatization of a base of GCIs is well-known.

@inproceedings{ Kr-KI15,
  address = {Dresden, Germany},
  author = {Francesco {Kriegel}},
  booktitle = {Proceedings of the 38th German Conference on Artificial Intelligence ({KI 2015})},
  doi = {http://dx.doi.org/10.1007/978-3-319-24489-1_10},
  editor = {Steffen {H{\"o}lldobler} and Sebastian {Rudolph} and Markus {Kr{\"o}tzsch}},
  pages = {124--136},
  publisher = {Springer Verlag},
  series = {Lecture Notes in Artificial Intelligence ({LNAI})},
  title = {Axiomatization of General Concept Inclusions in Probabilistic Description Logics},
  volume = {9324},
  year = {2015},
}

A description graph is a directed graph that has labeled vertices and edges. This document proposes a method for extracting a knowledge base from a description graph. The technique is presented for the description logic \(\mathcal{A\mkern-1.618mu L\mkern-1.618mu E\mkern-1.618mu Q\mkern-1.618mu R}(\mathsf{Self})\) which allows for conjunctions, primitive negation, existential restrictions, value restrictions, qualified number restrictions, existential self restrictions, and complex role inclusion axioms, but also sublogics may be chosen to express the axioms in the knowledge base. The extracted knowledge base entails all statements that can be expressed in the chosen description logic and are encoded in the input graph.

@inproceedings{ Kr-SNAFCA15,
  address = {Nerja, Spain},
  author = {Francesco {Kriegel}},
  booktitle = {Proceedings of the International Workshop on Social Network Analysis using Formal Concept Analysis ({SNAFCA 2015}) in conjunction with the 13th International Conference on Formal Concept Analysis ({ICFCA} 2015)},
  editor = {Sergei O. {Kuznetsov} and Rokia {Missaoui} and Sergei A. {Obiedkov}},
  publisher = {CEUR-WS.org},
  series = {CEUR Workshop Proceedings},
  title = {Extracting $\mathcal{A\mkern-1.618mu L\mkern-1.618mu E\mkern-1.618mu Q\mkern-1.618mu R}(\mathsf{Self})$-Knowledge Bases from Graphs},
  volume = {1534},
  year = {2015},
}

Formal Concept Analysis and its methods for computing minimal implicational bases have been successfully applied to axiomatise minimal \(\mathcal{E\mkern-1.618mu L}\)-TBoxes from models, so called bases of GCIs. However, no technique for an adjustment of an existing \(\mathcal{E\mkern-1.618mu L}\)-TBox w.r.t. a new model is available, i.e., on a model change the complete TBox has to be recomputed. This document proposes a method for the computation of a minimal extension of a TBox w.r.t. a new model. The method is then utilised to formulate an incremental learning algorithm that requires a stream of interpretations, and an expert to guide the learning process, respectively, as input.

@inproceedings{ Kr-DL15,
  address = {Athens, Greece},
  author = {Francesco {Kriegel}},
  booktitle = {Proceedings of the 28th International Workshop on Description Logics ({DL 2015})},
  editor = {Diego {Calvanese} and Boris {Konev}},
  pages = {452--464},
  publisher = {CEUR-WS.org},
  series = {CEUR Workshop Proceedings},
  title = {Incremental Learning of TBoxes from Interpretation Sequences with Methods of Formal Concept Analysis},
  volume = {1350},
  year = {2015},
}

A probabilistic formal context is a triadic context whose third dimension is a set of worlds equipped with a probability measure. After a formal definition of this notion, this document introduces probability of implications, and provides a construction for a base of implications whose probability satisfy a given lower threshold. A comparison between confidence and probability of implications is drawn, which yields the fact that both measures do not coincide, and cannot be compared. Furthermore, the results are extended towards the light-weight description logic \(\mathcal{E\mkern-1.618mu L}^{\bot}\) with probabilistic interpretations, and a method for computing a base of general concept inclusions whose probability fulfill a certain lower bound is proposed.

@inproceedings{ Kr-CLA15,
  address = {Clermont-Ferrand, France},
  author = {Francesco {Kriegel}},
  booktitle = {Proceedings of the 12th International Conference on Concept Lattices and their Applications ({CLA 2015})},
  editor = {Sadok {Ben Yahia} and Jan {Konecny}},
  pages = {193--204},
  publisher = {CEUR-WS.org},
  series = {CEUR Workshop Proceedings},
  title = {Probabilistic Implicational Bases in FCA and Probabilistic Bases of GCIs in $\mathcal{E\mkern-1.618mu L}^{\bot}$},
  volume = {1466},
  year = {2015},
}

Probabilistic interpretations consist of a set of interpretations with a shared domain and a measure assigning a probability to each interpretation. Such structures can be obtained as results of repeated experiments, e.g., in biology, psychology, medicine, etc. A translation between probabilistic and crisp description logics is introduced and then utilised to reduce the construction of a base of general concept inclusions of a probabilistic interpretation to the crisp case for which a method for the axiomatisation of a base of GCIs is well-known.

@techreport{ Kr-LTCS-15-14,
  address = {Dresden, Germany},
  author = {Francesco {Kriegel}},
  institution = {Chair for Automata Theory, Institute for Theoretical Computer Science, Technische Universit{\"a}t Dresden},
  note = {\url{https://tu-dresden.de/inf/lat/reports#Kr-LTCS-15-14}},
  number = {15-14},
  title = {{Learning General Concept Inclusions in Probabilistic Description Logics}},
  type = {LTCS-Report},
  year = {2015},
}

Model-based most specific concept descriptions are a useful means to compactly represent all knowledge about a certain individual of an interpretation that is expressible in the underlying description logic. Existing approaches only cover their construction in the case of \(\mathcal{E\mkern-1.618mu L}\) and \(\mathcal{F\mkern-1.618mu L\mkern-1.618mu E}\) w.r.t. greatest fixpoint semantics, and the case of \(\mathcal{E\mkern-1.618mu L}\) w.r.t. a role-depth bound, respectively. This document extends the results towards the more expressive description logic \(\mathcal{A\mkern-1.618mu L\mkern-1.618mu E\mkern-1.618mu Q}^{\geq}\mkern-1.618mu\mathcal{N}^{\leq}\mkern-1.618mu(\mathsf{Self})\) w.r.t. role-depth bounds and also gives a method for the computation of least common subsumers.

@techreport{ Kr-LTCS-15-02,
  address = {Dresden, Germany},
  author = {Francesco {Kriegel}},
  institution = {Chair for Automata Theory, Institute for Theoretical Computer Science, Technische Universit{\"a}t Dresden},
  note = {\url{https://tu-dresden.de/inf/lat/reports#Kr-LTCS-15-02}},
  number = {15-02},
  title = {{Model-Based Most Specific Concept Descriptions and Least Common Subsumers in $\mathcal{A\mkern-1.618mu L\mkern-1.618mu E\mkern-1.618mu Q}^{\geq}\mkern-1.618mu\mathcal{N}^{\leq}\mkern-1.618mu(\mathsf{Self})$}},
  type = {LTCS-Report},
  year = {2015},
}

It is well-known that the canonical implicational base of all implications valid w.r.t. a closure operator can be obtained from the set of all pseudo-closures. NextClosures is a parallel algorithm to compute all closures and pseudo-closures of a closure operator in a graded lattice, e.g., in a powerset. Furthermore, the closures and pseudo-closures can be constrained, and partially known closure operators can be explored.

@techreport{ Kr-LTCS-15-01,
  address = {Dresden, Germany},
  author = {Francesco {Kriegel}},
  institution = {Chair for Automata Theory, Institute for Theoretical Computer Science, Technische Universit{\"a}t Dresden},
  note = {\url{https://tu-dresden.de/inf/lat/reports#Kr-LTCS-15-01}},
  number = {15-01},
  title = {{NextClosures -- Parallel Exploration of Constrained Closure Operators}},
  type = {LTCS-Report},
  year = {2015},
}

The canonical base of a formal context plays a distinguished role in formal concept analysis. This is because it is the only minimal base so far that can be described explicitly. For the computation of this base several algorithms have been proposed. However, all those algorithms work sequentially, by computing only one pseudo-intent at a time - a fact which heavily impairs the practicability of using the canonical base in real-world applications. In this paper we shall introduce an approach that remedies this deficit by allowing the canonical base to be computed in a parallel manner. First experimental evaluations show that for sufficiently large data-sets the speedup is proportional to the number of available CPUs.

@inproceedings{ KrBo-CLA15,
  address = {Clermont-Ferrand, France},
  author = {Francesco {Kriegel} and Daniel {Borchmann}},
  booktitle = {Proceedings of the 12th International Conference on Concept Lattices and their Applications ({CLA 2015})},
  editor = {Sadok {Ben Yahia} and Jan {Konecny}},
  note = {Best Paper Award.},
  pages = {182--192},
  publisher = {CEUR-WS.org},
  series = {CEUR Workshop Proceedings},
  title = {NextClosures: Parallel Computation of the Canonical Base},
  volume = {1466},
  year = {2015},
}