Vectors and matrices over the Boolean (0,1) semiring have been studied extensively along with their applications to graph theory. The Boolean (0,1) semiring has been generalized to a class of semirings called chain semirings. This class includes the fuzzy interval. Vectors and matrices over chain semirings are examined. Rank-1 sets of vectors are defined and characterized. These rank-1 sets of vectors are then used to construct spaces of matrices (rank-1 spaces) with the property that all nonzero matrices in the space have semiring rank equal to 1. Finally, three classes of maximal (relative to containment) rank-1 spaces are identified.

The 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 publishers are compromised by this situation, as users have greater difficulty in identifying useful information. Publish-subscribe systems can be applied to cope with the reality of information overflow. In these systems, users specify their information interests as subscriptions and, subsequently, only matching information (event messages) is delivered; uninteresting information is filtered out before reaching users. In this dissertation, we consider content-based publish-subscribe systems, a sophisticated example of these systems. They perform the information-filtering task based on the content of provided information. In order to deal with high numbers of subscriptions and frequencies of event messages, publish-subscribe systems are realized as distributed systems. Advertisements---publisher specifications of potential future event messages---are optionally applied in these systems to reduce the internal distribution of subscriptions. Existing work on content-based publish-subscribe concepts mainly focuses on subscriptions and advertisements as pure conjunctive expressions. Therefore, subscriptions or advertisements using operators other than conjunction need to be canonically converted to disjunctive normal form by these systems. Each conjunctive component is then treated as individual subscription or advertisement. Unfortunately, the size of converted expressions is exponential in the worst case. In this dissertation, we show that the direct support of general Boolean subscriptions and advertisements improves the time and space efficiency of general-purpose content-based publish-subscribe systems. For this purpose, we develop suitable approaches for the filtering and routing of general Boolean expressions in these systems. Our approaches represent solutions to exactly those components of content-based publish-subscribe systems that currently restrict subscriptions and advertisements to conjunctive expressions. On the subscription side, we present an effective generic filtering algorithm, and a novel approach to optimize event routing tables, which we call subscription pruning. To support advertisements, we show how to calculate the overlap between subscriptions and advertisements, and introduce the first designated subscription routing optimization, which we refer to as advertisement pruning. We integrate these approaches into our prototype BoP (BOolean Publish-subscribe) which allows for the full support of general Boolean expressions in its filtering and routing components. In the evaluation part of this dissertation, we empirically analyze our prototypical implementation BoP and compare its algorithms to existing conjunctive solutions. We firstly show that our general-purpose Boolean filtering algorithm is more space- and time-efficient than a general-purpose conjunctive filtering algorithm. Secondly, we illustrate the effectiveness of the subscription pruning routing optimization and compare it to the existing covering optimization approach. Finally, we demonstrate the optimization effect of advertisement pruning while maintaining the existing overlapping relationships in the system.

This thesis presents an interactive computerised teaching suite developed for the design of combinatorial and sequential logic circuits. This suite fills a perceived gap in the currently available computer-based teaching software for digital logic design. Several existing digital logic educational software are available, however these existing programs were found to be unsuitable for our use in providing alternative mode subject delivery. This prompted the development of a Microsoft Windows TM tutorial suite, called WinLogiLab. WinLogiLab comprises of a set of tutorials that uses student provided input data, to perform the initial design steps for digital Combinatorial and Sequential logic circuits. The combinatorial tutorials are designed to show the link between Boolean Algebra and Digital Logic circuits, and follows the initial design steps: from Boolean algebra, truth tables, to Exact and the Heuristic minimisation techniques, to finally produce the combinatorial circuit. Similarly, the sequential tutorials can design simple State Machine Counters, and can model more complex Finite State Automata.

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 of casting them, but also the most efficient way of solving them. In this thesis we will present several techniques to advance search-based algorithms in the 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 strong rules of inference to more sophisticated online approaches such as dynamic partitioning. Furthermore, we will show that all of the presented techniques achieve an essential improvement of the search process when solving QBF. At the same time the displayed empirical results also reveal the orthogonality of the different techniques with respect to performance. Generally speaking each approach performs well on a particular subset of benchmarks, but performs poorly on others. Consequently, an adaptive employment of the available techniques that maximizes the performance would result in further improvements. We will demonstrate that such an adaptive approach can pay off in practice, by presenting the results of using machine learning methods to dynamically select the best variable ordering heuristics during search.

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 of casting them, but also the most efficient way of solving them. In this thesis we will present several techniques to advance search-based algorithms in the 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 strong rules of inference to more sophisticated online approaches such as dynamic partitioning. Furthermore, we will show that all of the presented techniques achieve an essential improvement of the search process when solving QBF. At the same time the displayed empirical results also reveal the orthogonality of the different techniques with respect to performance. Generally speaking each approach performs well on a particular subset of benchmarks, but performs poorly on others. Consequently, an adaptive employment of the available techniques that maximizes the performance would result in further improvements. We will demonstrate that such an adaptive approach can pay off in practice, by presenting the results of using machine learning methods to dynamically select the best variable ordering heuristics during search.

