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

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;]
Published on November 13, 2017
Volume 13, Issue 4

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;]
Published on September 14, 2023
Volume 19, Issue 3
  • < Previous
  • 1
  • Next >