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 27 for “"Boolean formulas"”.
-
Solving Quantified Boolean Formulas
Abstract Solving Quantified Boolean Formulas Horst Samulowitz Doctor of Philosophy Graduate Department of Computer Science University of Toronto 2008 Many real-world problems do not have a simple algorithmic solution and casting these problems as search problems is often not only the simplest way …
-
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 …
-
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 …
-
On the descriptive complexity of satisfiability on quantified Boolean formulas : a thesis presented in partial fulfilment of the requirements for the degree of Master of Information Sciences at Massey University, Wellington, New Zealand
… we deal with the construction of non trivial formulas in higher order logic languages. In particular, we focus on using SO (Second-Order logic) and TO (Third-Order logic) to express SATQBFk, and SATQBF respectively. First of all, we explain the relationship between logic languages and …
-
Automated Synthesis of Memristor Crossbar Networks
… can we synthesize crossbars for computing large Boolean formulas, up to 128-bit? b. How can we synthesize more compact crossbars for small Boolean formulas, up to 8-bit? c. For a given loop-free C program doing integer arithmetic, is it possible to synthesize an equivalent crossbar circuit? We …
-
Program analysis with boolean logic solvers
… techniques that are based on satisfiability of Boolean formulas in conjunctive normal form validate designs by forcing bounds on the range of variables of a design. Their primary drawback is that they are limited to designs of relatively low complexity. They translate a design expressed in an …
-
Constraint Satisfaction Techniques for Combinatorial Problems
… satisfaction paradigms like satisfiability of Boolean formulas and answer set programming, and techniques like symmetry breaking. Our contributions range from theoretical results to practical issues regarding tool applications to combinatorial problems. We prove search-versus-decision …
-
Weighted Model Counting with Algebraic Decision Diagrams
… compute exact literal-weighted model counts of Boolean formulas in conjunctive normal form. Our algorithm employs dynamic programming and uses algebraic decision diagrams as the primary data structure. We implement this technique in ADDMC, a new model counter. We empirically evaluate various …
-
ON SCALABILITY OF KNOWLEDGE COMPILATION APPLICATIONS
… compilation to work with more succinct logical formulas, and using the compiled representations in a more efficient manner. In particular, this thesis covers applications that employ knowledge compilation techniques to perform incremental constrained sampling for path planning and combinatorial …
-
Online algorithms in resource management and constraint satisfaction
… with delay and holding costs, and games on Boolean formulas. The algorithms presented for the problems yield the currently best known competitive ratios. Essentially matching lower bounds for the best possible competitive ratios are proved in the lot-sizing and checkpointing models.
-
Embedded supervisory control of discrete-event systems
… is introduced by extending the plant with boolean variables, guard formulas and updating functions. Boolean variables are used to encode the supervisor's states. Event observation is captured by a set of boolean functions that update the values of boolean variables, and control is …
-
Proof complexity of systems of branching programs
… is also a 1-transition. PBPs compute mono-tone Boolean functions, much like negation-free circuits or formulas do, but constitute a positive version of (non- uniform) NL, rather than P or NC1, respectively. We introduce eLNDT`, the positive fragment of eLNDT, that reasons about PBPs by …
-
Combining SMT with theorem proving for AMS verification : analytically verifying global convergence of a digital PLL
… – Z3 provides fully automated reasoning about boolean formulas, linear and non-linear systems of equalities, and simple data structures such as arrays. ACL2 provides a very flexible framework for induction along with proof structuring facilities to combine simpler results into larger theorems. …
-
Thresholds and Symmetries in Propositional Formulas
… concerning the satisfiability of propositional formulas are investigated. With respect to the first problem, there is great experimental evidence for a phenomenon known as the 'phase transition' of satisfiability, that is there is a sharp threshold, in the limit, between satisfiable and …
-
Attribute-based encryption : robust and efficient constructions
… restrictions on the expressiveness of the Boolean formulas used during encryption. For several proposed schemes the total number of attributes was fixed during setup, while others allowed any string to be used as attribute ("large universe" constructions), but with considerable weaker …
-
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 …
-
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. …
-
Searchable Encryption: Building Practical and Secure Cloud Data Systems
… to enable expressive searches over monotone Boolean formulas while remaining resilient against offline keyword guessing attacks. Finally, we bridge the gap between cryptographic design and real-world deployment with M-EDESE, the first multi-domain searchable encryption system designed for …
-
Reconfiguring Triangulations
… graph of satisfying assignments of Boolean formulas where there is a node for each satisfying assignment of a formula and an edge whenever one assignment can be changed to another by changing the value of exactly one variable from 0 to 1 or from 1 to 0. We show that computing the …
-
Formal Methods in Computer-aided Design
… been to encode them in formal languages, such as Boolean satisfiability (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 …
Page 1 of 2