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

Ian Pratt-Hartmann; Georgios Kourtis

doi:10.23638/LMCS-13(4:4)2017

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

Ian Pratt-Hartmann, Georgios Kourtis

Formal Methods

Research output: Contribution to journal › Article › peer-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 language	English
Article number	4
Pages (from-to)	1-39
Number of pages	39
Journal	Logical Methods in Computer Science
Volume	13
Issue number	4
DOIs	https://doi.org/10.23638/LMCS-13(4:4)2017
Publication status	Published - 30 Oct 2017

Keywords

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

Access to Document

10.23638/LMCS-13(4:4)2017Licence: CC BY-ND

Cite this

@article{f0fc0cca5e5f4fcbbc4be711d35d0866,

title = "Adding Path-Functional Dependencies to the Guarded Two-Variable Fragment with Counting",

abstract = "The satisfiability and finite satisfiability problems for the two-variable guardedfragment of first-order logic with counting quantifiers, a database, and path-functional dependencies are both ExpTime-complete.",

keywords = "satisfiability, two-variable fragmet, guarded fragment, counting quantifiers, integrity constraints, key constraints, path-functional dependencies",

author = "Ian Pratt-Hartmann and Georgios Kourtis",

year = "2017",

month = oct,

day = "30",

doi = "10.23638/LMCS-13(4:4)2017",

language = "English",

volume = "13",

pages = "1--39",

journal = "Logical Methods in Computer Science",

issn = "1860-5974",

publisher = "Logical Methods in Computer Science",

number = "4",

}

TY - JOUR

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

AU - Pratt-Hartmann, Ian

AU - Kourtis, Georgios

PY - 2017/10/30

Y1 - 2017/10/30

N2 - The satisfiability and finite satisfiability problems for the two-variable guardedfragment of first-order logic with counting quantifiers, a database, and path-functional dependencies are both ExpTime-complete.

AB - The satisfiability and finite satisfiability problems for the two-variable guardedfragment of first-order logic with counting quantifiers, a database, and path-functional dependencies are both ExpTime-complete.

KW - satisfiability

KW - two-variable fragmet

KW - guarded fragment

KW - counting quantifiers

KW - integrity constraints

KW - key constraints

KW - path-functional dependencies

U2 - 10.23638/LMCS-13(4:4)2017

DO - 10.23638/LMCS-13(4:4)2017

M3 - Article

SN - 1860-5974

VL - 13

SP - 1

EP - 39

JO - Logical Methods in Computer Science

JF - Logical Methods in Computer Science

IS - 4

M1 - 4

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this