Boolean Satisfiability (SAT) is a fundamental NP-complete problem of determining whether there exists an assignment of variables which makes a Boolean formula evaluate to True. SAT is a convenient representation for many naturally occurring optimization and decisions problems such as planning and circuit verification. SAT is most commonly solved by a form of backtracking search which systematically explores the space of possible variable assignments. We show that the order in which variable polarities are assigned can have a significant impact on the performance of backtracking algorithms. We present several ways of transforming SAT instances into non-linear objective functions and describe three value-ordering methods based on iterative optimization techniques. We implement and test these heuristics in the widely-recognized MiniSAT framework. The first approach determines polarities by applying Newton's Method to a sparse system of non-linear objective functions whose roots correspond to the satisfying assignments of the propositional formula. The second approach determines polarities by minimizing an objective function corresponding to the number of clauses conflicting with each assignment. The third approach determines preferred polarities by performing stochastic gradient descent on objective functions sampled from a family of continuous potentials. The heuristics are evaluated on a set of standard benchmarks including random, crafted and industrial problems. We compare our results to five existing heuristics, and show that MiniSAT equipped with our heuristics often outperforms state-of-the-art SAT solvers.

Cells behave as complex systems with regulatory processes that make use of many elements such as switches based on thresholds, memory, feedback, error-checking, and other components commonly encountered in electrical engineering. It is therefore not surprising that these complex systems are amenable to study by engineering methods. A great deal of effort has been spent on observing how cells store, modify, and use information. Still, an understanding of how one uses this knowledge to exert control over cells within a living organism is unavailable. Our prime objective is "Personalized Cancer Therapy" which is based on characterizing the treatment for every individual cancer patient. Knowing how one can systematically alter the behavior of an abnormal cancerous cell will lead towards personalized cancer therapy. Towards this objective, it is required to construct a model for the regulation of the cell and utilize this model to devise effective treatment strategies. The proposed treatments will have to be validated experimentally, but selecting good treatment candidates is a monumental task by itself. It is also a process where an analytic approach to systems biology can provide significant breakthrough. In this dissertation, theoretical frameworks towards effective treatment strategies in the context of probabilistic Boolean networks, a class of gene regulatory networks, are addressed. These proposed analytical tools provide insight into the design of effective therapeutic interventions.

Implicit surface modeling is attracting attention, because a complex object can be constructed easily and intuitively from some simple primitive objects, defined by primitive defining functions, using successive compositions of blending operations. Blending operations play a major role in implicit surfaces, because they can join intersecting primitive objects (operands) smoothly with transitions generated automatically by blending operators. Hence, this dissertation proposes three new methods: (1) the scale method, (2) field functions with adjustable inner and outer radii, and (3) the translation method, for developing blending operations that have blending range controls. That is, the proposed blending operations provide blending range parameters to adjust the size and shape of the transition of the blending surface freely, without deforming the shapes of blended primitives totally. The first and the third methods offer blending range controls by developing new blending operators, whereas the second method does the similar things by developing new primitive defining functions. The scale method is a generalized method. It provides a framework to transform any existing blending operators or arc-shaped curves into the blending operator that has the following properties: (1) Provides blending range and curvature parameters to adjust the size and shape of the transition of the blending surface, without deforming the shapes of blended primitives totally. (2) Behaves like Max/Min(x1,¡K,xk) operators in non-blending regions in the entire domain. As a result, it gives a more intuitive shape control on modeling its subsequent blends. (3) Possesses C1 continuity in the entire domain except the origin. As a result, it can prevent from generating non-smooth surfaces on sequential blends with overlapped blending regions. (4) Works to blend both non-zero and zero implicit surfaces. (5) Can be a new primitive in other blends, especially in Soft blending. (6) Applies for bulge elimination. Field functions with adjustable inner and outer radii provide parameters to adjust the inner and the outer radii of influence, respectively. This dissertation proposes four different transforms to develop this kind of field functions. Thus, using the proposed field functions as the new primitive defining functions of soft object modeling, Soft blending, R-functions, Ricci¡¦s super-ellipsoid blends and Perlin¡¦s set operations: (1) Can retain their low computing complexity. (2) Can perform the blending range controls, by adjusting the inner and the outer radii of influence of the proposed field functions. The translation method is also a generalized method. It offers a framework to transform any existing blending operators or arc-shaped curves into controllable blending operators for blending zero implicit surfaces. A controllable blending operator has the following properties: (1) Offers blending range and curvature parameters to adjust the size and shape of transition of the blending surface, without deforming the shapes of blended primitives completely. (2) Provides parameters mi, i=1,2,¡K,k, to behave like Max/Min(x1/m1,¡K,xk/mk) operators on non-blending regions in the entire domain, and its zero level blending surface remains unchanged, whatever mi, i=1,2,¡K,k, are set. As a result, by adjusting mi, i=1,2,¡K,k, a controllable blending operator has the following abilities to control its primitives¡¦ subsequent blends:

