6 papers
Unique key Horn functions
Kristóf Bérczi, Endre Boros, Ondřej Čepek +2
Given a relational database, a key is a set of attributes such that a value assignment to this set uniquely determines the values of all other attributes. The database uniquely def…
Generating clause sequences of a CNF formula
Kristóf Bérczi, Endre Boros, Ondřej Čepek +3
Given a CNF formula with clauses and variables , a truth assignment of leads to a clause sequence $σ_Φ(a)=(C_…
Bounds on the size of PC and URC formulas
Petr Kučera, Petr Savický
In this paper we investigate CNF formulas, for which the unit propagation is strong enough to derive a contradiction if the formula together with a partial assignment of the variab…
Backdoor Decomposable Monotone Circuits and their Propagation Complete Encodings
Petr Kučera, Petr Savický
We describe a compilation language of backdoor decomposable monotone circuits (BDMCs) which generalizes several concepts appearing in the literature, e.g. DNNFs and backdoor trees.…
Approximating minimum representations of key Horn functions
Kristóf Bérczi, Endre Boros, Ondřej Čepek +2
Horn functions form a subclass of Boolean functions and appear in many different areas of computer science and mathematics as a general tool to describe implications and dependenci…
Phase Transition in Matched Formulas and a Heuristic for Biclique Satisfiability
Miloš Chromý, Petr Kučera
A matched formula is a CNF formula whose incidence graph admits a matching which matches a distinct variable to every clause. We study phase transition in a context of matched form…