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 show that the solver can solve QBF problem efficiently.

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 previously proposed for QBF solving. With model counting integrated and learning techniques strengthened, our solver is general and effective. Experimental results demonstrate the overall superiority of the proposed algorithm in both solving performance and memory usage compared to the state-of-the-art solvers on a number of benchmark formulas.

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 rather than falsifying assignments that are pruned. Dual value propagation thus exploits the circuit representation and the duality of QBF formulas so that the same effective SAT techniques can now be used to prune both falsifying and satisfyingly assignments. We show empirically that dual propagation yields significantperformance improvements and advances the state of the art in QBF solving.

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 PCNF such that the weakening of universal quantifiers to existential quantifiers in the original formula corresponds to the removal of clauses in the transformed formula. This makes any tool or method for the computation of unsatisfiable cores of the traditional notion available for the computation of unsatisfiable cores of our enhanced notion. We implement our approach as an extension to the QBF solver DepQBF, and we perform an extensive experimental evaluation on a subset of QBFLIB. We illustrate with several case studies that helpful information can be provided by unsatisfiable cores of our enhanced notion.

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 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.

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 introduce dependency learning, a new technique for exploiting variable independence within QCDCL that allows solvers to learn variable dependencies on the fly. The resulting version of QCDCL enjoys improved propagation and increased flexibility in choosing variables for branching while retaining ordinary (long-distance) Q-resolution as its underlying proof system. We show that dependency learning can achieve exponential speedups over ordinary QCDCL. Experiments on standard benchmark sets demonstrate the effectiveness of this technique.

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 formules dans notre fragment NP. Nous définissons une architecture générale pour le problème de planification cognitive. Ensuite, nous définissons deux types de problème de planification : informatif et interrogatif, et nous calculons la complexité pour trouver une solution au problème de planification cognitive dans chacun de ces deux cas. De plus, nous illustrons le potentiel de notre cadre pour les applications en interaction humain-machine à l'aide de deux exemples dans lesquels un agent artificiel est censé interagir avec un agent humain par le dialogue et persuader l'humain de se comporter d'une certaine manière. Enfin, nous introduisons une formalisation de la planification cognitive simple en tant que formule booléenne quantifiée (QBF) avec un nombre optimal de quantificateurs dans le préfixe. Le modèle de planification cognitive a été mis implémenté. Nous décrivons comment représenter et générer la base de croyance. De plus, nous démontrons comment la machine exécute le processus de raisonnement pour trouver une séquence d'actes de langage destinés à induire une intention potentielle chez l'agent humain. L'implémentation comporte trois composants principaux : la révision des croyances, la planification cognitive et le module de traduction. Ces modules fonctionnent de manière intégrée pour capturer les croyances de l'agent humain au cours du processus d'interaction humain-machine et générer une séquence d'actes de parole pour atteindre un objectif persuasif. Finalement, nous présentons un langage épistémique pour représenter les croyances et les actions d'un joueur artificiel dans le contexte du jeu de société coopératif Yokai. Ce jeu nécessite une combinaison de théorie de l'esprit (ToM), de raisonnement temporel et de raisonnement spatial pour qu'un agent artificiel joue efficacement. Nous montrons que le langage rend bien compte de ces trois dimensions et que son problème de satisfiabilité est NP-complet. Nous implémentons le jeu et réalisons des expériences pour comparer le niveau de coopération entre les agents lorsqu'ils tentent d'atteindre un objectif commun en analysant deux scénarios : lorsque le jeu se joue entre un humain et l'agent artificiel versus lorsque deux humains jouent ensemble<br>In this thesis, we introduced a cognitive planning framework that can be used to endow artificial agents with the necessary skills to represent and reason about other agents' mental states. Our cognitive planning framework is based on an NP-fragment of an epistemic logic with a semantics exploiting belief bases and whose satisfiability problem can be reduced to SAT. We detail the set of translations for the reduction of our fragment to SAT. In addition, we provide complexity results for checking satisfiability of formulas in our NP-fragment. We define a general architecture for the cognitive planning problem. Afterward, we define two types of planning problem: informative and interrogative, and we find the complexity of finding a solution for the cognitive planning problem in both cases. Furthermore, we illustrated the potential of our framework for applications in human-machine interaction with the help of two examples in which an artificial agent is expected to interact with a human agent through dialogue and to persuade the human to behave in a certain way. Moreover, we introduced a formalization of simple cognitive planning as a quantified boolean formula (QBF) with an optimal number of quantifiers in the prefix. The model for cognitive planning was implemented. We describe how to represent and generate the belief base. Furthermore, we demonstrate how the machine performs the reasoning process to find a sequence of speech acts intended to induce a potential intention in the human agent. The implemented system has three main components: belief revision, cognitive planning, and the translator module. These modules work integrated to capture the human agent's beliefs during the human-machine interaction process and generate a sequence of speech acts to achieve a persuasive goal. Finally, we present an epistemic language to represent the beliefs and actions of an artificial player in the context of the board game Yokai. The cooperative game Yokai requires a combination of theory of mind (ToM), temporal and spatial reasoning for an artificial agent to play effectively. We show that the language properly accounts for these three dimensions and that its satisfiability problem is NP-complete. We implement the game and perform experiments to compare the cooperation level between agents when they try to achieve a common goal by analyzing two scenarios: when the game is played between a human and the artificial agent versus when two humans play the game

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 efficiently due to the structural simplicity of CNF. However, the translation to CNF involves a loss of some structural information. This thesis shows that this structural information is important for efficient QBF solving, and shows how this structural information can be utilized to improve state-of-the-art QBF solving. First, a non-CNF circuit-based solver is presented. It makes use of information not present in CNF to improve its performance. We present techniques that allow it to exploit the duality between solutions and conflicts that is lost when working with CNF. This duality can also be utilized in the production of certificates, allowing both true and false formulas to have easy-to-verify certificates of the same form. Then, it is shown that most modern CNF-based solvers can benefit from the additional information derived from duality using only minor modifications. Furthermore, even partial duality information can be helpful. We show that for standard methods for conversion to CNF, some of the required information can be reconstructed from the CNF and greatly benefit the solver.

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 satisfiability problem. We implemented both a CEGAR and a RECAR approach for the modal logic K satisfiability problem within the solver MoSaiC. We compared experimentally those approaches to the state-of-the-art solvers for that problem. The RECAR approach outperforms the CEGAR one for that problem and also compares favorably against the state-of-the-art on the benchmarks considered.

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. Based on clause selection, a recently proposed QBF technique, we propose an algorithm to solve E-MAJSAT. Moreover, our method can provide an approximate solution to E-MAJSAT with a lower bound when an exact answer is too expensive to compute. Experiments show that the proposed algorithm achieves significant performance gains and memory savings over the state-of-the-art SSAT solvers on a number of benchmark formulas, and provides useful lower bounds for cases where prior methods fail to compute exact answers.

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!