Log in

Relevant bibliographies by topics / Boolean Satisfiability problem

Contents

Journal articles
Dissertations / Theses
Books
Book chapters
Conference papers

Academic literature on the topic 'Boolean Satisfiability problem'

Author: Grafiati

Published: 4 June 2021

Last updated: 5 February 2022

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 'Boolean Satisfiability problem.'

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 "Boolean Satisfiability problem"

1

Dixon, H. E., M. L. Ginsberg, D. Hofer, E. M. Luks, and A. J. Parkes. "Generalizing Boolean Satisfiability III: Implementation." Journal of Artificial Intelligence Research 23 (April 1, 2005): 441–531. http://dx.doi.org/10.1613/jair.1656.

Full text

Abstract:

This is the third of three papers describing ZAP, a satisfiability engine that substantially generalizes existing tools while retaining the performance characteristics of modern high-performance solvers. The fundamental idea underlying ZAP is that many problems passed to such engines contain rich internal structure that is obscured by the Boolean representation used; our goal has been to define a representation in which this structure is apparent and can be exploited to improve computational performance. The first paper surveyed existing work that (knowingly or not) exploited problem structure

APA, Harvard, Vancouver, ISO, and other styles

2

LYNCE, INÊS, and JOÃO MARQUES-SILVA. "HAPLOTYPE INFERENCE WITH BOOLEAN SATISFIABILITY." International Journal on Artificial Intelligence Tools 17, no. 02 (2008): 355–87. http://dx.doi.org/10.1142/s0218213008003935.

Full text

Abstract:

Mutation in DNA is the principal cause for differences among human beings, and Single Nucleotide Polymorphisms (SNPs) are the most common mutations. Hence, a fundamental task is to complete a map of haplotypes (which identify SNPs) in the human population. Associated with this effort, a key computational problem is the inference of haplotype data from genotype data, since in practice genotype data rather than haplotype data is usually obtained. Different haplotype inference approaches have been proposed, including the utilization of statistical methods and the utilization of the pure parsimony

APA, Harvard, Vancouver, ISO, and other styles

3

Ali M. Ali Rushdi, Ali M. Ali Rushdi. "Satisfiability in Big Boolean Algebras via Boolean-Equation Solving." journal of King Abdulaziz University Engineering Sciences 28, no. 1 (2017): 3–18. http://dx.doi.org/10.4197/eng.28-1.1.

Full text

Abstract:

