Log in

Relevant bibliographies by topics / Conjunctive Normal Form (CNF)

Contents

Journal articles

Academic literature on the topic 'Conjunctive Normal Form (CNF)'

Author: Grafiati

Published: 19 February 2023

Last updated: 20 February 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Conjunctive Normal Form (CNF).'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Conjunctive Normal Form (CNF)"

1

Chen, Wenxiang, Darrell Whitley, Adele Howe, and Brian Goldman. "Stochastic Local Search over Minterms on Structured SAT Instances." Proceedings of the International Symposium on Combinatorial Search 7, no. 1 (2021): 125–26. http://dx.doi.org/10.1609/socs.v7i1.18403.

Full text

Abstract:

We observed that Conjunctive Normal Form (CNF) encodings of structured SAT instances often have a set of consecutive clauses defined over a small number of Boolean variables. To exploit the pattern, we propose a transformation of CNF to an alternative representation, Conjunctive Minterm Canonical Form (CMCF). The transformation is a two-step process: CNF clauses are first partitioned into disjoint subsets such that each subset contains CNF clauses with shared Boolean variables. CNF clauses in each subset are then replaced by Minterm Canonical Form (i.e., partial solutions), which is found by e

APA, Harvard, Vancouver, ISO, and other styles

2

WU, WANGMING. "COMMUTATIVE IMPLICATIONS ON COMPLETE LATTICES." International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 02, no. 03 (1994): 333–41. http://dx.doi.org/10.1142/s0218488594000274.

Full text

Abstract:

This paper is devoted to the investigation of commutative implications on a complete lattice L. It is proved that the disjunctive normal form (DNF) of a linguistic composition * is included in the conjunctive normal form (CNF) of that *, i.e., DNF(*) ≤ CNF(*) holds, for a special family of t-norms, t-conorms and negations induced by commutative implications.

APA, Harvard, Vancouver, ISO, and other styles

3

Woodruff, David P. "Technical Perspective." ACM SIGMOD Record 51, no. 1 (2022): 86. http://dx.doi.org/10.1145/3542700.3542720.

Full text

Abstract:

Model counting is the problem of approximately counting the number |Sol(Φ)| of satisfying assignments to a given model Φ, which could, for example, be a formula in conjunctive normal form (CNF) or a formula in disjunctive normal form (DNF).

APA, Harvard, Vancouver, ISO, and other styles

4

Bruni, Renato. "On the orthogonalization of arbitrary Boolean formulae." Journal of Applied Mathematics and Decision Sciences 2005, no. 2 (2005): 61–74. http://dx.doi.org/10.1155/jamds.2005.61.

Full text

Abstract:

The orthogonal conjunctive normal form of a Boolean function is a conjunctive normal form in which any two clauses contain at least a pair of complementary literals. Orthogonal disjunctive normal form is defined similarly. Orthogonalization is the process of transforming the normal form of a Boolean function to orthogonal normal form. The problem is of great relevance in several applications, for example, in the reliability theory. Moreover, such problem is strongly connected with the well-known propositional satisfiability problem. Therefore, important complexity issues are involved. A genera

APA, Harvard, Vancouver, ISO, and other styles

5

Zhang, Zaijun, Daoyun Xu, and Jincheng Zhou. "A Structural Entropy Measurement Principle of Propositional Formulas in Conjunctive Normal Form." Entropy 23, no. 3 (2021): 303. http://dx.doi.org/10.3390/e23030303.

Full text

Abstract:

The satisfiability (SAT) problem is a core problem in computer science. Existing studies have shown that most industrial SAT instances can be effectively solved by modern SAT solvers while random SAT instances cannot. It is believed that the structural characteristics of different SAT formula classes are the reasons behind this difference. In this paper, we study the structural properties of propositional formulas in conjunctive normal form (CNF) by the principle of structural entropy of formulas. First, we used structural entropy to measure the complex structure of a formula and found that th

APA, Harvard, Vancouver, ISO, and other styles

6

