No Cliques Allowed: The Next Step Towards BDD/FC Conjecture
This is an incremental step toward resolving a fundamental conjecture in existential rules for theoretical computer science.
The paper tackles the open problem of whether bounded derivation depth rule sets are finitely controllable, showing that universal models from such rule sets cannot contain arbitrarily large tournaments without implying a loop query, thereby narrowing potential counterexamples.
This paper addresses one of the fundamental open questions in the realm of existential rules: the conjecture on the finite controllability of bounded derivation depth rule sets (bdd $\Rightarrow$ fc). We take a step toward a positive resolution of this conjecture by demonstrating that universal models generated by bdd rule sets cannot contain arbitrarily large tournaments (arbitrarily directed cliques) without entailing a loop query, $\exists{x} E(x, x)$. This simple yet elegant result narrows the space of potential counterexamples to the (bdd $\Rightarrow$ fc) conjecture.