On the BDD/FC conjecture

Tomasz Gogacz; Jerzy Marcinkowski

doi:10.1145/2463664.2463668

On the BDD/FC conjecture

Tomasz Gogacz, Jerzy Marcinkowski

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract / Description of output

Bounded Derivation Depth property (BDD) and Finite Controllability (FC) are two properties of sets of datalog rules and tuple generating dependencies (known as Datalog3 programs), which recently attracted some attention. We conjecture that the first of these properties implies the second, and support this conjecture by some evidence proving, among other results, that it holds true for all theories over binary signature.

Original language	English
Title of host publication	PODS '13 Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems
Publisher	ACM
Pages	127-138
Number of pages	12
ISBN (Print)	978-1-4503-2066-5
DOIs	https://doi.org/10.1145/2463664.2463668
Publication status	Published - 2013

Access to Document

10.1145/2463664.2463668

http://dl.acm.org/citation.cfm?doid=2463664.2463668

Cite this

@inproceedings{e3ab6c4c27534b44aeffc8bcdbb275b8,

title = "On the BDD/FC conjecture",

abstract = "Bounded Derivation Depth property (BDD) and Finite Controllability (FC) are two properties of sets of datalog rules and tuple generating dependencies (known as Datalog3 programs), which recently attracted some attention. We conjecture that the first of these properties implies the second, and support this conjecture by some evidence proving, among other results, that it holds true for all theories over binary signature.",

author = "Tomasz Gogacz and Jerzy Marcinkowski",

year = "2013",

doi = "10.1145/2463664.2463668",

language = "English",

isbn = "978-1-4503-2066-5",

pages = "127--138",

booktitle = "PODS '13 Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems",

publisher = "ACM",

}

TY - GEN

T1 - On the BDD/FC conjecture

AU - Gogacz, Tomasz

AU - Marcinkowski, Jerzy

PY - 2013

Y1 - 2013

N2 - Bounded Derivation Depth property (BDD) and Finite Controllability (FC) are two properties of sets of datalog rules and tuple generating dependencies (known as Datalog3 programs), which recently attracted some attention. We conjecture that the first of these properties implies the second, and support this conjecture by some evidence proving, among other results, that it holds true for all theories over binary signature.

AB - Bounded Derivation Depth property (BDD) and Finite Controllability (FC) are two properties of sets of datalog rules and tuple generating dependencies (known as Datalog3 programs), which recently attracted some attention. We conjecture that the first of these properties implies the second, and support this conjecture by some evidence proving, among other results, that it holds true for all theories over binary signature.

U2 - 10.1145/2463664.2463668

DO - 10.1145/2463664.2463668

M3 - Conference contribution

SN - 978-1-4503-2066-5

SP - 127

EP - 138

BT - PODS '13 Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems

PB - ACM

ER -