Search

• < Previous
• 1
• Next >

---

Rewritability in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics

Cristina Feier ; Antti Kuusisto ; Carsten Lutz.

We study rewritability of monadic disjunctive Datalog programs, (the complements of) MMSNP sentences, and ontology-mediated queries (OMQs) based on expressive description logics of the ALC family and on conjunctive queries. We show that rewritability into FO and into monadic Datalog (MDLog) are&nbsp;[&hellip;]

---

The Complexity of Enriched Mu-Calculi

Piero A. Bonatti ; Carsten Lutz ; Aniello Murano ; Moshe Y. Vardi.

The fully enriched &mu;-calculus is the extension of the propositional &mu;-calculus with inverse programs, graded modalities, and nominals. While satisfiability in several expressive fragments of the fully enriched &mu;-calculus is known to be decidable and ExpTime-complete, it has recently been&nbsp;[&hellip;]

---

Modal Logics of Topological Relations

Carsten Lutz ; Frank Wolter.

Logical formalisms for reasoning about relations between spatial regions play a fundamental role in geographical information systems, spatial and constraint databases, and spatial reasoning in AI. In analogy with Halpern and Shoham's modal logic of time intervals based on the Allen relations, we&nbsp;[&hellip;]

---

The Data Complexity of Description Logic Ontologies

Carsten Lutz ; Frank Wolter.

We analyze the data complexity of ontology-mediated querying where the ontologies are formulated in a description logic (DL) of the ALC family and queries are conjunctive queries, positive existential queries, or acyclic conjunctive queries. Our approach is non-uniform in the sense that we aim to&nbsp;[&hellip;]

---

The Data Complexity of Ontology-Mediated Queries with Closed Predicates

Carsten Lutz ; Inanc Seylan ; Frank Wolter.

In the context of ontology-mediated querying with description logics (DLs), we study the data complexity of queries in which selected predicates can be closed (OMQCs). We provide a non-uniform analysis, aiming at a classification of the complexity into tractable and non-tractable for ontologies in&nbsp;[&hellip;]

---

Answer Counting under Guarded TGDs

Cristina Feier ; Carsten Lutz ; Marcin Przybyłko.

We study the complexity of answer counting for ontology-mediated queries and for querying under constraints, considering conjunctive queries and unions thereof (UCQs) as the query language and guarded TGDs as the ontology and constraint language, respectively. Our main result is a classification&nbsp;[&hellip;]

---