DeciGUT

From International Center for Computational Logic
Toggle side column

DeciGUT

A Grand Unified Theory of Decidability in Logic-Based Knowledge Representation
  •   Contact Sebastian Rudolph
  •   October 1, 2018 – March 31, 2024
  •   funded by European Research Council
LOGO-ERC-small.jpg

The project deals with the formal foundations of knowledge management as well as their application in today's information society. Among the biggest challenges in this area are the intelligent access to digital information as well as the automated composition of information from diverse sources. For these purposes, logical specifications of background knowledge - so-called ontologies - can be used together with automated reasoning techniques in order to enable a "meaning-aware" handling of data.

Unfortunately, reasoning in ontology languages of high expressivity is impossible to capture algorithmically – they are undecidable. Therefore, the quest for "good" ontology languages consists in identifying logical formalisms which are as expressive as possible, yet still decidable. Hitherto, the obtained results in this area have, however, been patchy and fragmented.

The goal of the DeciGUT project is the creation of a unified theory of decidability, which in turn will enable the definition of new, advanced ontology languages.

The project is of high relevance to diverse scientific fields like mathematical logic, artificial intelligence, and database theory with potentially far-reaching impact in areas such as semantic technologies and information systems.


Journal Articles

Sarah Alice Gaggl, Sebastian Rudolph, Hannes Straß
On the Decomposition of ADFs and the Complexity of Naive-based Semantics
Journal of Artificial Intelligence Research, 70:1-64, January 2021
Details Download
Norbert Manthey, Rafael Peñaloza Nyssen, Sebastian Rudolph
SATPin: Axiom Pinpointing for Lightweight Description Logics through Incremental SAT
Künstliche Intelligenz, 34(3):389-394, 2020
Details Download

Proceedings Articles

