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

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

    toronto-retro Repository record for Solving Quantified Boolean Formulas (opens in a new tab)

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

    whiterose Download PDF for Proof Complexity for Quantified Boolean Formulas (opens in a new tab)

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

    whiterose Download PDF for Quantified Boolean Formulas: Proof Complexity and Models of Solving (opens in a new tab)

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

    ucf Repository record for Automated Synthesis of Memristor Crossbar Networks (opens in a new tab)

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

    texas Repository record for Program analysis with boolean logic solvers (opens in a new tab)

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

    rit Repository record for Constraint Satisfaction Techniques for Combinatorial Problems (opens in a new tab)

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

    rice Repository record for Weighted Model Counting with Algebraic Decision Diagrams (opens in a new tab)

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

    nus Repository record for ON SCALABILITY OF KNOWLEDGE COMPILATION APPLICATIONS (opens in a new tab) Download file for ON SCALABILITY OF KNOWLEDGE COMPILATION APPLICATIONS (opens in a new tab)

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

    aalto Repository record for Online algorithms in resource management and constraint satisfaction (opens in a new tab)

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

    concordia Download PDF for Embedded supervisory control of discrete-event systems (opens in a new tab)

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

    birmingham Download PDF for Proof complexity of systems of branching programs (opens in a new tab)

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

    ubc Repository record for Combining SMT with theorem proving for AMS verification : analytically verifying global convergence of a digital PLL (opens in a new tab) Download PDF for Combining SMT with theorem proving for AMS verification : analytically verifying global convergence of a digital PLL (opens in a new tab)

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

    uiuc Repository record for Thresholds and Symmetries in Propositional Formulas (opens in a new tab)

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

    texas Repository record for Attribute-based encryption : robust and efficient constructions (opens in a new tab)

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

    whiterose Download PDF for QBF Proof Complexity (opens in a new tab)

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

    whiterose Download PDF for Reasons for Hardness in QBF Proof Complexity (opens in a new tab)

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

    oregon Repository record for Searchable Encryption: Building Practical and Secure Cloud Data Systems (opens in a new tab)

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

    waterloo Repository record for Reconfiguring Triangulations (opens in a new tab)

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

    toronto-retro Repository record for Formal Methods in Computer-aided Design (opens in a new tab)

Page 1 of 2