66 citations · 154 across the 21 of their papers we have counts for
27 papers
The Triguarded Fragment
Emanuel Kieroński, Sebastian Rudolph, Mantas Šimkus
A prominent research question in computational logic is how to restrict first-order predicate logic (FO) in such a way that the satisfiability problem becomes decidable. Among othe…
Derivation-Graph-Based Characterizations of Decidable Existential Rule Sets
Tim S. Lyon, Sebastian Rudolph
This paper establishes alternative characterizations of very expressive classes of existential rule sets with decidable query entailment. We consider the notable class of greedy bo…
Pushing the Boundaries of Tractable Multiperspective Reasoning: A Deduction Calculus for Standpoint EL+
Lucía Gómez Álvarez, Sebastian Rudolph, Hannes Strass
Standpoint EL is a multi-modal extension of the popular description logic EL that allows for the integrated representation of domain knowledge relative to diverse standpoints or pe…
Decidable (Ac)counting with Parikh and Muller: Adding Presburger Arithmetic to Monadic Second-Order Logic over Tree-Interpretable Structures
Luisa Herrmann, Vincent Peth, Sebastian Rudolph
We propose MSOBAPA, an expressive logic for describing countable structures, which subsumes and transcends both Counting Monadic Second-Order Logic (CMSO) and Boolean Alg…
Decidability of Querying First-Order Theories via Countermodels of Finite Width
Thomas Feller, Tim S. Lyon, Piotr Ostropolski-Nalewaja +1
We propose a generic framework for establishing the decidability of a wide range of logical entailment problems (briefly called querying), based on the existence of countermodels t…
Tractable Diversity: Scalable Multiperspective Ontology Management via Standpoint EL
Lucía Gómez Álvarez, Sebastian Rudolph, Hannes Strass
The tractability of the lightweight description logic EL has allowed for the construction of large and widely used ontologies that support semantic interoperability. However, compr…
Finite-Cliquewidth Sets of Existential Rules: Toward a General Criterion for Decidable yet Highly Expressive Querying
Thomas Feller, Tim S. Lyon, Piotr Ostropolski-Nalewaja +1
In our pursuit of generic criteria for decidable ontology-based querying, we introduce 'finite-cliquewidth sets' (FCS) of existential rules, a model-theoretically defined class of…
How to Agree to Disagree: Managing Ontological Perspectives using Standpoint Logic
Lucía Gómez Álvarez, Sebastian Rudolph, Hannes Strass
The importance of taking individual, potentially conflicting perspectives into account when dealing with knowledge has been widely recognised. Many existing ontology management app…
AGM Belief Revision, Semantically
Faiq Miftakhul Falakh, Sebastian Rudolph, Kai Sauerwald
We establish a generic, model-theoretic characterization of belief revision operators implementing the paradigm of minimal change according to the seminal work by Alchourrón, Gärde…
Capturing Homomorphism-Closed Decidable Queries with Existential Rules
Camille Bourgaux, David Carral, Markus Krötzsch +2
Existential rules are a very popular ontology-mediated query language for which the chase represents a generic computational approach for query answering. It is straightforward tha…
The Price of Selfishness: Conjunctive Query Entailment for ALCSelf is 2ExpTime-hard
Bartosz Bednarczyk, Sebastian Rudolph
In logic-based knowledge representation, query answering has essentially replaced mere satisfiability checking as the inferencing problem of primary interest. For knowledge bases i…
A General Katsuno-Mendelzon-Style Characterization of AGM Belief Base Revision for Arbitrary Monotonic Logics
Faiq Miftakhul Falakh, Sebastian Rudolph, Kai Sauerwald
The AGM postulates by Alchourrón, Gärdenfors, and Makinson continue to represent a cornerstone in research related to belief change. We generalize the approach of Katsuno and Mende…
On Logics and Homomorphism Closure
Manuel Bodirsky, Thomas Feller, Simon Knäuer +1
Predicate logic is the premier choice for specifying classes of relational structures. Homomorphisms are key to describing correspondences between relational structures. Questions…
Finite Model Theory of the Triguarded Fragment and Related Logics
Emanuel Kieroński, Sebastian Rudolph
The Triguarded Fragment (TGF) is among the most expressive decidable fragments of first-order logic, subsuming both its two-variable and guarded fragments without equality. We show…
Knowledge Graphs Evolution and Preservation -- A Technical Report from ISWS 2019
Nacira Abbas, Kholoud Alghamdi, Mortaza Alinam +71
One of the grand challenges discussed during the Dagstuhl Seminar "Knowledge Graphs: New Directions for Knowledge Representation on the Semantic Web" and described in its report is…
A Journey to the Frontiers of Query Rewritability
Piotr Ostropolski-Nalewaja, Jerzy Marcinkowski, David Carral +1
This paper is about (first order) query rewritability in the context of theory-mediated query answering. The starting point of our journey is the FUS/FES conjecture, saying that if…
Datalog-Expressibility for Monadic and Guarded Second-Order Logic
Manuel Bodirsky, Simon Knäuer, Sebastian Rudolph
We characterise the sentences in Monadic Second-order Logic (MSO) that are over finite structures equivalent to a Datalog program, in terms of an existential pebble game. We also s…
Satisfiability and Query Answering in Description Logics with Global and Local Cardinality Constraints
Franz Baader, Bartosz Bednarczyk, Sebastian Rudolph
We introduce and investigate the expressive description logic (DL) ALCSCC++, in which the global and local cardinality constraints introduced in previous papers can be mixed. On th…
Neural Machine Translating from Natural Language to SPARQL
Xiaoyu Yin, Dagmar Gromann, Sebastian Rudolph
SPARQL is a highly powerful query language for an ever-growing number of Linked Data resources and Knowledge Graphs. Using it requires a certain familiarity with the entities in th…
Linked Open Data Validity -- A Technical Report from ISWS 2018
Tayeb Abderrahmani Ghor, Esha Agrawal, Mehwish Alam +68
Linked Open Data (LOD) is the publicly available RDF data in the Web. Each LOD entity is identfied by a URI and accessible via HTTP. LOD encodes globalscale knowledge potentially a…
On the Ontological Modeling of Trees
David Carral, Pascal Hitzler, Hilmar Lapp +1
Trees -- i.e., the type of data structure known under this name -- are central to many aspects of knowledge organization. We investigate some central design choices concerning the…
Bound Your Models! How to Make OWL an ASP Modeling Language
Sarah Alice Gaggl, Sebastian Rudolph, Lukas Schweizer
To exploit the Web Ontology Language OWL as an answer set programming (ASP) language, we introduce the notion of bounded model semantics, as an intuitive and computationally advant…
Worst-case Optimal Query Answering for Greedy Sets of Existential Rules and Their Subclasses
Sebastian Rudolph, Michaël Thomazo, Jean-François Baget +1
The need for an ontological layer on top of data, associated with advanced reasoning mechanisms able to exploit the semantics encoded in ontologies, has been acknowledged both in t…
Query Containment for Highly Expressive Datalog Fragments
Pierre Bourhis, Markus Krötzsch, Sebastian Rudolph
The containment problem of Datalog queries is well known to be undecidable. There are, however, several Datalog fragments for which containment is known to be decidable, most notab…