Complexity thresholds in inclusion logic

Miika Hannula, Lauri Hella

Tutkimustuotos: ArtikkeliScientificvertaisarvioitu

6 Lataukset (Pure)

Abstrakti

Inclusion logic differs from many other logics of dependence and independence in that it can only describe polynomial-time properties. In this article we examine more closely connections between syntactic fragments of inclusion logic and different complexity classes. Our focus is on two computational problems: maximal subteam membership and the model checking problem for a fixed inclusion logic formula. We show that very simple quantifier-free formulae with one or two inclusion atoms generate instances of these problems that are complete for (non-deterministic) logarithmic space and polynomial time. We also present a safety game for the maximal subteam membership problem and use it to investigate this problem over teams in which one variable is a key. Furthermore, we relate our findings to consistent query answering over inclusion dependencies, and present a fragment of inclusion logic that captures non-deterministic logarithmic space in ordered models.

AlkuperäiskieliEnglanti
Artikkeli104759
JulkaisuInformation and Computation
Vuosikerta287
Varhainen verkossa julkaisun päivämäärä5 toukok. 2021
DOI - pysyväislinkit
TilaJulkaistu - 2022
OKM-julkaisutyyppiA1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä

Julkaisufoorumi-taso

  • Jufo-taso 2

!!ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Sormenjälki

Sukella tutkimusaiheisiin 'Complexity thresholds in inclusion logic'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä