Adding Path-Functional Dependencies to the Guarded Two-Variable Fragment with Counting

Ian Pratt-Hartmann, Georgios Kourtis

Research output: Contribution to journalArticlepeer-review

Abstract

The satisfiability and finite satisfiability problems for the two-variable guarded
fragment of first-order logic with counting quantifiers, a database, and path-functional dependencies are both ExpTime-complete.
Original languageEnglish
Article number4
Pages (from-to)1-39
Number of pages39
JournalLogical Methods in Computer Science
Volume13
Issue number4
DOIs
Publication statusPublished - 30 Oct 2017

Keywords

  • satisfiability
  • two-variable fragmet
  • guarded fragment
  • counting quantifiers
  • integrity constraints
  • key constraints
  • path-functional dependencies

Fingerprint

Dive into the research topics of 'Adding Path-Functional Dependencies to the Guarded Two-Variable Fragment with Counting'. Together they form a unique fingerprint.

Cite this