135 citations · 302 across the 18 of their papers we have counts for
19 papers
Recovering Explanations from Transformed Rule-Based Ontologies
Alex Ivliev, Markus Krötzsch, Maximilian Marx
Datalog rules are often used to define ontologies over Knowledge Graphs. Rule reasoners routinely optimise such ontologies by rewriting their rules into a form that can be evaluate…
Stratified Negation in RDF Rules: A Correct Approach (Extended Version)
Nils Küchenmeister, Alex Ivliev, Dörthe Arndt +1
Combining RDF rule languages, such as N3 or SHACL Rules, with default negation is challenging. Existing methods to stratify negation often fail for RDF rules, since individual trip…
Evaluating a Visual Query Tracer and Builder for Learning Declarative Logic Programming
Julián Méndez, Lukas Gerlach, Tobias Wieland +3
Nemo Explain Visualizer (nev) is an interactive visual query tracer and builder for Nemo, a powerful Datalog reasoner with extended features. Our tools were developed with and for…
Chase Termination Beyond Polynomial Time
Philipp Hanisch, Markus Krötzsch
The chase is a widely implemented approach to reason with tuple-generating dependencies (tgds), used in data exchange, data integration, and ontology-based query answering. However…
Nemo: First Glimpse of a New Rule Engine
Alex Ivliev, Stefan Ellmauthaler, Lukas Gerlach +4
This system demonstration presents Nemo, a new logic programming engine with a focus on reliability and performance. Nemo is built for data-centric analytic computations, modelled…
Efficient Dependency Analysis for Rule-Based Ontologies
Larry González, Alex Ivliev, Markus Krötzsch +1
Several types of dependencies have been proposed for the static analysis of existential rule ontologies, promising insights about computational properties and possible practical us…
Deciding Hyperproperties Combined with Functional Specifications
Raven Beutner, David Carral, Bernd Finkbeiner +2
We study satisfiability for HyperLTL with a quantifier prefix, known to be highly undecidable in general. HyperLTL can express system properties that relate mu…
Expressivity of Planning with Horn Description Logic Ontologies (Technical Report)
Stefan Borgwardt, Jörg Hoffmann, Alisa Kovtunova +3
State constraints in AI Planning globally restrict the legal environment states. Standard planning languages make closed-domain and closed-world assumptions. Here we address open-w…
Answering Queries with Negation over Existential Rules
Stefan Ellmauthaler, Markus Krötzsch, Stephan Mennicke
Ontology-based query answering with existential rules is well understood and implemented for positive queries, in particular conjunctive queries. The situation changes drastically…
Partially Ordered Automata and Piecewise Testability
Tomáš Masopust, Markus Krötzsch
Partially ordered automata are automata where the transition relation induces a partial order on states. The expressive power of partially ordered automata is closely related to th…
Universality of Confluent, Self-Loop Deterministic Partially Ordered NFAs is Hard
Tomáš Masopust, Markus Krötzsch
An automaton is partially ordered if the only cycles in its transition diagram are self-loops. The expressivity of partially ordered NFAs (poNFAs) can be characterized by the Strau…
Complexity of Universality and Related Problems for Partially Ordered NFAs
Markus Krötzsch, Tomáš Masopust, Michaël Thomazo
Partially ordered nondeterminsitic finite automata (poNFAs) are NFAs whose transition relation induces a partial order on states, that is, for which cycles occur only in the form o…
Column-Oriented Datalog Materialization for Large Knowledge Graphs (Extended Technical Report)
Jacopo Urbani, Ceriel Jacobs, Markus Krötzsch
The evaluation of Datalog rules over large Knowledge Graphs (KGs) is essential for many applications. In this paper, we present a new method of materializing Datalog inferences, wh…
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…
Acyclicity Notions for Existential Rules and Their Application to Query Answering in Ontologies
Bernardo Cuenca Grau, Ian Horrocks, Markus Krötzsch +4
Answering conjunctive queries (CQs) over a set of facts extended with existential rules is a prominent problem in knowledge representation and databases. This problem can be solved…
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…
OWL: Yet to arrive on the Web of Data?
Birte Glimm, Aidan Hogan, Markus Krötzsch +1
Seven years on from OWL becoming a W3C recommendation, and two years on from the more recent OWL 2 W3C recommendation, OWL has still experienced only patchy uptake on the Web. Alth…
A Description Logic Primer
Markus Krötzsch, Frantisek Simancik, Ian Horrocks
This paper provides a self-contained first introduction to description logics (DLs). The main concepts and features are explained with examples before syntax and semantics of the D…
A Categorical View on Algebraic Lattices in Formal Concept Analysis
Pascal Hitzler, Markus Krötzsch, Guo-Qiang Zhang
Formal concept analysis has grown from a new branch of the mathematical field of lattice theory to a widely recognized tool in Computer Science and elsewhere. In order to fully ben…