Log in

Relevant bibliographies by topics / QBF solver

Contents

Journal articles
Dissertations / Theses
Book chapters
Conference papers

Academic literature on the topic 'QBF solver'

Author: Grafiati

Published: 22 June 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 'QBF solver.'

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 "QBF solver"

1

Weihua, Su, Yin Minghao, Wang Jianan, and Zhou Junping. "Message Passing Algorithm for Solving QBF Using More Reasoning." Mathematical Problems in Engineering 2013 (2013): 1–6. http://dx.doi.org/10.1155/2013/165927.

Full text

Abstract:

We present a novel solver for solving Quantified Boolean Formulae problem (QBF). In order to improve the performance, we introduce some reasoning rules into the message passing algorithm for solving QBF. When preprocessing the formulae, the solver incorporates the equality reduction and the hyperbinary resolution. Further, the solver employs the message passing method to obtain more information when selecting branches. By using the unit propagation, conflict driven learning, and satisfiability directed implication and learning, the solver handles the branches. The experimental results also sho

APA, Harvard, Vancouver, ISO, and other styles

2

Lonsing, Florian, and Armin Biere. "DepQBF: A Dependency-Aware QBF Solver." Journal on Satisfiability, Boolean Modeling and Computation 7, no. 2-3 (2010): 71–76. http://dx.doi.org/10.3233/sat190077.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Chen, Pei-Wei, Yu-Ching Huang, and Jie-Hong R. Jiang. "A Sharp Leap from Quantified Boolean Formula to Stochastic Boolean Satisfiability Solving." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 5 (2021): 3697–706. http://dx.doi.org/10.1609/aaai.v35i5.16486.

Full text

Abstract:

Stochastic Boolean Satisfiability (SSAT) is a powerful representation for the concise encoding of quantified decision problems with uncertainty. While it shares commonalities with quantified Boolean formula (QBF) satisfiability and has the same PSPACE-complete complexity, SSAT solving tends to be more challenging as it involves expensive model counting, a.k.a. Sharp-SAT. To date, SSAT solvers, especially those imposing no restrictions on quantification levels, remain much lacking. In this paper, we present a new SSAT solver based on the framework of clause selection and cube distribution previ

APA, Harvard, Vancouver, ISO, and other styles

4

Goultiaeva, Alexandra, and Fahiem Bacchus. "Exploiting QBF Duality on a Circuit Representation." Proceedings of the AAAI Conference on Artificial Intelligence 24, no. 1 (2010): 71–76. http://dx.doi.org/10.1609/aaai.v24i1.7548.

Full text

Abstract:

Search based solvers for Quantified Boolean Formulas (QBF) have adapted the SAT solver techniques of unit propagation and clause learning to prune falsifying assignments. The technique of cube learning has been developed to help them prune satisfying assignments. Cubes, however, have not been able to achieve the same degree of effectiveness as clauses. In this paper we demonstrate how a circuit representation for QBF can support the propagation of dual truth values. The dual values support the identical techniques of unit propagation and clause learning, except now it is satisfying assignments

APA, Harvard, Vancouver, ISO, and other styles

5

Schuppan, Viktor. "Enhanced Unsatisfiable Cores for QBF: Weakening Universal to Existential Quantifiers." International Journal on Artificial Intelligence Tools 29, no. 03n04 (2020): 2060012. http://dx.doi.org/10.1142/s021821302060012x.

Full text

Abstract:

We introduce an enhanced notion of unsatisfiable cores for QBF in prenex CNF that allows to weaken universal quantifiers to existential quantifiers in addition to the traditional removal of clauses. The resulting unsatisfiable cores can be different from those of the traditional notion in terms of syntax, standard semantics, and proof-based semantics. This not only gives rise to explanations of unsatisfiability but, via duality, also leads to diagnoses and repairs of unsatisfiability that are not obtained with traditional unsatisfiable cores. We use a source-to-source transformation on QBF in

APA, Harvard, Vancouver, ISO, and other styles

6

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

7

Narizzano, Massimo, Luca Pulina, and Armando Tacchella. "Report of the Third QBF Solvers Evaluation1." Journal on Satisfiability, Boolean Modeling and Computation 2, no. 1-4 (2006): 145–64. http://dx.doi.org/10.3233/sat190019.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Tentrup, Leander. "CAQE and QuAbS: Abstraction Based QBF Solvers." Journal on Satisfiability, Boolean Modeling and Computation 11, no. 1 (2019): 155–210. http://dx.doi.org/10.3233/sat190121.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Lonsing, Florian, and Armin Biere. "Efficiently Representing Existential Dependency Sets for Expansion-based QBF Solvers." Electronic Notes in Theoretical Computer Science 251 (September 2009): 83–95. http://dx.doi.org/10.1016/j.entcs.2009.08.029.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Peitl, Tomáš, Friedrich Slivovsky, and Stefan Szeider. "Dependency Learning for QBF." Journal of Artificial Intelligence Research 65 (June 18, 2019): 181–208. http://dx.doi.org/10.1613/jair.1.11529.

Full text

Abstract:

