Search


Volume

Author

Year

  • < Previous
  • 1
  • Next >
3 results

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;]
Published on September 22, 2008
Volume 4, Issue 3

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;]
Published on May 23, 2019
Volume 15, Issue 2

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;]
Published on August 28, 2019
Volume 15, Issue 3
  • < Previous
  • 1
  • Next >