Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 21 for “"QBF"”.
-
QBF Proof Complexity
Quantified Boolean Formulas (QBF) and their proof complexity are not as well understood as propositional formulas, yet remain an area of interest due to their relation to QBF solving. Proof systems for QBF provide a theoretical underpinning for the performance of these solvers. We define a novel …
-
Exploiting Problem Structure in QBF Solving
… 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 …
-
Reasons for Hardness in QBF Proof Complexity
Quantified Boolean Formulas (QBF) extend the canonical NP-complete satisfiability problem by including Boolean quantifiers. Determining the truth of a QBF is PSPACE-complete; this is expected to be a harder problem than satisfiability, and hence QBF solving has much wider applications in practice. …
-
Jeux combinatoires et formules booléennes quantifiées (QBF) : encodages pour le jeu de Tic-Tac-Toe d'Harary
… joueur. Les formules booléennes quantifiées (QBF), où l’alternance de quantificateurs universels et existentiels est de nature interactive, possèdent une sémantique naturelle en termes de jeux, ce qui en fait une représentation totalement adéquate et prometteuse pour la détermination de …
-
Quantified Boolean Formulas: Proof Complexity and Models of Solving
Quantified Boolean formulas (QBF), which form the canonical PSPACE-complete decision problem, are a decidable fragment of first-order logic. Any problem that can be solved within a polynomial-size space can be encoded succinctly as a QBF, including many concrete problems in computer science from …
-
Proof Complexity for Quantified Boolean Formulas
Quantified Boolean formulas (QBF) extend the propositional satisfiability problem by allowing variables to be universally as well as existentially quantified. Deciding whether a QBF is true or false is PSPACE-complete and a wide range of mathematical and industrial problems can be expressed as …
-
Complexity and structural heuristics for propositional and quantified satisfiability
… there are also recent interests in using QBF, an extension of propositional logic, as a modeling language to be used in a similar fashion. The hope is that QBF, being a more powerful language, can compactly encode, and in turn, be used to solve, a larger range of applications. Still, …
-
Predicting Low Probability Streamflow Using Lidar Data and Hydraulic Geometry
… of shear stress to estimate bankfull discharge (Qbf). Assuming that Qbf is the median of the annual peak flow distribution, a 2-parameter Extreme Value Type I distribution was fitted to predict discharge to a 200-year return period. The method was compared with gauged sites in low-order streams …
-
Formal Methods in Computer-aided Design
… (SAT) and quantified Boolean formulas (QBFs), and focus academic resources on improving SAT and QBF solvers. The significant progress of these solvers has validated this strategy. This dissertation contributes to the further advancement of formal techniques in CAD. Today, the …
-
Planning as Quantified Boolean Formulae
… Planning as Quantified Boolean Formulae (QBF) has been relegated to conformant Planning approaches, with the exception of one encoding that has not yet been investigated in detail. QBF is a promising setting for Planning given that the problems have the same complexity. This work …
-
Solving Quantified Boolean Formulas
… context of solving quantified boolean formulas (QBF). QBF enables complex realworld problems including planning, two-player games and verification to be captured in a compact and quite natural fashion. We will discuss techniques ranging from straight forward pre-processing methods utilizing …
-
On the magnitude and frequency of sediment transport in rivers
… effort to predicting the bankfull discharge, Qbf, and associated channel geometry at Qbf for the purposes of channel study, classification, and design. In a study comparing various Qbf predictors in coarse and fine bed rivers, I find that the discharge associated with 50% of cumulative …
-
Parameterized complexity in graph theory, logic and machine learning
… the PSpace-complete Quantified Boolean Formula (QBF) problem. Moving beyond standard graph parameters, this work utilises ``backdoors'', which are sets of variables whose removal yields tractable classes like Quantified 2-CNF. By introducing ``Enhanced Backdoors'', the research bridges the gap …
-
Full spectrum analytical channel design with the capacity/supply ratio (CSR)
… interval discharge (Q1.5), bankfull discharge (Qbf), and the discharges associated with 50th (Qs50) and 75th (Qs75) percentiles of the cumulative sediment yield curve. The Qs50 and Qs75 single-discharge designs match the CSR output most closely followed by the Qbf and Qeff. The Qeff proved to be …
-
On the relationship between satisfiability and partially observable Markov decision processes
… (SSAT), Quantified Boolean Satisfiability (QBF) and decision-theoretic planning in finite horizon partially observable Markov decision processes (POMDPs) are all PSPACE-Complete problems. Since they are all complete for the same complexity class, I show how to convert them into one another …
-
BDD-based decision procedures for modal logic K
… as developing an algorithm to translate K to QBF based on our decision procedure. Experimental results show that the BDD-based approach dominates for modally heavy formulas, while search-based approaches dominate for propositionally-heavy formulas.
-
Efektivní redukce konečných automatů
… redukovať konečný stavový automat pomocou SAT a QBF solverov. Vytvorili sme množinu pravidiel pre každý solver pre tvorbu klauzule v konjunktnej normálnej forme, ktorá dokáže jednoznačne reprezentovať automat v Booleovej algebre. S využitím tohto faktu sme vytvorili nový spôsob redukcie …
-
A Formal Approach to Concurrent Error Detection in FPGA LUTs
… normal form. A quantified boolean formula (QBF) based approach to designing CED logic based on parity check codes is found to be infeasible for designs of a realistic size. It is shown that a satisfiability (SAT) solver can be used to find variable assignments that indicate which circuit …
-
Applying CDCL to verification and test: when laziness pays off
… abbildet. Verglichen zu existierenden akkuraten QBF-basierten Ansätzen ist CDCL+CEGAR deutlich schneller. Zum Zweiten werden Erweiterungen vorgestellt, die es erlauben iSAT3 im Bereich der Softwareverifikation einzusetzen. Insbesondere wenn es um das Erkennen von unerreichbarem Code in C …
-
Algorithm capability and applications in artificial intelligence
… and for solving Quantified Boolean Formula (QBF). The most well known algorithm for solving SAT is called DPLL. It has been well studied and is continuously being optimized in an effort to develop faster SAT solvers. The amount of work being done on optimizing DPLL makes it a good candidate …
Page 1 of 2