Quantified Boolean Formulas (QBFs) can be used to succinctly encode problems from domains such as formal verification, planning, and synthesis. One of the main approaches to QBF solving is Quantified Conflict Driven Clause Learning (QCDCL). By default, QCDCL assigns variables in the order of their appearance in the quantifier prefix so as to account for dependencies among variables. Dependency schemes can be used to relax this restriction and exploit independence among variables in certain cases, but only at the cost of nontrivial interferences with the proof system underlying QCDCL. We introd

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic "QBF solver"

1

Fernandez, Davila Jorge Luis. "Planification cognitive basée sur la logique : de la théorie à l'implémentation." Electronic Thesis or Diss., Toulouse 3, 2022. http://thesesups.ups-tlse.fr/5491/.

Full text

Abstract:

Dans cette thèse, nous définissons un cadre de planification cognitive permettant de doter des agents artificiels des compétences nécessaires pour représenter et raisonner sur les états mentaux d'autres agents. Notre cadre de planification cognitive est basé sur un fragment NP d'une logique épistémique avec une sémantique exploitant des bases de croyances et dont le problème de satisfiabilité peut être réduit à SAT. Nous détaillons l'ensemble des traductions pour la réduction de notre fragment à SAT. De plus, nous fournissons des résultats de complexité pour vérifier la satisfiabilité des form

APA, Harvard, Vancouver, ISO, and other styles

2

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

Book chapters on the topic "QBF solver"

1

Giunchiglia, Enrico, Massimo Narizzano, and Armando Tacchella. "QuBE++: An Efficient QBF Solver." In Formal Methods in Computer-Aided Design. Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-30494-4_15.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Olivo, Oswaldo, and E. Allen Emerson. "A More Efficient BDD-Based QBF Solver." In Principles and Practice of Constraint Programming – CP 2011. Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-23786-7_51.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Goultiaeva, Alexandra, Vicki Iverson, and Fahiem Bacchus. "Beyond CNF: A Circuit-Based QBF Solver." In Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-02777-2_38.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Bryant, Randal E., and Marijn J. H. Heule. "Dual Proof Generation for Quantified Boolean Formulas with a BDD-based Solver." In Automated Deduction – CADE 28. Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-79876-5_25.

Full text

Abstract:

AbstractExisting proof-generating quantified Boolean formula (QBF) solvers must construct a different type of proof depending on whether the formula is false (refutation) or true (satisfaction). We show that a QBF solver based on ordered binary decision diagrams (BDDs) can emit a single dual proof as it operates, supporting either outcome. This form consists of a sequence of equivalence-preserving clause addition and deletion steps in an extended resolution framework. For a false formula, the proof terminates with the empty clause, indicating conflict. For a true one, it terminates with all clauses deleted, indicating tautology. Both the length of the proof and the time required to check it are proportional to the total number of BDD operations performed. We evaluate our solver using a scalable benchmark based on a two-player tiling game.

APA, Harvard, Vancouver, ISO, and other styles

5

Balyo, Tomáš, and Florian Lonsing. "HordeQBF: A Modular and Massively Parallel QBF Solver." In Theory and Applications of Satisfiability Testing – SAT 2016. Springer International Publishing, 2016. http://dx.doi.org/10.1007/978-3-319-40970-2_33.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Heyman, Tamir, Dan Smith, Yogesh Mahajan, Lance Leong, and Husam Abu-Haimed. "Dominant Controllability Check Using QBF-Solver and Netlist Optimizer." In Lecture Notes in Computer Science. Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-09284-3_18.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Lonsing, Florian, and Uwe Egly. "DepQBF 6.0: A Search-Based QBF Solver Beyond Traditional QCDCL." In Automated Deduction – CADE 26. Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-63046-5_23.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Klieber, William, Samir Sapra, Sicun Gao, and Edmund Clarke. "A Non-prenex, Non-clausal QBF Solver with Game-State Learning." In Theory and Applications of Satisfiability Testing – SAT 2010. Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-14186-7_12.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Heisinger, Maximilian, Martina Seidl, and Armin Biere. "ParaQooba: A Fast and Flexible Framework for Parallel and Distributed QBF Solving." In Tools and Algorithms for the Construction and Analysis of Systems. Springer Nature Switzerland, 2023. http://dx.doi.org/10.1007/978-3-031-30823-9_22.

Full text

Abstract:

AbstractOver the last years, innovative parallel and distributed SAT solving techniques were presented that could impressively exploit the power of modern hardware and cloud systems. Two approaches were particularly successful: (1) search-space splitting in a Divide-and-Conquer (D &C) manner and (2) portfolio-based solving. The latter executes different solvers or configurations of solvers in parallel. For quantified Boolean formulas (QBFs), the extension of propositional logic with quantifiers, there is surprisingly little recent work in this direction compared to SAT.In this paper, we present ParaQooba, a novel framework for parallel and distributed QBF solving which combines D &C parallelization and distribution with portfolio-based solving. Our framework is designed in such a way that it can be easily extended and arbitrary sequential QBF solvers can be integrated out of the box, without any programming effort. We show how ParaQooba orchestrates the collaboration of different solvers for joint problem solving by performing an extensive evaluation on benchmarks from QBFEval’22, the most recent QBF competition.