A Boolean partition algebra is a pair $(B,F)$ where $B$ is a Boolean algebra and $F$ is a filter on the semilattice of partitions of $B$ where $\bigcup F=B\setminus\{0\}$. In this dissertation, we shall investigate the algebraic theory of Boolean partition algebras and their connection with uniform spaces. In particular, we shall show that the category of complete non-Archimedean uniform spaces is equivalent to a subcategory of the category of Boolean partition algebras, and notions such as supercompleteness of non-Archimedean uniform spaces can be formulated in terms of Boolean partition algebras.

Modeling gene regulation is an important problem in genomic research. The Boolean network (BN) and its generalization Probabilistic Boolean network (PBN) have been proposed to model genetic regulatory interactions. BN is a deterministic model while PBN is a stochastic model. In a PBN, on one hand, its stationary distribution gives important information about the long-run behavior of the network. On the other hand, one may be interested in system synthesis which requires the construction of networks from the observed stationary distribution. This results in an inverse problem of constructing PBNs from a given stationary distribution and a given set of Boolean Networks (BNs), which is ill-posed and challenging, because there may be many networks or no network having the given properties and the size of the inverse problem is huge. The inverse problem is first formulated as a constrained least squares problem. A heuristic method is then proposed based on the conjugate gradient (CG) algorithm, an iterative method, to solve the resulting least squares problem. An estimation method for the parameters of the PBNs is also discussed. Numerical examples are then given to demonstrate the effectiveness of the proposed methods. However, the PBNs generated by the above algorithm depends on the initial guess and is not unique. A heuristic method is then proposed for generating PBNs from a given transition probability matrix. Unique solution can be obtained in this case. Moreover, these algorithms are able to recover the dominated BNs and therefore the major structure of the network. To further evaluate the feasible solutions, a maximum entropy approach is proposed using entropy as a measure of the fitness. Newton’s method in conjunction with the CG method is then applied to solving the inverse problem. The convergence rate of the proposed method is demonstrated. Numerical examples are also given to demonstrate the effectiveness of our proposed method. Another important problem is to find the optimal control policy for a PBN so as to avoid the network from entering into undesirable states. By applying external control, the network is desired to enter into some state within a few time steps. For PBN CONTROL, people propose to find a control sequence such that the network will terminate in the desired state with a maximum probability. Also, the problem of minimizing the maximum cost is considered. Integer linear programming (ILP) and dynamic programming (DP) in conjunction with hard constraints are then employed to solve the above problems. Numerical experiments are given to demonstrate the effectiveness of our algorithms. A hardness result is demonstrated and suggests that PBN CONTROL is harder than BN CONTROL. In addition, deciding the steady state probability in PBN for a specified global state is demonstrated to be NP-hard. However, due to the high computational complexity of PBNs, DP method is computationally inefficient for a large size network. Inspired by the state reduction strategies studied in [86], the DP method in conjunction with state reduction approach is then proposed to reduce the computational cost of the DP method. Numerical examples are given to demonstrate both the effectiveness and the efficiency of our proposed method. / published_or_final_version / Mathematics / Doctoral / Doctor of Philosophy