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 20 for “"disjunctive normal form"”.
-
On the Learnability of Disjunctive Normal Form Formulas and Decision Trees
The learnability of disjunctive normal form formulas and decision trees is investigated. Polynomial time algorithms are given, and nonlearnability results are obtained, for restricted versions of these general learning problems.
-
A tabular propositional logic: and/or Table Translator
… to help users translate any logic statement into Disjunctive Normal Form and present the result as an AND/OR TABLE, which makes the logic relation easier to express by using a two-dimensional grid of values or expressions. This tool is implemented through a web-based and Java-based application. …
-
A tabular propositional logic: and/or Table Translator
… to help users translate any logic statement into Disjunctive Normal Form and present the result as an AND/OR TABLE, which makes the logic relation easier to express by using a two-dimensional grid of values or expressions. This tool is implemented through a web-based and Java-based application. …
-
Algorithmic models in quantum mechanics
… of quantum states and assess its performance on states with varying levels of complexity. Third, we discuss the time complexity of classical and quantum learning algorithms and prove that Boolean functions in disjunctive normal form are efficiently quantum PAC learnable under product …
-
Classifier system learning of the Boolean multiplexer function
… is a special case of a concept expressable in a disjunctive normal form, the k + 2<sup><i>k</i></sup> multiplexer is expressable as a k + 1 disjunctive normal formula. A variety of modifications to the classifier system are investigated to induce rapid learning. Some of the methods tried axe …
-
Algorithm for Learning from a Random Walk Oracle
Learning Disjunctive Normal Form and Threshold of Parity functions are well-studied problems in computational learning theory. Under different learning models we can achieve different time complexities with respect to the size of the input. In this thesis, I consider using an oracle whose power …
-
Fuzzy Cellular Automata in Conjunctive Normal Form
… To date, FCA have only been studied in disjunctive normal form (DNF). In this thesis, we study FCA in conjunctive normal form (CNF). We classify FCA in CNF both analytically and empirically. We compare these classes to their DNF counterparts. We prove that certain FCA exhibit chaos in …
-
Efficiently Learning Monotone Decision Trees with ID3
… functions from random examples drawn from a uniform distribution. In this paper, I take the ID3 information-gain-first classification algorithm and apply it to the task of learning monotone Boolean functions from examples that are uniformly distributed over {0,1}^n. I limited my scope to the …
-
The shortest disjunctive normal forms of Boolean functions by reducing the number of arguments
Denoting the length of a shortest disjunctive normal form of a Boolean function / by l(f), this thesis provides a way to express l(f) in terms of l(g) for some Boolean function g with no more arguments than f and with the same number of zeros as f . This method is useful for finding the shortest …
-
A heuristic approach to network hardening using attack graphs
… initially satisfied security conditions. In the disjunctive normal form (DNF) of the logic proposition, each disjunction then provides a viable solution to network hardening. However, such solutions suffer from an exponential time complexity. In this thesis, we study heuristic methods for solving …
-
Functional Encryption as Mediated Obfuscation
… feasibility result for obfuscating conjunctive normal form and disjunctive normal form formulae (under a weaker “semantic” notion of security). Finally, we use mediated obfuscation to illustrate a connection between worst-case and average-case static obfuscation. In short, an average-case …
-
Functional Encryption as Mediated Obfuscation
… feasibility result for obfuscating conjunctive normal form and disjunctive normal form formulae (under a weaker “semantic” notion of security). Finally, we use mediated obfuscation to illustrate a connection between worst-case and average-case static obfuscation. In short, an average-case …
-
Properties and Behaviours of Fuzzy Cellular Automata
… created from the extension of Boolean rules in disjunctive normal form to continuous functions. Motivated by recent results on the classification of these rules from empirical evidence, we set out first to show that fuzzy cellular automata can shed some light on classical cellular automata and …
-
Constrained Counting and Sampling: Bridging the Gap Between Theory and Practice
… or approaches with proven guarantees but poor performance in practice. In this thesis, we introduce a novel hashing-based algorithmic framework for constrained sampling and counting that combines the classical algorithmic technique of universal hashing with the dramatic progress made in Boolean …
-
Conformance preserving data dissemination for large-scale peer to peer systems
… a new pattern of data dissemination based on conformance constraints where data accuracy can be traded for low bandwidth. We formally define the problem of conformance preserving data dissemination and address two types of conformance data dissemination problems that we are interested in: data …
-
Feature Model Synthesis
… extracting a feature graph from a propositional formula in either conjunctive normal form (CNF), or disjunctive normal form (DNF). A feature graph describes all feature diagrams that are complete with respect to the input. We evaluated our algorithms against related synthesis algorithms and found …
-
Bridging semantic gap: learning and integrating semantics for content-based retrieval
… the semantic gap between computable low-level information and high-level user interpretation. In this thesis, we address the issue of semantic gap with a structured learning framework to allow modular extraction of visual semantics. Semantic image regions (e.g. face, building, sky etc) are …
-
General Boolean expressions in publish-subscribe systems
… increasing amount of electronically available information in society today is undeniable. Examples include the numbers of general web pages, scientific publications, and items in online auctions. From a user's perspective, this trend will lead to information overflow. Moreover, information …
-
Generalisation and optimisation in neural networks
… optimisers in a principled manner to maximise performance? <br><br>In the first part, we introduce a discrete fully-connected network (DFCN) model that offers useful insights for both questions. We prove a one-to-one correspondence between DFCN architectures and Disjunctive Normal Form (DNF) …
-
Towards Optimal Tree Construction of Monotone Functions
This thesis focuses on finding counterexamples for the conjecture suggested by Dr. Jackson that if two Boolean variables i and j in a monotone Boolean function have the relation such that if i is relevant in only one sub-tree with j as root while j is relevant in both sub-trees with i as root, then …