Academic literature on the topic 'Conjunctive Normal Form (CNF)'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
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 (September 1, 2021): 125–26. http://dx.doi.org/10.1609/socs.v7i1.18403.
Full textAbstract:
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 enumeration. We show empirically that a simple Stochastic Local Search (SLS) solver based on CMCF can consistently achieve a higher success rate using fewer evaluations than the SLS solver WalkSAT on two representative classes of structured SAT problems.
2
WU, WANGMING. "COMMUTATIVE IMPLICATIONS ON COMPLETE LATTICES." International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 02, no. 03 (September 1994): 333–41. http://dx.doi.org/10.1142/s0218488594000274.
Full textAbstract:
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.
3
Woodruff, David P. "Technical Perspective." ACM SIGMOD Record 51, no. 1 (May 31, 2022): 86. http://dx.doi.org/10.1145/3542700.3542720.
Full textAbstract:
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).
4
Bruni, Renato. "On the orthogonalization of arbitrary Boolean formulae." Journal of Applied Mathematics and Decision Sciences 2005, no. 2 (January 1, 2005): 61–74. http://dx.doi.org/10.1155/jamds.2005.61.
Full textAbstract:
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 general procedure for transforming an arbitrary CNF or DNF to an orthogonal one is proposed. Such procedure is tested on randomly generated Boolean formulae.
5
Zhang, Zaijun, Daoyun Xu, and Jincheng Zhou. "A Structural Entropy Measurement Principle of Propositional Formulas in Conjunctive Normal Form." Entropy 23, no. 3 (March 4, 2021): 303. http://dx.doi.org/10.3390/e23030303.
Full textAbstract:
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 the difficulty solving the formula is related to the structural entropy of the formula. The smaller the compressing information of a formula, the more difficult it is to solve the formula. Secondly, we proposed a λ-approximation strategy to approximate the structural entropy of large formulas. The experimental results showed that the proposed strategy can effectively approximate the structural entropy of the original formula and that the approximation ratio is more than 92%. Finally, we analyzed the structural properties of a formula in the solution process and found that a local search solver tends to select variables in different communities to perform the next round of searches during a search and that the structural entropy of a variable affects the probability of the variable being flipped. By using these conclusions, we also proposed an initial candidate solution generation strategy for a local search for SAT, and the experimental results showed that this strategy effectively improves the performance of the solvers CCAsat and Sparrow2011 when incorporated into these two solvers.
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 textAbstract:
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 this proof leads to another result: a much shorter and simpler proof of the fact that the Boolean minimization problem for matched CNFs is a complete problem for the second level of the polynomial hierarchy. The main result of this paper deals with the structure of clause minimum CNFs. We prove here that if a Boolean function f admits a representation by a matched CNF then every clause minimum CNF representation of f is matched.
7
Elffers, Jan, and Jakob Nordstrm. "A Cardinal Improvement to Pseudo-Boolean Solving." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 02 (April 3, 2020): 1495–503. http://dx.doi.org/10.1609/aaai.v34i02.5508.
Full textAbstract:
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 detection is not successful, and yields significant gains for some SAT competition and crafted benchmarks for which pseudo-Boolean reasoning is stronger than CDCL. It also boosts performance for some native pseudo-Boolean formulas where this approach helps to improve learned constraints.
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 textAbstract:
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) for QSAT---the standard input formats of SAT and QSAT solvers---have recently proven very effective in increasing solver efficiency when applied before (i.e., in preprocessing) or during (i.e., in inprocessing) satisfiability search. In this article, we develop and analyze clause elimination procedures for pre- and inprocessing. Clause elimination procedures form a family of (P)CNF formula simplification techniques which remove clauses that have specific (in practice polynomial-time) redundancy properties while maintaining the satisfiability status of the formulas. Extending known procedures such as tautology, subsumption, and blocked clause elimination, we introduce novel elimination procedures based on asymmetric variants of these techniques, and also develop a novel family of so-called covered clause elimination procedures, as well as natural liftings of the CNF-level procedures to PCNF. We analyze the considered clause elimination procedures from various perspectives. Furthermore, for the variants not preserving logical equivalence under clause elimination, we show how to reconstruct solutions to original CNFs from satisfying assignments to simplified CNFs, which is important for practical applications for the procedures. Complementing the more theoretical analysis, we present results on an empirical evaluation on the practical importance of the clause elimination procedures in terms of the effect on solver runtimes on standard real-world application benchmarks. It turns out that the importance of applying the clause elimination procedures developed in this work is empirically emphasized in the context of state-of-the-art QSAT solving.
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 (November 1, 2021): 012133. http://dx.doi.org/10.1088/1742-6596/2090/1/012133.
Full textAbstract:
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 for banyan-type networks. In the proposed scheme, the routing is formulated to a SAT problem represented in CNF. By feeding the problem to a SAT solver, it is found whether the problem is satisfiable or unsatisfiable. If the problem is unsatisfiable for a certain request, the network is not rearrangeable. By contrast, if the problem is satisfiable for any requests, the network is rearrangeable. This study applies the CNF-SAT modelling scheme to various configurations of 2n – 1 stage banyan-type networks. These networks are assessed for rearrangeability by solving the SAT problems. The proposed method will be helpful to conduct future theoretical studies on banyan-type networks.
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 textAbstract:
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 outlined deduction process is known to be sound and complete if given a formula in CNF and if a form of resolution, called ``Q-resolution'', is used. We introduce Q-resolution on terms, to be used for formulas in disjunctive normal form. We show that the computation performed by most of the available procedures for QBFs --based on the Davis-Logemann-Loveland procedure (DLL) for propositional satisfiability-- corresponds to a tree in which Q-resolution on terms and clauses alternate. This poses the theoretical bases for the introduction of learning, corresponding to recording Q-resolution formulas associated with the nodes of the tree. We discuss the problems related to the introduction of learning in DLL based procedures, and present solutions extending state-of-the-art proposals coming from the literature on propositional satisfiability. Finally, we show that our DLL based solver extended with learning, performs significantly better on benchmarks used in the 2003 QBF solvers comparative evaluation.
Dissertations / Theses on the topic "Conjunctive Normal Form (CNF)"
1
Duong, Thach-Thao Nguyen. "Improving Diversification in Local Search for Propositional Satisfiability." Thesis, Griffith University, 2014. http://hdl.handle.net/10072/365717.
Full textAbstract:
In recent years, the Propositional Satisfiability (SAT) has become standard for encoding real world complex constrained problems. SAT has significant impacts on various research fields in Artificial Intelligence (AI) and Constraint Programming (CP). SAT algorithms have also been successfully used in solving many practical and industrial applications that include electronic design automation, default reasoning, diagnosis, planning, scheduling, image interpretation, circuit design, and hardware and software verification. The most common representation of a SAT formula is the Conjunctive Normal Form (CNF). A CNF formula is a conjunction of clauses where each clause is a disjunction of Boolean literals. A SAT formula is satisfiable if there is a truth assignment for each variable such that all clauses in the formula are satisfied. Solving a SAT problem is to determine a truth assignment that satisfies a CNF formula. SAT is the first problem proved to be NP-complete [20]. There are many algorithmic methodologies to solve SAT. The most obvious one is systematic search; however another popular and successful approach is stochastic local search (SLS). Systematic search is usually referred to as complete search or backtrack-style search. In contrast, SLS is a method to explore the search space by randomisation and perturbation operations. Although SLS is an incomplete search method, it is able to find the solutions effectively by using limited time and resources. Moreover, some SLS solvers can solve hard SAT problems in a few minutes while these problems could be beyond the capacity of systematic search solvers.Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Information and Communication Technology
Science, Environment, Engineering and Technology
Full Text
2
Grim, Pavel. "Převod výrazů v C do DIMACS formátu." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2015. http://www.nusl.cz/ntk/nusl-234975.
Full textAbstract:
This work focuses on proposition of transfer of the expressions entered in the C programming language into DIMACS format and creation of program in programming language C++ making this transfer. This work contains a description of the C programming language and its operators. It also contains a description of the conjunctive normal form and a description of the DIMACS format. Following is a proposal for a program for the transfer of expression in the C programming language to the DIMACS format and description of realization of program performing this transfer.
3
Forrester, David M. "Fuzzy Cellular Automata in Conjunctive Normal Form." Thèse, Université d'Ottawa / University of Ottawa, 2011. http://hdl.handle.net/10393/19987.
Full textAbstract:
Cellular automata (CA) are discrete dynamical systems comprised of a lattice of finite-state cells. At each time step, each cell updates its state as a function of the previous state of itself and its neighbours.
Fuzzy cellular automata (FCA) are a real-valued extension of Boolean cellular automata which "fuzzifies" Boolean logic in the transition function using real values between zero and one (inclusive). To date, FCA have only been studied in disjunctive normal form (DNF).
In this thesis, we study FCA in conjunctive normal form (CNF). We classify FCA in CNF both analytically and empirically. We compare these classes to their DNF counterparts. We prove that certain FCA exhibit chaos in CNF, in contrast to the periodic behaviours of DNF FCA. We also briefly explore five different forms of fuzzy logic, and suggest further study. In support of this research, we introduce novel methods of simulating and visualizing FCA.
4
Steinke, Peter [Verfasser], Steffen [Gutachter] Hölldobler, and Armin [Gutachter] Biere. "Pseudo-Boolean Constraint Encodings for Conjunctive Normal Form and their Applications / Peter Steinke ; Gutachter: Steffen Hölldobler, Armin Biere." Dresden : Technische Universität Dresden, 2020. http://d-nb.info/1227196822/34.
Full text
5
Sheridan, Daniel. "Temporal logic encodings for SAT-based bounded model checking." Thesis, University of Edinburgh, 2006. http://hdl.handle.net/1842/1467.
Full textAbstract:
Since its introduction in 1999, bounded model checking (BMC) has quickly become a serious and indispensable tool for the formal verification of hardware designs and, more recently, software. By leveraging propositional satisfiability (SAT) solvers, BMC overcomes some of the shortcomings of more conventional model checking methods. In model checking we automatically verify whether a state transition system (STS) describing a design has some property, commonly expressed in linear temporal logic (LTL). BMC is the restriction to only checking the looping and non-looping runs of the system that have bounded descriptions. The conventional BMC approach is to translate the STS runs and LTL formulae into propositional logic and then conjunctive normal form (CNF). This CNF expression is then checked by a SAT solver. In this thesis we study the effect on the performance of BMC of changing the translation to propositional logic. One novelty is to use a normal form for LTL which originates in resolution theorem provers. We introduce the normal form conversion early on in the encoding process and examine the simplifications that it brings to the generation of propositional logic. We further enhance the encoding by specialising the normal form to take advantage of the types of runs peculiar to BMC. We also improve the conversion from propositional logic to CNF. We investigate the behaviour of the new encodings by a series of detailed experimental comparisons using both hand-crafted and industrial benchmarks from a variety of sources. These reveal that the new normal form based encodings can reduce the solving time by a half in most cases, and up to an order of magnitude in some cases, the size of the improvement corresponding to the complexity of the LTL expression. We also compare our method to the popular automata-based methods for model checking and BMC.
6
Pham, Duc Nghia, and n/a. "Modelling and Exploiting Structures in Solving Propositional Satisfiability Problems." Griffith University. Institute for Integrated and Intelligent Systems, 2006. http://www4.gu.edu.au:8080/adt-root/public/adt-QGU20070216.143447.
Full textAbstract:
Recent research has shown that it is often preferable to encode real-world problems as propositional satisfiability (SAT) problems and then solve using a general purpose SAT solver. However, much of the valuable information and structure of these realistic problems is flattened out and hidden inside the corresponding Conjunctive Normal Form (CNF) encodings of the SAT domain. Recently, systematic SAT solvers have been progressively improved and are now able to solve many highly structured practical problems containing millions of clauses. In contrast, state-of-the-art Stochastic Local Search (SLS) solvers still have difficulty in solving structured problems, apparently because they are unable to exploit hidden structure as well as the systematic solvers. In this thesis, we study and evaluate different ways to effectively recognise, model and efficiently exploit useful structures hidden in realistic problems. A summary of the main contributions is as follows: 1. We first investigate an off-line processing phase that applies resolution-based pre-processors to input formulas before running SLS solvers on these problems. We report an extensive empirical examination of the impact of SAT pre-processing on the performance of contemporary SLS techniques. It emerges that while all the solvers examined do indeed benefit from pre-processing, the effects of different pre-processors are far from uniform across solvers and across problems. Our results suggest that SLS solvers need to be equipped with multiple pre-processors if they are ever to match the performance of systematic solvers on highly structured problems. [Part of this study was published at the AAAI-05 conference]. 2. We then look at potential approaches to bridging the gap between SAT and constraint satisfaction problem (CSP) formalisms. One approach has been to develop a many-valued SAT formalism (MV-SAT) as an intermediate paradigm between SAT and CSP, and then to translate existing highly efficient SAT solvers to the MV-SAT domain. In this study, we follow a different route, developing SAT solvers that can automatically recognise CSP structure hidden in SAT encodings. This allows us to look more closely at how constraint weighting can be implemented in the SAT and CSP domains. Our experimental results show that a SAT-based mechanism to handle weights, together with a CSP-based method to instantiate variables, is superior to other combinations of SAT and CSP-based approaches. In addition, SLS solvers based on this many-valued weighting approach outperform other existing approaches to handle many-valued CSP structures. [Part of this study was published at the AAAI-05 conference]. 3. Finally, we propose and evaluate six different schemes to encode temporal reasoning problems, in particular the Interval Algebra (IA) networks, into SAT CNF formulas. We then empirically examine the performance of local search as well as systematic solvers on the new temporal SAT representations, in comparison with solvers that operate on native IA representations. Our empirical results show that zChaff (a state-of-the-art complete SAT solver) together with the best IA-to-SAT encoding scheme, can solve temporal problems significantly faster than existing IA solvers working on the equivalent native IA networks. [Part of this study was published at the CP-05 workshop].
7
Pham, Duc Nghia. "Modelling and Exploiting Structures in Solving Propositional Satisfiability Problems." Thesis, Griffith University, 2006. http://hdl.handle.net/10072/365503.
Full textAbstract:
Recent research has shown that it is often preferable to encode real-world problems as propositional satisfiability (SAT) problems and then solve using a general purpose SAT solver. However, much of the valuable information and structure of these realistic problems is flattened out and hidden inside the corresponding Conjunctive Normal Form (CNF) encodings of the SAT domain. Recently, systematic SAT solvers have been progressively improved and are now able to solve many highly structured practical problems containing millions of clauses. In contrast, state-of-the-art Stochastic Local Search (SLS) solvers still have difficulty in solving structured problems, apparently because they are unable to exploit hidden structure as well as the systematic solvers. In this thesis, we study and evaluate different ways to effectively recognise, model and efficiently exploit useful structures hidden in realistic problems. A summary of the main contributions is as follows: 1. We first investigate an off-line processing phase that applies resolution-based pre-processors to input formulas before running SLS solvers on these problems. We report an extensive empirical examination of the impact of SAT pre-processing on the performance of contemporary SLS techniques. It emerges that while all the solvers examined do indeed benefit from pre-processing, the effects of different pre-processors are far from uniform across solvers and across problems. Our results suggest that SLS solvers need to be equipped with multiple pre-processors if they are ever to match the performance of systematic solvers on highly structured problems. [Part of this study was published at the AAAI-05 conference]. 2. We then look at potential approaches to bridging the gap between SAT and constraint satisfaction problem (CSP) formalisms. One approach has been to develop a many-valued SAT formalism (MV-SAT) as an intermediate paradigm between SAT and CSP, and then to translate existing highly efficient SAT solvers to the MV-SAT domain. In this study, we follow a different route, developing SAT solvers that can automatically recognise CSP structure hidden in SAT encodings. This allows us to look more closely at how constraint weighting can be implemented in the SAT and CSP domains. Our experimental results show that a SAT-based mechanism to handle weights, together with a CSP-based method to instantiate variables, is superior to other combinations of SAT and CSP-based approaches. In addition, SLS solvers based on this many-valued weighting approach outperform other existing approaches to handle many-valued CSP structures. [Part of this study was published at the AAAI-05 conference]. 3. Finally, we propose and evaluate six different schemes to encode temporal reasoning problems, in particular the Interval Algebra (IA) networks, into SAT CNF formulas. We then empirically examine the performance of local search as well as systematic solvers on the new temporal SAT representations, in comparison with solvers that operate on native IA representations. Our empirical results show that zChaff (a state-of-the-art complete SAT solver) together with the best IA-to-SAT encoding scheme, can solve temporal problems significantly faster than existing IA solvers working on the equivalent native IA networks. [Part of this study was published at the CP-05 workshop].Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
Institute for Integrated and Intelligent Systems
Full Text
8
Steinke, Peter. "Pseudo-Boolean Constraint Encodings for Conjunctive Normal Form and their Applications." 2019. https://tud.qucosa.de/id/qucosa%3A38409.
Full textAbstract:
In contrast to a single clause a pseudo-Boolean (PB) constraint is much more expressive and hence it is easier to define problems with the help of PB constraints. But while PB constraints provide us with a high-level problem description, it has been shown that solving PB constraints can be done faster with the help of a SAT solver. To apply such a solver to a PB constraint we have to encode it with clauses into conjunctive normal form (CNF). While we can find a basic encoding into CNF which is equivalent to a given PB constraint, the solving time of a SAT solver significantly depends on different properties of an encoding, e.g. the number of clauses or if generalized arc consistency (GAC) is maintained during the search for a solution.
There are various PB encodings that try to optimize or balance these properties. This thesis is about such encodings. For a better understanding of the research field an overview about the state-of-the art encodings is given. The focus of the overview is a simple but complete description of each encoding, such that any reader could use, implement and extent them in his own work. In addition two novel encodings are presented: The Sequential Weight Counter (SWC) encoding and the Binary Merger Encoding. While the SWC encoding provides a very simple structure – it is listed in four lines – empirical evaluation showed its practical usefulness in various applications. The Binary Merger encoding reduces the number of clauses a PB encoding needs while having the important GAC property. To the best of our knowledge currently no other encoding has a lower upper bound for the number of clauses produced by a PB encoding with this property. This is an important improvement of the state-of-the art, since both GAC and a low number of clauses are vital for an improved solving time of the SAT solver. The thesis also contributes to the development of new applications for PB constraint encodings. The programming library PBLib provides researchers with an open source implementation of almost all PB encodings – including the encodings for the special cases at-most-one and cardinality constraints. The PBLib is also the foundation of the presented weighted MaxSAT solver optimax, the PBO solver pbsolver and the WBO, PBO and weighted MaxSAT solver npSolver.
9
Illner, Petr. "Kompilace KNF do backdoor decomposable monotone circuit." Master's thesis, 2021. http://www.nusl.cz/ntk/nusl-451073.
Full textAbstract:
An NNF circuit is a directed acyclic graph (DAG), where each leaf is labelled with either true/false or a literal, and each inner node represents either a conjunction (∧) or a disjunction (∨). A decomposable NNF (DNNF) is an NNF satisfying the decomposabi- lity property for each conjunction node. The C-BDMC language generalizes the DNNF language. In a C-BDMC, the leaves can contain CNF formulae from a given base class C. In this paper, we focus only on renamable Horn formulae. We experimentally compare the sizes of d-BDMC and d-DNNF representations. We describe a new compilation langu- age, called cara DNNF (c-DNNF), that generalizes the DNNF language. A c-DNNF circuit can be considered as a compressed representation of a DNNF circuit. We present a new experimental knowledge compiler, called CaraCompiler, for converting a CNF formula into a d-BDMC or a (c)d-DNNF circuit. CaraCompiler is based on the state-of-the-art compiler D4. Also, we mention some extensions for the compiler D4, such as caching hypergraph cuts that can reduce the compilation times. 1
Books on the topic "Conjunctive Normal Form (CNF)"
1
Gluckman, Sir Peter, Mark Hanson, Chong Yap Seng, and Anne Bardsley. Vitamin B12 (cobalamin) in pregnancy and breastfeeding. Oxford University Press, 2015. http://dx.doi.org/10.1093/med/9780198722700.003.0013.
Full textAbstract:
Vitamin B12 is required for the synthesis of fatty acids and myelin and so is crucial for normal neurological function and maintenance of the CNS. In conjunction with folate, it is involved in red blood cell formation and DNA synthesis, and in embryogenesis, it is important for proper neural tube formation and brain development. Maternal intake during pregnancy is important, as only newly absorbed vitamin B12, and not that stored in the maternal liver, is concentrated in the placenta. Despite the active transfer during pregnancy, the vitamin B12 content in the newborn is low, and the infant is dependent on breast milk for ongoing needs. Pregnant and lactating women should ensure that their diet contains sufficient (animal) sources of vitamin B12; those consuming vegan or strict vegetarian diets should either take vitamin B12 supplements or seek foods that have been fortified with vitamin B12.
Book chapters on the topic "Conjunctive Normal Form (CNF)"
1
Lin, Yi, Lucas M. Tabajara, and Moshe Y. Vardi. "ZDD Boolean Synthesis." In Tools and Algorithms for the Construction and Analysis of Systems, 64–83. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-030-99524-9_4.
Full textAbstract:
AbstractMotivated by applications in boolean-circuit design, boolean synthesis is the process of synthesizing a boolean function with multiple outputs, given a relation between its inputs and outputs. Previous work has attempted to solve boolean functional synthesis by converting a specification formula into a Binary Decision Diagram (BDD) and quantifying existentially the output variables. We make use of the fact that the specification is usually given in the form of a Conjunctive Normal Form (CNF) formula, and we can perform resolution on a symbolic representation of a CNF formula in the form of a Zero-suppressed Binary Decision Diagram (ZDD). We adapt the realizability test to the context of CNF and ZDD, and show that the Cross operation defined in earlier work can be used for witness construction. Experiments show that our approach is complementary to BDD-based Boolean synthesis.
2
Shultz, Thomas R., Scott E. Fahlman, Susan Craw, Periklis Andritsos, Panayiotis Tsaparas, Ricardo Silva, Chris Drummond, et al. "Conjunctive Normal Form." In Encyclopedia of Machine Learning, 209–10. Boston, MA: Springer US, 2011. http://dx.doi.org/10.1007/978-0-387-30164-8_158.
Full text
3
Pfahringer, Bernhard. "Conjunctive Normal Form." In Encyclopedia of Machine Learning and Data Mining, 260–61. Boston, MA: Springer US, 2017. http://dx.doi.org/10.1007/978-1-4899-7687-1_158.
Full text
4
Dantsin, Evgeny, and Alexander Wolpert. "Reconstruction of Boolean Formulas in Conjunctive Normal Form." In Lecture Notes in Computer Science, 592–601. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-94776-1_49.
Full text
5
Jabbour, Said, Joao Marques-Silva, Lakhdar Sais, and Yakoub Salhi. "Enumerating Prime Implicants of Propositional Formulae in Conjunctive Normal Form." In Logics in Artificial Intelligence, 152–65. Cham: Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-11558-0_11.
Full text
6
Kuznetsov, Stepan. "Conjunctive Grammars in Greibach Normal Form and the Lambek Calculus with Additive Connectives." In Formal Grammar, 242–49. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-39998-5_15.
Full text
7
Prestwich, Steven. "Chapter 2. CNF Encodings." In Frontiers in Artificial Intelligence and Applications. IOS Press, 2021. http://dx.doi.org/10.3233/faia200985.
Full textAbstract:
Before a combinatorial problem can be solved by current SAT methods, it must usually be encoded in conjunctive normal form, which facilitates algorithm implementation and allows a common file format for problems. Unfortunately there are several ways of encoding most problems and few guidelines on how to choose among them, yet the choice of encoding can be as important as the choice of search algorithm. This chapter reviews theoretical and empirical work on encoding methods, including the use of Tseitin encodings, the encoding of extensional and intensional constraints, the interaction between encodings and search algorithms, and some common sources of error. Case studies are used for illustration.
8
Drechsler, Rolf, Tommi Junttila, and Ilkka Niemelä. "Chapter 27. Non-Clausal SAT and ATPG." In Frontiers in Artificial Intelligence and Applications. IOS Press, 2021. http://dx.doi.org/10.3233/faia201011.
Full textAbstract:
When studying the propositional satisfiability problem (SAT), that is, the problem of deciding whether a propositional formula is satisfiable, it is typically assumed that the formula is given in the conjunctive normal form (CNF). Also most software tools for deciding satisfiability of a formula (SAT solvers) assume that their input is in CNF. An important reason for this is that it is simpler to develop efficient data structures and algorithms for CNF than for arbitrary formulas. On the other hand, using CNF makes efficient modeling of an application cumbersome. Therefore one often employs a more general formula representation in modeling and then transforms the formula into CNF for SAT solvers. Transforming a propositional formula in CNF either increases the formula size exponentially or requires the use of auxiliary variables, which can have an negative effect on the performance of a SAT solver in the worst-case. Moreover, by translating to CNF one often loses information about the structure of the original problem. In this chapter we survey methods for solving propositional satisfiability problems when the input formula is not given in CNF but as a general formula or even more compactly as a Boolean circuit. We show how the techniques applied in CNF level Davis-Putnam-Loveland-Logemann algorithm generalize to Boolean circuits and how the problem structure available in the circuit form can be exploited. Then we consider a closely related area of automatic test pattern generation (ATPG) for digital circuits and review classical ATPG algorithms, formulation of ATPG as a SAT problem, and advanced techniques for SAT-based ATPG.
9
Uvarov, Sergey I. "Empirical Evaluation of the Asymptotic Behavior of the Analysis Complexity of Hard Random 3-CNF Formulas." In Machine Learning and Artificial Intelligence. IOS Press, 2022. http://dx.doi.org/10.3233/faia220420.
Full textAbstract:
This paper continued the study of the complexity behavior of the satisfiability analysis of hard random formulas given in the conjunctive normal form (CNF). In the 3-CNF formula, each clause contains three literals of logical variables. The number of logical variables in the formula is N. In this paper, the SAT solver is improved by introducing equality reduction and pure literal identification procedures. The solver improvement reduced the exponent (with base 2) from N/20.86 to N/21.41 with an R=4.6 ratio of the number of clauses to the number of variables. The results show that the efficiency of the pure literals identification procedure decreases as R increases. An important part of the study is an empirical estimation of the algorithmic complexity of the SAT problem with large number of variables. The proposed method gives a convenient lower bound on the complexity of analysis for random 3-CNF formulas. We estimated the algorithmic complexity for the range N=256÷8192. The exponential dependence of complexity on N for random 3-CNF formulas at a fixed value of R is demonstrated in this range.
10
Biere, Armin, Matti Järvisalo, and Benjamin Kiesl. "Chapter 9. Preprocessing in SAT Solving." In Frontiers in Artificial Intelligence and Applications. IOS Press, 2021. http://dx.doi.org/10.3233/faia200992.
Full textAbstract:
Preprocessing has become a key component of the Boolean satisfiability (SAT) solving workflow. In practice, preprocessing is situated between the encoding phase and the solving phase, with the aim of decreasing the total solving time by applying efficient simplification techniques on SAT instances to speed up the search subsequently performed by a SAT solver. In this chapter, we overview key preprocessing techniques proposed in the literature. While the main focus is on techniques applicable to formulas in conjunctive normal form (CNF), we also selectively cover main ideas for preprocessing structural and higher-level SAT instance representations.
Conference papers on the topic "Conjunctive Normal Form (CNF)"
1
Lei, Zhendong, Shaowei Cai, and Chuan Luo. "Extended Conjunctive Normal Form and An Efficient Algorithm for Cardinality Constraints." In Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}. California: International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/ijcai.2020/159.
Full textAbstract:
Satisfiability (SAT) and Maximum Satisfiability (MaxSAT) are two basic and important constraint problems with many important applications. SAT and MaxSAT are expressed in CNF, which is difficult to deal with cardinality constraints. In this paper, we introduce Extended Conjunctive Normal Form (ECNF), which expresses cardinality constraints straightforward and does not need auxiliary variables or clauses. Then, we develop a simple and efficient local search solver LS-ECNF with a well designed scoring function under ECNF. We also develop a generalized Unit Propagation (UP) based algorithm to generate the initial solution for local search. We encode instances from Nurse Rostering and Discrete Tomography Problems into CNF with three different cardinality constraint encodings and ECNF respectively. Experimental results show that LS-ECNF has much better performance than state of the art MaxSAT, SAT, Pseudo-Boolean and ILP solvers, which indicates solving cardinality constraints with ECNF is promising.
2
Selman, Joe, Mohamed Amer, Alan Fern, and Sinisa Todorovic. "PEL-CNF: Probabilistic event logic conjunctive normal form for video interpretation." In 2011 IEEE International Conference on Computer Vision Workshops (ICCV Workshops). IEEE, 2011. http://dx.doi.org/10.1109/iccvw.2011.6130308.
Full text
3
Gdansky, N. I., and A. A. Denisov. "METHODS OF REDUCING OF LARGE BOOLEAN FORMULAS REPRESENTED IN A CONJUNCTIVE NORMAL FORM FOR DETERMINING THEIR SATISFIABILITY." In STATE AND DEVELOPMENT PROSPECTS OF AGRIBUSINESS. DSTU-PRINT, 2020. http://dx.doi.org/10.23947/interagro.2020.1.472-475.
Full textAbstract:
The article explores the satisfiability of conjunctive normal forms used in modeling systems.The problems of CNF preprocessing are considered.The analysis of particular methods for reducing this formulas, which have polynomial input complexity is given.
4
Čepek, Ondřej, Štefan Gurský, and Petr Kučera. "On Minimum Representations of Matched Formulas (Extended Abstract)." In Twenty-Sixth International Joint Conference on Artificial Intelligence. California: International Joint Conferences on Artificial Intelligence Organization, 2017. http://dx.doi.org/10.24963/ijcai.2017/706.
Full textAbstract:
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.
5
Pan, Weiyu. "Optimal Conjunctive Normal Form Encoding for Symbolic Execution." In The 33rd International Conference on Software Engineering and Knowledge Engineering. KSI Research Inc., 2021. http://dx.doi.org/10.18293/seke2021-113.
Full text
6
Fu, Zhaohui, and Sharad Malik. "Extracting Logic Circuit Structure from Conjunctive Normal Form Descriptions." In 20th International Conference on VLSI Design held jointly with 6th International Conference on Embedded Systems (VLSID'07). IEEE, 2007. http://dx.doi.org/10.1109/vlsid.2007.81.
Full text
7
Otten, Jens. "nanoCoP: Natural Non-clausal Theorem Proving." In Twenty-Sixth International Joint Conference on Artificial Intelligence. California: International Joint Conferences on Artificial Intelligence Organization, 2017. http://dx.doi.org/10.24963/ijcai.2017/695.
Full textAbstract:
Most efficient fully automated theorem provers implement proof search calculi that require the input formula to be in a clausal form, i.e. disjunctive or conjunctive normal form. The translation into clausal form introduces a significant overhead to the proof search and modifies the structure of the original formula. Translating a proof in clausal form back into a more readable non-clausal proof of the original formula is not straightforward. This paper presents a non-clausal automated theorem prover for classical first-order logic. It is based on a non-clausal connection calculus and implemented with a few lines of Prolog code. Working entirely on the original structure of the input formula yields not only a speed up of the proof search, but the resulting non-clausal proofs are also shorter.
8
Yang, Yichao, Jiayue Shen, Mark A. Levenstein, and Zhili Hao. "Preliminary Study of a Polymer-Based Microfluidic Device for Detecting Distributed Shear Loads." In ASME 2014 International Mechanical Engineering Congress and Exposition. American Society of Mechanical Engineers, 2014. http://dx.doi.org/10.1115/imece2014-36670.
Full textAbstract:
This paper reports on a polymer-based microfluidic device for detecting distributed shear loads. This device is comprised of a symmetric 3D polydimethylsiloxane (PDMS) microstructure, two electrolyte-filled microchannels embedded underneath the microstructure, and a set of electrode pairs distributed along the length of each microchannel. In conjunction with its electrode pairs, one body of electrolyte in each microchannel functions as distributed resistive transducers along the microchannel length. The 3D microstructure is built into a rectangular block with a narrow shear-loading bump on its top. The edges of the bump are aligned right at the width centers of the two microchannels. Thus, distributed shear loads acting on the bump translate to normal loads of opposite directions on the tops of the two microchannels, and consequently opposite geometrical changes in the microchannels, which register as resistance changes by the distributed resistive transducers. Together with a CNC mold, a two-mask photolithographic fabrication process is employed to fabricate a prototype device. The fabricated device is tested using a custom experimental setup. The experimental results validate the design concept of the device and further show that the device exhibits a linear response to shear loads with good repeatability.
9
Xu, Zhe, and Ufuk Topcu. "Transfer of Temporal Logic Formulas in Reinforcement Learning." In Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}. California: International Joint Conferences on Artificial Intelligence Organization, 2019. http://dx.doi.org/10.24963/ijcai.2019/557.
Full textAbstract:
Transferring high-level knowledge from a source task to a target task is an effective way to expedite reinforcement learning (RL). For example, propositional logic and first-order logic have been used as representations of such knowledge. We study the transfer of knowledge between tasks in which the timing of the events matters. We call such tasks temporal tasks. We concretize similarity between temporal tasks through a notion of logical transferability, and develop a transfer learning approach between different yet similar temporal tasks. We first propose an inference technique to extract metric interval temporal logic (MITL) formulas in sequential disjunctive normal form from labeled trajectories collected in RL of the two tasks. If logical transferability is identified through this inference, we construct a timed automaton for each sequential conjunctive subformula of the inferred MITL formulas from both tasks. We perform RL on the extended state which includes the locations and clock valuations of the timed automata for the source task. We then establish mappings between the corresponding components (clocks, locations, etc.) of the timed automata from the two tasks, and transfer the extended Q-functions based on the established mappings. Finally, we perform RL on the extended state for the target task, starting with the transferred extended Q-functions. Our implementation results show, depending on how similar the source task and the target task are, that the sampling efficiency for the target task can be improved by up to one order of magnitude by performing RL in the extended state space, and further improved by up to another order of magnitude using the transferred extended Q-functions.
10
Villarreal, Anthony A., Constantine Tarawneh, Miguel Ontiveros, James Aranda, and Robert Jones. "Prototyping a Conductive Polymer Steering Pad for Rail Freight Service." In 2019 Joint Rail Conference. American Society of Mechanical Engineers, 2019. http://dx.doi.org/10.1115/jrc2019-1286.
Full textAbstract:
The AdapterPlus™ steering pad is a polymer component on a railcar that helps to reduce stresses on the axle as a railcar rounds a curve. One railway application requires a minimum of 240 mA to be passed through the steering pad to the rail, which activates air valves that control automated cargo gates. Currently, two copper studs are inserted into the pad to provide a conductive path. However, after continuous cyclic loading caused by normal service operation, the copper studs deform, wear, and eventually lose contact between the two surfaces rendering the pad nonconductive. One proposed solution to this problem is to create a steering pad made entirely from an electrically conductive material. The University Transportation Center for Railway Safety (UTCRS) research team has successfully created a conductive nanocomposite made from vapor grown carbon nanofibers (CNFs) and a modified form of Elastollan 1195A thermoplastic polyurethane (TPU). Previous attempts to create this material were promising but failed to produce an electrically conductive specimen when injection molded. Preliminary results have shown that the new material can be injection molded to create an electrically conductive test specimen. An injection molded insert was designed, fabricated, and incorporated into the existing steering pad design for further testing. Pressure measurement film had previously been used to find the points of maximum stress inside the pad to optimize the design of the composite insert. Characterization of the resistivity of the composite material was carried out in order to verify functionality in future iterations of this product. The resistance of the composite material is expected to be non-linear with a strong dependence on load and voltage. Conductivity tests were performed using a material testing system with a compressive load ranging from 1500 pounds to 5500 pounds. The voltage at each load was also varied between 10V to 20V and the nonlinear resistance of the material was examined. The results have shown that the CNF/TPU composite is a potential replacement for the current TPU used for the pad and, with minimal modifications, can be implemented in field service operation.