The 20th International Conference on Principles of Knowledge Representation and Reasoning (KR 2023) was held in Rhodes, Greece, from Sep 2-8. During the conference, the KR’23 Ray Reiter Best Paper Prize, the Marco Cadoli Distinguished Student Paper Award, and the Best Student Paper Award of the Description Logic Workshop were presented to researchers of TU Wien Informatics!

The Ray Reiter Best Paper Prize was introduced in 2004 in honor of the contributions made by Canadian computer scientist and logician Ray Reiter. The prize of USD 2000 is sponsored by the Artificial Intelligence Journal. This year, the prize was presented to Agata Ciabattoni and Dmitry Rozplokhas for their paper “Streamlining Input/Output Logics with Sequent Calculi”. Agata is a full professor at the faculty of informatics at TU Wien and Dmitry is a PhD student in the doctoral college LogiCS@TUWien.

Abstract
Input/Output (I/O) logic is a general framework for reasoning about conditional norms and/or causal relations. We streamline Bochman’s causal I/O logics via proof-search-oriented sequent calculi. Our calculi establish a natural syntactic link between the derivability in these logics and in the original I/O logics. As a consequence of our results, we obtain new, simple semantics for all these logics, complexity bounds, embeddings into normal modal logics, and efficient deduction methods. Our work encompasses many scattered results and provides uniform solutions to various unresolved problems.

You may read the full paper in the conference proceedings: https://proceedings.kr.org/2023/15/

But this was not the only prize awarded to researchers of TU Wien Informatics! This year’s Marco Cadoli Distinguished Student Paper Award was presented to Rafael Kiesel and Thomas Eiter for their paper “Knowledge Compilation and more with SharpSAT-TD”. Rafael is a former student of the LogiCS doctoral program; his supervisor Thomas is Professor of Knowledge-Based Systems in the faculty of informatics at TU Wien.

Abstract
SharpSAT-TD is a recently published exact model counter that performed exceptionally well in the recent editions of the Model Counting Competition (https://mccompetition.org/). Notably, it additionally features *weighted* model counting capabilities over any semiring. In this work, we show how to exploit this fact to use SharpSAT-TD as a knowledge compiler to the class of sd-DNNF circuits. Our experimental evaluation shows that the efficiency of SharpSAT-TD for (weighted) model counting transfers to knowledge compilation, since it outperforms other state of the art knowledge compilers on standard benchmark sets. Additionally, we generalized SharpSAT-TD’s preprocessing to support arbitrary semirings and consider the utility of auxiliary variables in this setting.

You may read the full paper in the conference proceedings: https://proceedings.kr.org/2023/40/

We also learned that the Best Student Paper Award of the Description Logic Workshop 2023 (co-located with KR 2023) was presented to Sanja Lukumbuzya, Magdalena Ortiz and Mantas Simkus for their paper “On the Expressive Power of Ontology-Mediated Queries: Capturing coNP”. Sanja is a PreDoc researcher in the Databases and Artificial Intelligence group of TU Wien Informatics, and Magdalena is a VCLA board member.

Abstract
The complexity and relative expressiveness of Ontology-mediated Queries (OMQs) is quite well understood by now. In this paper, we study the expressive power of OMQs from a descriptive complexity perspective, where the central question is to understand whether a given OMQ language is powerful enough to express all queries that can be computed within some bound on time or space. We show that the OMQ language that pairs instance queries with ontologies in the very expressive DL ALCHOI with closed predicates cannot express all coNP-computable Boolean queries, despite being coNP-complete in data complexity. We, then, propose an extension of this OMQ language that is expressive enough to precisely capture the class of all Boolean queries computable in coNP. This involves adding functionality as well as path expressions and nominal schemata, which are restricted in a way that allows us to carefully incorporate them into the existing mosaic technique for the DL ALCHOIF with closed predicates without affecting the coNP upper bound in data complexity.

Congratulations on these excellent achievements!