Source author record

Ondřej Čepek

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics Databases Logic in Computer Science

Catalog footprint

Research overview

2works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Generating clause sequences of a CNF formula

Given a CNF formula $Φ$ with clauses $C_1,\ldots,C_m$ and variables $V=\{x_1,\ldots,x_n\}$ , a truth assignment $a:V\rightarrow\{0,1\}$ of $Φ$ leads to a clause sequence $σ_Φ(a)=(C_1(a),\ldots,C_m(a))\in\{0,1\}^m$ where $C_i(a) = 1$ if clause $C_i$ evaluates to $1$ under assignment $a$ , otherwise $C_i(a) = 0$ . The set of all possible clause sequences carries a lot of information on the formula, e.g. SAT, MAX-SAT and MIN-SAT can be encoded in terms of finding a clause sequence with extremal properties. We consider a problem posed at Dagstuhl Seminar 19211 "Enumeration in Data Management" (2019) about the generation of all possible clause sequences of a given CNF with bounded dimension. We prove that the problem can be solved in incremental polynomial time. We further give an algorithm with polynomial delay for the class of tractable CNF formulas. We also consider the generation of maximal and minimal clause sequences, and show that generating maximal clause sequences is NP-hard, while minimal clause sequences can be generated with polynomial delay.

preprint2020arXiv

Unique key Horn functions

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 defines a pure Horn function $h$ , representing the functional dependencies. If the knowledge of the attribute values in set $A$ determines the value for attribute $v$ , then $A\rightarrow v$ is an implicate of $h$ . If $K$ is a key of the database, then $K\rightarrow v$ is an implicate of $h$ for all attributes $v$ . Keys of small sizes play a crucial role in various problems. We present structural and complexity results on the set of minimal keys of pure Horn functions. We characterize Sperner hypergraphs for which there is a unique pure Horn function with the given hypergraph as the set of minimal keys. Furthermore, we show that recognizing such hypergraphs is co-NP-complete already when every hyperedge has size two. On the positive side, we identify several classes of graphs for which the recognition problem can be decided in polynomial time. We also present an algorithm that generates the minimal keys of a pure Horn function with polynomial delay. By establishing a connection between keys and target sets, our approach can be used to generate all minimal target sets with polynomial delay when the thresholds are bounded by a constant. As a byproduct, our proof shows that the Minimum Key problem is at least as hard as the Minimum Target Set Selection problem with bounded thresholds.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.