This paper studies Satisfiability (SAT) in finite atomic Boolean algebras larger than the two-valued one B2, which are named big Boolean algebras. Unlike the formula ݃(ࢄ (in the SAT problem over B2, which is either satisfiable or unsatisfiable, this formula for the SAT problem over a big Boolean algebra could be unconditionally satisfiable, conditionally satisfiable, or unsatisfiable depending on the nature of the consistency condition of the Boolean equation {݃(ࢄ = (1}, since this condition could be an identity, a genuine equation, or a contradiction. The paper handles this latter SAT problem

APA, Harvard, Vancouver, ISO, and other styles

4

BRAHA, DAN. "Design-as-satisfiability: A new approach to automated synthesis." Artificial Intelligence for Engineering Design, Analysis and Manufacturing 15, no. 5 (2001): 385–99. http://dx.doi.org/10.1017/s0890060401155022.

Full text

Abstract:

This article addresses computational synthesis systems that attempt to find a structural description that matches a set of initial functional requirements and design constraints with a finite sequence of production rules. It has been previously shown by the author that it is computationally difficult to identify a sequence of production rules that can lead to a satisficing design solution. As a result, computational synthesis, particularly with large volumes of selection information, requires effective design search procedures. Many computational synthesis systems utilize transformational sear

APA, Harvard, Vancouver, ISO, and other styles

5

Budinich, Marco. "The Boolean SATisfiability Problem in Clifford algebra." Theoretical Computer Science 784 (September 2019): 1–10. http://dx.doi.org/10.1016/j.tcs.2019.03.027.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Dixon, H. E., M. L. Ginsberg, E. M. Luks, and A. J. Parkes. "Generalizing Boolean Satisfiability II: Theory." Journal of Artificial Intelligence Research 22 (December 1, 2004): 481–534. http://dx.doi.org/10.1613/jair.1555.

Full text

Abstract:

This is the second of three planned papers describing ZAP, a satisfiability engine that substantially generalizes existing tools while retaining the performance characteristics of modern high performance solvers. The fundamental idea underlying ZAP is that many problems passed to such engines contain rich internal structure that is obscured by the Boolean representation used; our goal is to define a representation in which this structure is apparent and can easily be exploited to improve computational performance. This paper presents the theoretical basis for the ideas underlying ZAP, arguing

APA, Harvard, Vancouver, ISO, and other styles

7

Pedrycz, W., G. Succi, and O. Shai. "Genetic-fuzzy approach to the Boolean satisfiability problem." IEEE Transactions on Evolutionary Computation 6, no. 5 (2002): 519–25. http://dx.doi.org/10.1109/tevc.2002.804915.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Li, Xiao-Wei, Guang-Hui Li, and Ming Shao. "Formal Verification Techniques Based on Boolean Satisfiability Problem." Journal of Computer Science and Technology 20, no. 1 (2005): 38–47. http://dx.doi.org/10.1007/s11390-005-0004-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

OSTROWSKI, RICHARD, and LIONEL PARIS. "FROM XSAT TO SAT BY EXHIBITING BOOLEAN FUNCTIONS." International Journal on Artificial Intelligence Tools 18, no. 05 (2009): 783–99. http://dx.doi.org/10.1142/s0218213009000408.

Full text

Abstract:

Given a Boolean formula in conjunctive normal form (CNF), the Exact Satisfiability problem (XSAT), a variant of the Satisfiability problem (SAT), consists in finding an assignment to the variables such that each clause contains exactly one satisfied literal. Best algorithms to solve this problem run in [Formula: see text] ([Formula: see text] for X3SAT). Another possibility is to transform each clause in a set of equivalent clauses for the Satisfiability problem and to use modern and powerful solvers (zChaff, Berkmin, MiniSat, RSat etc.) to find such truth assignment. In this paper we introduc

APA, Harvard, Vancouver, ISO, and other styles

10

HEAD, TOM. "PHOTOCOMPUTING: EXPLORATIONS WITH TRANSPARENCY AND OPACITY." Parallel Processing Letters 17, no. 04 (2007): 339–47. http://dx.doi.org/10.1142/s0129626407003071.

Full text

Abstract:

We continue to search for methods of parallel computing using light. An algorithm for solving instances of the Boolean satisfiability problem is given and illustrated using a photocopying machine with plastic transparencies as medium. The algorithm solves satisfiability problems in linear time but requires the assumption that information can be stored with a density that is exponential in the number of variables in the problem instance. Consideration is given to situations in which this density limitation is not quite absolute.

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic "Boolean Satisfiability problem"

1

Pari, Pushkin Raj. "Several issues on the boolean satisfiability (SAT) problem." College Park, Md. : University of Maryland, 2004. http://hdl.handle.net/1903/1427.

Full text

Abstract:

Thesis (M.S.) -- University of Maryland, College Park, 2004.<br>Thesis research directed by: Dept. of Electrical Engineering. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.

APA, Harvard, Vancouver, ISO, and other styles

2

Hoessen, Benoît. "Solving the Boolean satisfiability problem using the parallel paradigm." Thesis, Artois, 2014. http://www.theses.fr/2014ARTO0406/document.

Full text

Abstract:

Cette thèse présente différentes techniques permettant de résoudre le problème de satisfaction de formule booléenes utilisant le parallélisme et du calcul distribué. Dans le but de fournir une explication la plus complète possible, une présentation détaillée de l'algorithme CDCL est effectuée, suivi d'un état de l'art. De ce point de départ, deux pistes sont explorées. La première est une amélioration d'un algorithme de type portfolio, permettant d'échanger plus d'informations sans perte d'efficacité. La seconde est une bibliothèque de fonctions avec son interface de programmation permettant d

APA, Harvard, Vancouver, ISO, and other styles

3

Nguyen, Van-Hau. "SAT Encodings of Finite CSPs." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2015. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-162186.

Full text

Abstract:

Boolean satisfiability (SAT) is the problem of determining whether there exists an assignment of the Boolean variables to the truth values such that a given Boolean formula evaluates to true. SAT was the first example of an NP-complete problem. Only two decades ago SAT was mainly considered as of a theoretical interest. Nowadays, the picture is very different. SAT solving becomes mature and is a successful approach for tackling a large number of applications, ranging from artificial intelligence to industrial hardware design and verification. SAT solving consists of encodings and solvers. In

APA, Harvard, Vancouver, ISO, and other styles

4

Ghasemzadeh, Mohammad. "A new algorithm for the quantified satisfiability problem, based on zero-suppressed binary decision diagrams and memoization." Phd thesis, [S.l.] : [s.n.], 2005. http://deposit.ddb.de/cgi-bin/dokserv?idn=978444213.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Yeum, Ji-A. "Probability of Solvability of Random Systems of 2-Linear Equations over GF(2)." Columbus, Ohio : Ohio State University, 2008. http://rave.ohiolink.edu/etdc/view?acc%5Fnum=osu1230149164.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Trigueiros, F. P. Maria-José. "Applications booléennes et projections polyèdrales." Grenoble INPG, 1994. http://www.theses.fr/1994INPG0060.

Full text

Abstract:

Dans cette thèse, nous présentons une généralisation de l'approche polyédrale classique du problème de satisfiabilité d'un ensemble de fonctions booléennes {fl,…, fm} à n variables. Nous proposons d'élargir la représentation spatiale au graphe d'une application booléenne f = (fl,…, fm). Autrement dit, nous construisons le sous-ensemble des points de l'hypercube de dimension n+m dont les coordonnées sont les lignes de la table de vérité de fl,…, fm. Nous considérons ensuite l'enveloppe convexe de ces points. L'objet de ce travail est de donner un large ensemble d'applications booléennes dont le

APA, Harvard, Vancouver, ISO, and other styles

7

Siala, Mohamed. "Search, propagation, and learning in sequencing and scheduling problems." Thesis, Toulouse, INSA, 2015. http://www.theses.fr/2015ISAT0008/document.

Full text

Abstract:

Les problèmes de séquencement et d'ordonnancement forment une famille de problèmes combinatoires qui implique la programmation dans le temps d'un ensemble d'opérations soumises à des contraintes de capacités et de ressources. Nous contribuons dans cette thèse à la résolution de ces problèmes dans un contexte de satisfaction de contraintes et d'optimisation combinatoire. Nos propositions concernent trois aspects différents: comment choisir le prochain nœud à explorer (recherche)? comment réduire efficacement l'espace de recherche (propagation)? et que peut-on apprendre des échecs rencontrés lor

APA, Harvard, Vancouver, ISO, and other styles

8

Lonlac, Konlac Jerry Garvin. "Contributions à la résolution du problème de la Satisfiabilité Propositionnelle." Thesis, Artois, 2014. http://www.theses.fr/2014ARTO0404/document.

Full text

Abstract:

Dans cette thèse, nous nous intéressons à la résolution du problème de la satisfiabilité propositionnelle (SAT). Ce problème fondamental en théorie de la complexité est aujourd'hui utilisé dans de nombreux domaines comme la planification, la bio-informatique, la vérification de matériels et de logiciels. En dépit d'énormes progrès observés ces dernières années dans la résolution pratique du problème SAT, il existe encore une forte demande d'algorithmes efficaces pouvant permettre de résoudre les problèmes difficiles. C'est dans ce contexte que se situent les différentes contributions apportées

APA, Harvard, Vancouver, ISO, and other styles

9

Goultiaeva, Alexandra. "Exploiting Problem Structure in QBF Solving." Thesis, 2014. http://hdl.handle.net/1807/44111.

Full text

Abstract:

Deciding the truth of a Quantified Boolean Formula (QBF) is a canonical PSPACE-complete problem. It provides a powerful framework for encoding problems that lie in PSPACE. These include many problems in automatic verification, and problems with discrete uncertainty or non-determinism. Two person adversarial games are another type of problem that are naturally encoded in QBF. It is standard practice to use Conjunctive Normal Form (CNF) when representing QBFs. Any propositional formula can be efficiently translated to CNF via the addition of new variables, and solvers can be implemented more ef

APA, Harvard, Vancouver, ISO, and other styles

10

Nguyen, Van-Hau. "SAT Encodings of Finite CSPs." Doctoral thesis, 2014. https://tud.qucosa.de/id/qucosa%3A28571.

Full text

Abstract:

Boolean satisfiability (SAT) is the problem of determining whether there exists an assignment of the Boolean variables to the truth values such that a given Boolean formula evaluates to true. SAT was the first example of an NP-complete problem. Only two decades ago SAT was mainly considered as of a theoretical interest. Nowadays, the picture is very different. SAT solving becomes mature and is a successful approach for tackling a large number of applications, ranging from artificial intelligence to industrial hardware design and verification. SAT solving consists of encodings and solvers. In

APA, Harvard, Vancouver, ISO, and other styles

Books on the topic "Boolean Satisfiability problem"

1

The satisfiability problem. Elsevier, 1999.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Boolean Satisfiability problem"

1

Hsiang, Jieh, and Guan Huang. "Some fundamental properties of Boolean ring normal forms." In Satisfiability Problem: Theory and Applications. American Mathematical Society, 1997. http://dx.doi.org/10.1090/dimacs/035/16.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Milano, Michela, and Andrea Roli. "Solving the Satisfiability Problem Through Boolean Networks." In AI*IA 99: Advances in Artificial Intelligence. Springer Berlin Heidelberg, 2000. http://dx.doi.org/10.1007/3-540-46238-4_7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Maknickas, Algirdas Antano. "Linear Programming Formulation of Boolean Satisfiability Problem." In Lecture Notes in Electrical Engineering. Springer Netherlands, 2013. http://dx.doi.org/10.1007/978-94-007-7684-5_22.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Makino, Kazuhisa, Suguru Tamaki, and Masaki Yamamoto. "An Exact Algorithm for the Boolean Connectivity Problem for k-CNF." In Theory and Applications of Satisfiability Testing – SAT 2010. Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-14186-7_15.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Heule, Marijn J. H., Oliver Kullmann, and Victor W. Marek. "Solving and Verifying the Boolean Pythagorean Triples Problem via Cube-and-Conquer." In Theory and Applications of Satisfiability Testing – SAT 2016. Springer International Publishing, 2016. http://dx.doi.org/10.1007/978-3-319-40970-2_15.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Liu, Minghao, Fan Zhang, Pei Huang, Shuzi Niu, Feifei Ma, and Jian Zhang. "Learning the Satisfiability of Pseudo-Boolean Problem with Graph Neural Networks." In Lecture Notes in Computer Science. Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-58475-7_51.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Genitrini, Antoine, and Cécile Mailler. "Equivalence Classes of Random Boolean Trees and Application to the Catalan Satisfiability Problem." In LATIN 2014: Theoretical Informatics. Springer Berlin Heidelberg, 2014. http://dx.doi.org/10.1007/978-3-642-54423-1_41.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Semenov, Alexander, and Oleg Zaikin. "Using Monte Carlo Method for Searching Partitionings of Hard Variants of Boolean Satisfiability Problem." In Lecture Notes in Computer Science. Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-21909-7_21.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Ansótegui, Carlos, and Felip Manyà. "Mapping Problems with Finite-Domain Variables to Problems with Boolean Variables." In Theory and Applications of Satisfiability Testing. Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11527695_1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Teige, Tino, and Martin Fränzle. "Generalized Craig Interpolation for Stochastic Boolean Satisfiability Problems." In Tools and Algorithms for the Construction and Analysis of Systems. Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-19835-9_14.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Boolean Satisfiability problem"

1

Hartley, Stephen J. "Steiner systems and the Boolean satisfiability problem." In the 1996 ACM symposium. ACM Press, 1996. http://dx.doi.org/10.1145/331119.331192.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Mejia-Lavalle, Manuel, A. Jose Ruiz, O. Joaquin Perez, and S. Marilu Cervantes. "Modified Neural Net for the Boolean Satisfiability Problem." In 2015 International Conference on Mechatronics, Electronics and Automotive Engineering (ICMEAE). IEEE, 2015. http://dx.doi.org/10.1109/icmeae.2015.46.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Su, Juexiao, Tianheng Tu, and Lei He. "A quantum annealing approach for boolean satisfiability problem." In DAC '16: The 53rd Annual Design Automation Conference 2016. ACM, 2016. http://dx.doi.org/10.1145/2897937.2897973.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Pichugina, Oksana, and Olha Matsyi. "Boolean Satisfiability Problem: Discrete and Continuous Reformulations with Applications." In 2020 IEEE 15th International Conference on Advanced Trends in Radioelectronics, Telecommunications and Computer Engineering (TCSET). IEEE, 2020. http://dx.doi.org/10.1109/tcset49122.2020.235507.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Caleiro, Carlos, Filipe Casal, and Andreia Mordido. "Classical Generalized Probabilistic Satisfiability." In Twenty-Sixth International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, 2017. http://dx.doi.org/10.24963/ijcai.2017/126.

Full text

Abstract:

We analyze a classical generalized probabilistic satisfiability problem (GGenPSAT) which consists in deciding the satisfiability of Boolean combinations of linear inequalities involving probabilities of classical propositional formulas. GGenPSAT coincides precisely with the satisfiability problem of the probabilistic logic of Fagin et al. and was proved to be NP-complete. Here, we present a polynomial reduction of GGenPSAT to SMT over the quantifier-free theory of linear integer and real arithmetic. Capitalizing on this translation, we implement and test a solver for the GGenPSAT problem. As p

APA, Harvard, Vancouver, ISO, and other styles

6

Lin, Hai. "A Scalable Method for a Particular Scheduling Problem Based on Boolean Satisfiability." In 2015 International conference on Applied Science and Engineering Innovation. Atlantis Press, 2015. http://dx.doi.org/10.2991/asei-15.2015.209.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Hong, Huang, Latifur Khan, Ayoade Gbadebo, Zhou Shaohua, and Wei Yong. "A Complex Task Scheduling Scheme for Big Data Platforms Based on Boolean Satisfiability Problem." In 2018 IEEE International Conference on Information Reuse and Integration for Data Science (IRI). IEEE, 2018. http://dx.doi.org/10.1109/iri.2018.00033.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Niskanen, Andreas, Daniel Neugebauer, and Matti Järvisalo. "Controllability of Control Argumentation Frameworks." In Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}. International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/ijcai.2020/257.

Full text

Abstract:

Control argumentation frameworks (CAFs) allow for modeling uncertainties inherent in various argumentative settings. We establish a complete computational complexity map of the central computational problem of controllability in CAFs for five key semantics. We also develop Boolean satisfiability based counterexample-guided abstraction refinement algorithms and direct encodings of controllability as quantified Boolean formulas, and empirically evaluate their scalability on a range of NP-hard variants of controllability.

APA, Harvard, Vancouver, ISO, and other styles

9

Münzer, Clemens, Kristina Shea, and Bergen Helms. "Solving Design Tasks in Engineering Using Object-Oriented Graph-Based Representations and Boolean Satisfiability." In ASME 2013 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2013. http://dx.doi.org/10.1115/detc2013-12537.

Full text

Abstract:

Ever since computers have been used to support human designers, a variety of representations have been used to encapsulate engineering knowledge. Computational design synthesis approaches utilize this knowledge to generate design candidates for a specified task. However, new approaches are required to enable systematic solution space exploration. This paper presents an approach that combines a graph-based, object-oriented knowledge representation with first-order logic and Boolean satisfiability. This combination is used as the foundation for a generic, automated approach for requirement-drive

APA, Harvard, Vancouver, ISO, and other styles

10

Barak-Pelleg, Dina, and Daniel Berend. "On the Satisfiability Threshold of Random Community-Structured SAT." In Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/174.

Full text

Abstract:

For both historical and practical reasons, the Boolean satisfiability problem (SAT) has become one of central importance in computer science. One type of instances arises when the clauses are chosen uniformly randomly \textendash{} random SAT. Here, a major problem, recently solved for sufficiently large clause length, is the satisfiability threshold conjecture. The value of this threshold is known exactly only for clause length $2$, and there has been a lot of research concerning its value for arbitrary fixed clause length. In this paper, we endeavor to study the satisfiability threshold for

APA, Harvard, Vancouver, ISO, and other styles

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!