APA, Harvard, Vancouver, ISO, and other styles

10

Lonsing, Florian, and Uwe Egly. "Evaluating QBF Solvers: Quantifier Alternations Matter." In Lecture Notes in Computer Science. Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-98334-9_19.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "QBF solver"

1

Rabe, Markus N., and Leander Tentrup. "CAQE: A Certifying QBF Solver." In 2015 Formal Methods in Computer-Aided Design (FMCAD). IEEE, 2015. http://dx.doi.org/10.1109/fmcad.2015.7542263.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Pigorsch, Florian, and Christoph Scholl. "Exploiting structure in an AIG based QBF solver." In 2009 Design, Automation & Test in Europe Conference & Exhibition (DATE'09). IEEE, 2009. http://dx.doi.org/10.1109/date.2009.5090919.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Santos, Rafael, Joao Afonso, and Jose Monteiro. "Short-circuit Analysis using a Parallel QBF Solver." In 2020 XXXV Conference on Design of Circuits and Integrated Systems (DCIS). IEEE, 2020. http://dx.doi.org/10.1109/dcis51330.2020.9268636.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Pigorsch, Florian, and Christoph Scholl. "An AIG-Based QBF-solver using SAT for preprocessing." In the 47th Design Automation Conference. ACM Press, 2010. http://dx.doi.org/10.1145/1837274.1837318.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Yu, Yinlei, and Sharad Malik. "Validating the result of a Quantified Boolean Formula (QBF) solver." In the 2005 conference. ACM Press, 2005. http://dx.doi.org/10.1145/1120725.1120821.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Marin, Paolo, Massimo Narizzano, Enrico Giunchiglia, Matthew Lewis, Tobias Schubert, and Bernd Becker. "Comparison of knowledge sharing strategies in a parallel QBF solver." In Simulation (HPCS). IEEE, 2009. http://dx.doi.org/10.1109/hpcsim.2009.5195312.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Lagniez, Jean-Marie, Daniel Le Berre, Tiago de Lima, and Valentin Montmirail. "A Recursive Shortcut for CEGAR: Application To The Modal Logic K Satisfiability Problem." 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/94.

Full text

Abstract:

Counter-Example-Guided Abstraction Refinement (CEGAR) has been very successful in model checking large systems. Since then, it has been applied to many different problems. It especially proved to be an highly successful practical approach for solving the PSPACE complete QBF problem. In this paper, we propose a new CEGAR-like approach for tackling PSPACE complete problems that we call RECAR (Recursive Explore and Check Abstraction Refinement). We show that this generic approach is sound and complete. Then we propose a specific implementation of the RECAR approach to solve the modal logic K sati

APA, Harvard, Vancouver, ISO, and other styles

8

Böhm, Benjamin, Tomáš Peitl, and Olaf Beyersdorff. "QCDCL with Cube Learning or Pure Literal Elimination - What is Best?" In Thirty-First International Joint Conference on Artificial Intelligence {IJCAI-22}. International Joint Conferences on Artificial Intelligence Organization, 2022. http://dx.doi.org/10.24963/ijcai.2022/248.

Full text

Abstract:

Quantified conflict-driven clause learning (QCDCL) is one of the main approaches for solving quantified Boolean formulas (QBF). We formalise and investigate several versions of QCDCL that include cube learning and/or pure-literal elimination, and formally compare the resulting solving models via proof complexity techniques. Our results show that almost all of the QCDCL models are exponentially incomparable with respect to proof size (and hence solver running time), pointing towards different orthogonal ways how to practically implement QCDCL.

APA, Harvard, Vancouver, ISO, and other styles

9

Lee, Nian-Ze, Yen-Shi Wang, and Jie-Hong R. Jiang. "Solving Exist-Random Quantified Stochastic Boolean Satisfiability via Clause Selection." 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/186.

Full text

Abstract:

Stochastic Boolean satisfiability (SSAT) is an expressive language to formulate decision problems with randomness. Solving SSAT formulas has the same PSPACE-complete computational complexity as solving quantified Boolean formulas (QBFs). Despite its broad applications and profound theoretical values, SSAT has received relatively little attention compared to QBF. In this paper, we focus on exist-random quantified SSAT formulas, also known as E-MAJSAT, which is a special fragment of SSAT commonly applied in probabilistic conformant planning, posteriori hypothesis, and maximum expected utility. B

APA, Harvard, Vancouver, ISO, and other styles

10

Fernandez, Jorge, Olivier Gasquet, Andreas Herzig, et al. "TouIST: a Friendly Language for Propositional Logic and More." 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/756.

Full text

Abstract:

This work deals with logical formalization and problem solving using automated solvers. We present the automatic translator TouIST that provides a simple language to generate logical formulas from a problem description. Our tool allows us to model many static or dynamic combinatorial problems and to benefit from the regular improvements of SAT, QBF or SMT solvers in order to solve these problems efficiently. In particular, we show how to use TouIST to solve different classes of planning tasks in Artificial Intelligence.

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!