Camille Bourgaux, David Carral, Markus Krötzsch, Sebastian Rudolph, Michaël Thomazo
Capturing Homomorphism-Closed Decidable Queries with Existential Rules
Proc. 18th International Conference on Principles of Knowledge Representation and Reasoning (KR'21), to appear
Details Download
Bartosz Bednarczyk
Exploiting forwardness: Satisfiability and Query-Entailment in Forward Guarded Fragment
Proceedings of the 17th Edition of the European Conference on Logics in Artificial Intelligence (JELIA 2021), May 2021. Springer International Publishing
Details Download
Bartosz Bednarczyk, Sebastian Rudolph
The Price of Selfishness: Conjunctive Query Entailment for ALCSelf is 2ExpTime-hard (Extended Abstract)
In Martin Homola, Vladislav Ryzhikov, Renate A. Schmidt, eds., Proceedings of the 34th International Workshop on Description Logics (DL 2021), CEUR Workshop Proceedings, to appear. CEUR-WS.org
Details Download
Emanuel Kieroński, Sebastian Rudolph
Finite Model Theory of the Triguarded Fragment and Related Logics
Proceedings of the 36th Annual Symposium on Logic in Computer Science (LICS 2021), to appear
Details Download
Bartosz Bednarczyk, Emanuel Kieroński
Finite-Controllability of Conjunctive Queries in the Z family of Description Logics (Extended Abstract)
In Martin Homola, Vladislav Ryzhikov, Renate A. Schmidt, eds., Proceedings of the 34th International Workshop on Description Logics (DL 2021), CEUR Workshop Proceedings, to appear. CEUR-WS.org
Details Download
Manuel Bodirsky, Thomas Feller, Simon Knäuer, Sebastian Rudolph
On Logics and Homomorphism Closure
Proceedings of the 36th Annual Symposium on Logic in Computer Science (LICS 2021), to appear
Details Download
Manuel Bodirsky, Simon Knäuer, Sebastian Rudolph
Datalog-Expressibility for Monadic and Guarded Second-Order Logic
In Nikhil Bansal, James Worrell, eds., Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP), LIPIcs, to appear. Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Details Download
Sarah Alice Gaggl, Sebastian Rudolph, Hannes Straß
On the Decomposition of ADFs and the Complexity of Naive-based Semantics
IJCAI 2021 Journal Track, 2021
Details
Franz Baader, Bartosz Bednarczyk, Sebastian Rudolph
Satisfiability and Query Answering in Description Logics with Global and Local Cardinality Constraints
Proceedings of the 24th European Conference on Artificial Intelligence (ECAI 2020), June 2020
Details Download
Bartosz Bednarczyk, Robert Ferens, Piotr Ostropolski-Nalewaja
All-Instances Oblivious Chase Termination is Undecidable for Single-Head Binary TGDs
Proceedings of the 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial Intelligence (IJCAI 2020), July 2020. International Joint Conferences on Artificial Intelligence
Details Download
Bartosz Bednarczyk, Stéphane Demri, Alessio Mansutti
A Framework for Reasoning about Dynamic Axioms in Description Logics
Proceedings of the 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial Intelligence (IJCAI 2020), July 2020. International Joint Conferences on Artificial Intelligence
Details Download
Franz Baader, Bartosz Bednarczyk, Sebastian Rudolph
Satisfiability Checking and Conjunctive Query Answering in Description Logics with Global and Local Cardinality Constraints
In Mantas Simkus, Grant E. Weddell, eds., Proceedings of the 32nd International Workshop on Description Logics, volume 2373 of CEUR Workshop Proceedings, June 2019. CEUR-WS.org
Details Download
Markus Krötzsch, Maximilian Marx, Sebastian Rudolph
The Power of the Terminating Chase
In Pablo Barceló, Marco Calautti, eds., Proceedings of the 22nd International Conference on Database Theory (ICDT 2019), volume 127 of LIPIcs, 3:1--3:17, 2019. Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Details Download
Bartosz Bednarczyk, Sebastian Rudolph
Worst-Case Optimal Querying of Very Expressive Description Logics with Path Expressions and Succinct Counting
Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI'19), August 2019. International Joint Conferences on Artificial Intelligence
Details Download
Sebastian Rudolph, Lukas Schweizer, Zhihao Yao
SPARQL Queries over Ontologies Under the Fixed-Domain Semantics
In Abhaya C. Nayak, Alok Sharma, eds., PRICAI 2019: Trends in Artificial Intelligence - 16th Pacific Rim International Conference on Artificial Intelligence, Cuvu, Yanuca Island, Fiji, August 26-30, 2019, Proceedings, Part I, volume 11670 of Lecture Notes in Computer Science, 486--499, August 2019. Springer
Details Download
Bernhard Ganter, Sebastian Rudolph, Gerd Stumme
Explaining Data with Formal Concept Analysis
In Markus Krötzsch, Daria Stepanova, eds., Reasoning Web. Explainable Artificial Intelligence - 15th International Summer School 2019, Bolzano, Italy, September 20-24, 2019, Tutorial Lectures., volume 11810 of LNCS, 153-195, 2019. Springer
Details Download
Bartosz Bednarczyk, Sebastian Rudolph
Worst-Case Optimal Querying of Very Expressive Description Logics with Path Expressions and Succinct Counting
In Mantas Simkus, Grant E. Weddell, eds., Proceedings of the 32nd International Workshop on Description Logics, volume 2373 of CEUR Workshop Proceedings, June 2019. CEUR-WS.org
Details Download
Ana Ozaki, Markus Krötzsch, Sebastian Rudolph
Happy Ever After: Temporally Attributed Description Logics
In Magdalena Ortiz, Thomas Schneider, eds., Proceedings of the 31st International Workshop on Description Logics (DL 2018), volume 2211 of CEUR Workshop Proceedings, 2018. CEUR-WS.org
Details Download
Sebastian Rudolph, Mantas Simkus
The Triguarded Fragment of First-Order Logic
In Gilles Barthe, Geoff Sutcliffe, Margus Veanes, eds., Proceedings of the 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning, volume 57 of EPiC Series in Computing, 604-619, 2018. EasyChair
Details Download

Book Chapters

Sebastian Rudolph
Presburger Concept Cardinality Constraints in Very Expressive Description Logics – Allegro sexagenarioso ma non ritardando
In Carsten Lutz, Uli Sattler, Cesare Tinelli, Anni-Yasmin Turhan, Frank Wolter, eds., Description Logic, Theory Combination, and All That - Essays Dedicated to Franz Baader on the Occasion of His 60th Birthday, volume 11560 of LNCS, 542-561. Springer, 2019
Details Download
Ana Ozaki, Markus Krötzsch, Sebastian Rudolph
Temporally Attributed Description Logics
In Carsten Lutz, Uli Sattler, Cesare Tinelli, Anni-Yasmin Turhan, Frank Wolter, eds., Description Logic, Theory Combination, and All That - Essays Dedicated to Franz Baader on the Occasion of His 60th Birthday, volume 11560 of LNCS, 441-474. Springer, 2019
Details Download

Technical Reports

Manuel Bodirsky, Simon Knäuer, Sebastian Rudolph
Datalog-Expressibility for Monadic and Guarded Second-Order Logic
Technical Report, arXiv.org, volume 2010.05677, October 2020
Details Download