66 citations · 154 across the 21 of their papers we have counts for
13 papers · 1 filter
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…
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…
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…
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…
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…
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…
Nominals, Inverses, Counting, and Conjunctive Queries or: Why Infinity is your Friend!
Sebastian Rudolph, Birte Glimm
Description Logics are knowledge representation formalisms that provide, for example, the logical underpinning of the W3C OWL standards. Conjunctive queries, the standard query lan…
Type-elimination-based reasoning for the description logic SHIQbs using decision diagrams and disjunctive datalog
Sebastian Rudolph, Markus Krötzsch, Pascal Hitzler
We propose a novel, type-elimination-based method for reasoning in the description logic SHIQbs including DL-safe rules. To this end, we first establish a knowledge compilation met…