Cepek, O., S. Gursky, and P. Kucera. "On Minimum Representations of Matched Formulas." Journal of Artificial Intelligence Research 51 (December 23, 2014): 707–23. http://dx.doi.org/10.1613/jair.4517.

Full text

Abstract:

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. Each matched CNF is trivially satisfiable (each clause can be satisfied by its representative variable). Another property which is easy to see, is that the class of matched CNFs is not closed under partial assignment of truth values to variables. This latter property leads to a fact (proved here) that given two matched CNFs it is co-NP complete to decide whether they are logically equivalent. The construction in thi

APA, Harvard, Vancouver, ISO, and other styles

7

Elffers, Jan, and Jakob Nordstrm. "A Cardinal Improvement to Pseudo-Boolean Solving." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 02 (2020): 1495–503. http://dx.doi.org/10.1609/aaai.v34i02.5508.

Full text

Abstract:

Pseudo-Boolean solvers hold out the theoretical potential of exponential improvements over conflict-driven clause learning (CDCL) SAT solvers, but in practice perform very poorly if the input is given in the standard conjunctive normal form (CNF) format. We present a technique to remedy this problem by recovering cardinality constraints from CNF on the fly during search. This is done by collecting potential building blocks of cardinality constraints during propagation and combining these blocks during conflict analysis. Our implementation has a non-negligible but manageable overhead when detec

APA, Harvard, Vancouver, ISO, and other styles

8

Heule, Marijn, Matti Järvisalo, Florian Lonsing, Martina Seidl, and Armin Biere. "Clause Elimination for SAT and QSAT." Journal of Artificial Intelligence Research 53 (June 26, 2015): 127–68. http://dx.doi.org/10.1613/jair.4694.

Full text

Abstract:

The famous archetypical NP-complete problem of Boolean satisfiability (SAT) and its PSPACE-complete generalization of quantified Boolean satisfiability (QSAT) have become central declarative programming paradigms through which real-world instances of various computationally hard problems can be efficiently solved. This success has been achieved through several breakthroughs in practical implementations of decision procedures for SAT and QSAT, that is, in SAT and QSAT solvers. Here, simplification techniques for conjunctive normal form (CNF) for SAT and for prenex conjunctive normal form (PCNF)

APA, Harvard, Vancouver, ISO, and other styles

9

Ohta, S. "CNF-SAT modelling for banyan-type networks and its application for assessing the rearrangeability." Journal of Physics: Conference Series 2090, no. 1 (2021): 012133. http://dx.doi.org/10.1088/1742-6596/2090/1/012133.

Full text

Abstract:

Abstract A banyan-type network is a switching network, which is constructed by placing unit switches with two inputs and two outputs in s (s > 1) stages. In each stage, 2 n – 1 (n > 1) unit switches are aligned. Past studies conjecture that this network becomes rearrangeable when s ≥ 2n-1. Although a considerable number of theoretical analyses have been done, the rearrangeability of the banyan-type network with 2n – 1 or more stages is not completely proved. As a tool to assess the rearrangeability, this study presents a CNF-SAT (conjunctive normal form - satisfiability) modelling scheme

APA, Harvard, Vancouver, ISO, and other styles

10

Giunchiglia, E., M. Narizzano, and A. Tacchella. "Clause/Term Resolution and Learning in the Evaluation of Quantified Boolean Formulas." Journal of Artificial Intelligence Research 26 (August 17, 2006): 371–416. http://dx.doi.org/10.1613/jair.1959.

Full text

Abstract:

Resolution is the rule of inference at the basis of most procedures for automated reasoning. In these procedures, the input formula is first translated into an equisatisfiable formula in conjunctive normal form (CNF) and then represented as a set of clauses. Deduction starts by inferring new clauses by resolution, and goes on until the empty clause is generated or satisfiability of the set of clauses is proven, e.g., because no new clauses can be generated. In this paper, we restrict our attention to the problem of evaluating Quantified Boolean Formulas (QBFs). In this setting, the above outli

APA, Harvard, Vancouver, ISO, and other styles

More sources

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!