Author name cluster

Ondřej Čepek

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

1 author row

KR Conference 2025 Conference Paper

Boolean Nearest Neighbor Language in the Knowledge Compilation Map

Ondřej Čepek
Jelena Glišić

The Boolean Nearest Neighbor (BNN) representation of Boolean functions was recently introduced by Hajnal, Liu and Turan. A BNN representation of function f is a pair (P, N) of sets of Boolean vectors (called positive and negative prototypes) where f(x) = 1 for every positive prototype x ∈ P, f(x) = 0 for every negative prototype x ∈ N, and the value f(x) for x not in (P ∪ N) is determined by the type of the closest prototype. The main aim of this paper is to determine the position of the BNN language in the Knowledge Compilation Map (KCM). To this end, we settle the complexity status of most standard queries and transformations (those listed in KCM) for BNN inputs. We also compare the succinctness of the BNN language with several languages considered in KCM.

PDF Details DOI

TCS Journal 2022 Journal Article

Unique key Horn functions

Kristóf Bérczi
Endre Boros
Ondřej Čepek
Petr Kučera
Kazuhisa Makino

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 → v is an implicate of h. If K is a key of the database, then K → 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, improving on earlier results. 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.

Details DOI

TCS Journal 2021 Journal Article

Generating clause sequences of a CNF formula

Kristóf Bérczi
Endre Boros
Ondřej Čepek
Khaled Elbassioni
Petr Kučera
Kazuhisa Makino

Given a CNF formula Φ with clauses C 1, …, C m and variables V = { x 1, …, x n }, a truth assignment a: V → { 0, 1 } of Φ leads to a clause sequence σ Φ ( a ) = ( C 1 ( a ), …, C m ( a ) ) ∈ { 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.

Details DOI

JAIR Journal 2020 Journal Article

Properties of Switch-List Representations of Boolean Functions

Miloš Chromý
Ondřej Čepek

In this paper, we focus on a less usual way to represent Boolean functions, namely on representations by switch-lists, which are closely related to interval representations. Given a truth table representation of a Boolean function f the switch-list representation of f is a list of Boolean vectors from the truth table which have a different function value than the preceding Boolean vector in the truth table. The main aim of this paper is to include this type of representation in the Knowledge Compilation Map by Darwiche and Marquis and to argue that switch-lists may in certain situations constitute a reasonable choice for a target language in knowledge compilation. First, we compare switch-list representations with a number of standard representations (such as CNF, DNF, and OBDD) with respect to their relative succinctness. As a by-product of this analysis, we also give a short proof of a longstanding open question proposed by Darwiche and Marquis, namely the incomparability of MODS (models) and PI (prime implicates) representations. Next, using the succinctness result between switch-lists and OBDDs, we develop a polynomial time compilation algorithm from switch-lists to OBDDs. Finally, we analyze which standard transformations and queries (those considered by Darwiche and Marquis) can be performed in polynomial time with respect to the size of the input if the input knowledge is represented by a switch-list. We show that this collection is very broad and the combination of polynomial time transformations and queries is quite unique. Some of the queries can be answered directly using the switch-list input, others require a compilation of the input to OBDD representations which are then used to answer the queries.

PDF Details DOI

IJCAI Conference 2020 Conference Paper

Switch-List Representations in a Knowledge Compilation Map

Ondřej Čepek
Miloš Chromý

In this paper we focus on a less usual way to represent Boolean functions, namely on representations by switch-lists. Given a truth table representation of a Boolean function f the switch-list representation (SLR) of f is a list of Boolean vectors from the truth table which have a different function value than the preceding Boolean vector in the truth table. The main aim of this paper is to include the language SL of all SLR in the Knowledge Compilation Map [Darwiche and Marquis, 2002] and to argue, that SL may in certain situations constitute a reasonable choice for a target language in knowledge compilation. First we compare SL with a number of standard representation languages (such as CNF, DNF, and OBDD) with respect to their relative succinctness. As a by-product of this analysis we also give a short proof of a long standing open question from [Darwiche and Marquis, 2002], namely the incomparability of MODS (models) and PI (prime implicates) languages. Next we analyze which standard transformations and queries (those considered in [Darwiche and Marquis, 2002] can be performed in poly-time with respect to the size of the input SLR. We show that this collection is quite broad and the combination of poly-time transformations and queries is quite unique.

PDF Details DOI

IJCAI Conference 2017 Conference Paper

On Minimum Representations of Matched Formulas (Extended Abstract)

Ondřej Čepek
Štefan Gurský
Petr Kučera

A Boolean formula in conjunctive normal form (CNF) is called matched if the system of sets of variables which appear in individual clauses has a system of distinct representatives. We present here two results for matched CNFs: The first result is a shorter and simpler proof of the fact that Boolean minimization remains complete for the second level of polynomial hierarchy even if the input is restricted to matched CNFs. The second result is structural --- we show that if a Boolean function f admits a representation by a matched CNF then every clause minimum CNF representation of f is matched.

PDF Details

TCS Journal 2013 Journal Article

A decomposition method for CNF minimality proofs

Endre Boros
Ondřej Čepek
Petr Kučera

A CNF is minimal if no shorter CNF representing the same function exists, where by CNF length we mean either the number of clauses or the total number of literals (sum of clause lengths). In this paper we develop a decomposition approach that can be in certain situations applied to a CNF formula when proving its minimality. We give two examples in which this decomposition approach is used. Both examples deal with pure Horn minimization, a problem defined as follows: given a pure Horn CNF, construct a logically equivalent pure Horn CNF which is the shortest possible (either w. r. t. the number of clauses or w. r. t. the total number of literals). Both presented examples give alternative proofs of known complexity results for pure Horn minimization.

Details DOI

AIJ Journal 2013 Journal Article

Complexity issues related to propagation completeness

Martin Babka
Tomáš Balyo
Ondřej Čepek
Štefan Gurský
Petr Kučera
Václav Vlček

Knowledge compilation is a process of adding more information to a knowledge base in order to make it easier to deduce facts from the compiled base than from the original one. One type of knowledge compilation occurs when the knowledge in question is represented by a Boolean formula in conjunctive normal form (CNF). The goal of knowledge compilation in this case is to add clauses to the input CNF until a logically equivalent propagation complete CNF is obtained. A CNF is called propagation complete if after any partial substitution of truth values all logically entailed literals can be inferred from the resulting CNF formula by unit propagation. The key to this type of knowledge compilation is the ability to generate so-called empowering clauses. A clause is empowering for a CNF if it is an implicate and for some partial substitution of truth values it enlarges the set of entailed literals inferable by unit propagation. In this paper we study several complexity issues related to empowering implicates, propagation completeness, and its relation to resolution proofs. We show several results: (a) given a CNF and a clause it is co-NP complete to decide whether the clause is an empowering implicate of the CNF, (b) given a CNF it is NP-complete to decide whether there exists an empowering implicate for it and thus it is co-NP complete to decide whether a CNF is propagation complete, and (c) there exist CNFs to which an exponential number of clauses must be added to make them propagation complete.

Details DOI