Success at the KR 2023 Conference
The researchers of the TU Wien Informatics received three Best Paper Awards.
The 20th International Conference on Principles of Knowledge Representation and Reasoning (KR 2023) was held this September in Rhodes, Greece. The KR conference series is the leading forum for the comprehensive and up-to-date exploration of progress in the theory and principles underlying the representation and computational management of knowledge.
The KR 2023 was very successful for the researchers of TU Wien Informatics, who were awarded with the Ray Reiter Best Paper Prize, the Marco Cadoli Distinguished Student Paper Award, and the Best Student Paper Award of the Description Logic Workshop.
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 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”.
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.
Abstract: SharpSAT-TD is a recently published exact model counter that performed exceptionally well in the recent editions of the Model Counting Competition. 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.
The Best Student Paper Award of the Description Logic Workshop (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”.
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.
Find more details on the winners and the awards here.