Efficient manipulation of Boolean functions is an important component of many computer-aided design task. As a data structure for representing and manipulating Boolean functions, Binary Decision Diagrams are commonly used. These diagrams are commonly used in many fields such as model checking, system verification, circuit design, etc. In this thesis we describe these diagrams and there are present their modifications. Furthermore, this paper present and describes techniques for effective handling and representation of binary decision diagrams. This thesis describes the design and implementation of library that will work with these diagrams. It is further discussed how the developed library can be used within the library VATA for manipulating tree automata. Finally, the library was compared with well known and heavily optimized library CUDD, which is public and with library CacBDD. The experimental results showed that the performance of the proposed library is quite close to that of CUDD a CacBDD (has comparable and mostly even slightly better performance).

Le but de cette thèse est l'étude des Automates Cellulaires (AC) dans la perspective des fonctions booléennes et des dessins combinatoires. Au-delà de son intérêt théorique, cette recherche est motivée par ses applications à la cryptographie, puisque les fonctions booléennes et les dessins combinatoires sont utilisés pour construire des générateurs de nombres pseudo aléatoires (Pseudorandom Number Generators, PRNG) et des schémas de partage de secret (Secret Sharing Schemes, SSS). Les résultats présentés dans la thèse ont été développés sur trois lignes de recherche, organisées comme suit. La première ligne porte sur l'utilisation des algorithmes d'optimisation heuristique pour chercher des fonctions booléennes ayant des bonnes propriétés cryptographiques, à utiliser comme des règles locales dans des PRNG basés sur les AC. La motivation principale est l'amélioration du générateur de Wolfram basé sur la règle 30, qui a été montré être vulnérable vis à vis de deux attaques cryptanalytiques. La deuxième ligne s'occupe des fonctions booléennes vectorielles engendrées par les règles globales des AC. La première contribution considère la période des pré-images des configurations spatialement périodiques dans les AC surjectifs, et l'analyse des propriétés cryptographiques des règles globales des AC. La troisième ligne se concentre sur les dessins combinatoires engendrés par les AC, en considérant les Carrés Latins Orthogonaux (Orthogonal Latin Squares, OLS), qui sont équivalents aux SSS. En particulier, on donne une caractérisation algébrique des OLS engendrés par les AC linéaires, et on utilise des algorithmes heuristiques pour construire des OLS basés sur des AC non linéaires. / The goal of this thesis is the investigation of Cellular Automata (CA) from the perspective of Boolean functions and combinatorial designs. Beside its theoretical interest, this research finds its motivation in cryptography, since Boolean functions and combinatorial designs are used to construct Pseudorandom Number Generators (PRNG) and Secret Sharing Schemes (SSS). The results presented in the thesis are developed along three research lines, organized as follows. The first line considers the use of heuristic optimization algorithms to search for Boolean functions with good cryptographic properties, to be used as local rules in CA-based PRNG. The main motivation is to improve Wolfram's generator based on rule 30, which has been shown to be vulnerable against two cryptanalytic attacks. The second line deals with vectorial Boolean functions induced by CA global rules. The first contribution considers the period of preimages of spatially periodic configurations in surjective CA, and analyze the cryptographic properties of CA global rules. The third line focuses on the combinatorial designs generated by CA, specifically considering Orthogonal Latin Squares (OLS), which are equivalent to SSS. In particular, an algebraic characterization of OLS generated by linear CA is given, and heuristic algorithms are used to build OLS based on nonlinear CA.

In contrast to a single clause a pseudo-Boolean (PB) constraint is much more expressive and hence it is easier to define problems with the help of PB constraints. But while PB constraints provide us with a high-level problem description, it has been shown that solving PB constraints can be done faster with the help of a SAT solver. To apply such a solver to a PB constraint we have to encode it with clauses into conjunctive normal form (CNF). While we can find a basic encoding into CNF which is equivalent to a given PB constraint, the solving time of a SAT solver significantly depends on different properties of an encoding, e.g. the number of clauses or if generalized arc consistency (GAC) is maintained during the search for a solution. There are various PB encodings that try to optimize or balance these properties. This thesis is about such encodings. For a better understanding of the research field an overview about the state-of-the art encodings is given. The focus of the overview is a simple but complete description of each encoding, such that any reader could use, implement and extent them in his own work. In addition two novel encodings are presented: The Sequential Weight Counter (SWC) encoding and the Binary Merger Encoding. While the SWC encoding provides a very simple structure – it is listed in four lines – empirical evaluation showed its practical usefulness in various applications. The Binary Merger encoding reduces the number of clauses a PB encoding needs while having the important GAC property. To the best of our knowledge currently no other encoding has a lower upper bound for the number of clauses produced by a PB encoding with this property. This is an important improvement of the state-of-the art, since both GAC and a low number of clauses are vital for an improved solving time of the SAT solver. The thesis also contributes to the development of new applications for PB constraint encodings. The programming library PBLib provides researchers with an open source implementation of almost all PB encodings – including the encodings for the special cases at-most-one and cardinality constraints. The PBLib is also the foundation of the presented weighted MaxSAT solver optimax, the PBO solver pbsolver and the WBO, PBO and weighted MaxSAT solver npSolver.

<p>The method of forcing is widely used in set theory to obtain&nbsp;various consistency proofs. Complete Boolean algebras play the main role&nbsp;in applications of forcing. Therefore it is useful to define games on Boolean&nbsp;algebras that characterize their properties important for the method. The&nbsp;most investigated game is Jech&rsquo;s distributivity game, such that the first&nbsp;player has the winning strategy iff the algebra is not (&omega;, 2)-distributive.&nbsp;We define another game characterizing the collapsing of the continuum to&nbsp;&omega;, prove several sufficient conditions for the second player to have a winning&nbsp;strategy, and obtain a Boolean algebra on which the game is undetermined.&nbsp;</p> / <p>Forsing je metod &scaron;iroko kori&scaron;ćen u teoriji skupova za dokaze konsistentnosti. Kompletne&nbsp; Bulove algebre igraju glavnu ulogu u primenama forsinga. Stoga je korisno definisati igre na Bulovim algebrama koje karakteri&scaron;u njihove osobine od značaja za taj metod. Najbolje proučena je Jehova igra, koja ima osobinu da prvi igrač ima pobedničku strategiju akko algebra nije (&omega;, 2)-distributivna. U tezi defini&scaron;emo jo&scaron; jednu igru, koja karakteri&scaron;e kolaps kontinuuma na &omega;, dokazujemo nekoliko dovoljnih uslova da bi drugi igra&scaron; imao pobedničku strategiju, i konstrui&scaron;emo Bulovu algebru na kojoj je igra neodređena.</p>

<p>A priori limit operator&gt;. maps sequence of a set X into a subset of X.<br />There exists maximal topology on X such that for each sequence x there holds<br />&gt;.(x) C limx. The space obtained in such way is always sequential.<br />If a priori limit operator each sequence x which satisfy lim sup x = lim inf x<br />maps into {lim sup x}, then we obtain the sequential topology Ts.&nbsp; If a priori &#39;limit<br />operator maps each sequence x into {lim sup x}, we obtain topology denoted by<br />aT. Properties of these topologies, in general, on class of Boolean algebras with<br />condition (Ii) and on class of weakly-distributive b-cc algebras are investigated.<br />Also, the relations between these classes and other classes of Boolean algebras are<br />considered.</p> / <p>A priori limit operator A svakom nizu elemenata skupa X dodeljuje neki<br />podskup skupa X. Tada na skupu X postoji maksimalna topologija takva da za<br />svaki niz x vazi A(X) c lim x. Tako dobijen prostor je uvek sekvencijalan.<br />Ako a priori limit operator svakom nizu x koji zadovoljava uslov lim sup x =<br />liminfx dodeljuje skup {limsupx} onda se, na gore opisan nacin, dobija tzv.<br />sekvencijalna topologija Ts. Ako a priori limit operator svakom nizu x dodeljuje<br />{lim sup x}, dobija se topologija oznacena sa OT.&nbsp; Ispitivane su osobine ovih<br />topologija, generalno, na klasi Bulovih algebri koje zadovoljavaju uslov (Ii) ina<br />klasi slabo-distributivnih i b-cc algebri, kao i odnosi ovih klasa prema drugim<br />klasama Bulovih algebri.</p>

This thesis consists of two parts. In part I, a group of combinatorial problems pertaining to strings, boolean matrices and graphs is studied. For given two strings x and y, their edit distance is the minimum number of character insertions, deletions and substitutions required to convert x into y. In this thesis we provide an algorithm that computes a constant approximation of edit distance in truly sub-quadratic time. Based on the provided ideas, we construct a separate sub- quadratic time algorithm that can find an occurrence of a pattern P in a given text T while allowing a few edit errors. Afterwards we study the boolean matrix multiplication (BMM) problem where given two boolean matrices, the aim is to find their product over boolean semi-ring. For this problem, we present two combinatorial models and show in these models BMM requires Ω(n3 /2O( √ log n) ) and Ω(n7/3 /2O( √ log n) ) work respectively. Furthermore, we also give a construction of a sparse sub-graph that preserves the distance between a designated source and any other vertex as long as the total weight increment of all the edges is bounded by some constant. In part II, we study the efficient construction of quasi-Gray codes. We give a construction of space optimal quasi-Gray codes over odd sized alphabets with read complexity 4...

This thesis compares two modeling methods, subdivision and booleans, which are used for the creation of hard surface assets in the gaming industry. The parameters that are assessed are the time taken to create the models with the respective method and the quality of the models. Quality refers to the presence of shading artifacts. In order to compare the methods, models of varying complexity have been created, the time of creation has been measured and experts in 3D modeling have assessed the quality. The results show that the boolean method is better suited for complex models, while both methods work well for simpler models. / Den här avhandlingen jämför två modelleringsmetoder, subdivision och booleans, som används för skapandet av hardsurface assets inom spelbranschen. Parametrarna som bedöms är den tid det tar att skapa modellerna med respektive metod och kvalitén på modellerna. Med kvalité avses förekomsten av shading artefakter. För att jämföra metoderna har modeller av varierande komplexitet skapats, skapandets tid har mätts och experter inom 3D-modellering har bedömt kvalitén. Resultatet visar att booleansmetoden är bättre lämpad för komplexa modeller medan båda metoder fungerar bra för simplare modeller.

Les maladies complexes comme le Cancer et la maladie d'Alzheimer sont causées par des perturbations moléculaires multiples responsables d'un comportement cellulaire pathologique.Un enjeu majeur de la médecine de précision est l'identification des perturbations moléculaires induites par les maladies complexes et les thérapies à partir de leurs conséquences sur les phénotypes cellulaire.Nous définissons un modèle des maladies complexes,appelé la reprogrammation comportementale,assimilant les perturbations moléculaires à des altérations des fonctions dynamiques locales de systèmes dynamiques discrets induisant une reprogrammation de la dynamique globale du réseau. Ce cadre de modélisation s'appuie d'une part, sur les réseaux Booléens contrôlés, qui sont des réseaux Booléens dans lesquels sont insérés des paramètres de contrôle modélisant les perturbations et, d'autre part, sur la définition de modes (Possibilité, Nécessité) permettant d'exprimer les objectifs de cette reprogrammation.A partir de ce cadre, nous démontrons que le calcul des noyaux, i.e., des ensembles minimaux d'actions permettant la reprogrammation selon un mode s'exprime comme un problème d'inférence abductive en logique propositionnelle. En nous appuyant sur les méthodes historiques de calcul d'impliquants premiers des fonctions Booléennes,nous développons deux méthodes permettant le calcul exhaustif des noyaux de la reprogrammation. Enfin, nous évaluons la pertinence du cadre de modélisation pour l'identification des perturbations responsables de la transformation d'une cellule saine en cellule cancéreuse et la découverte de cibles thérapeutiques sur un modèle du cancer du sein. Nous montrons notamment que les perturbations inférées par nos méthodes sont compatibles avec la connaissance biologique en discriminant les oncogènes des gènes suppresseurs de tumeurs et en récupérant la mutation du gène BRCA1. De plus, la méthode récupère le phénomène de létalité synthétique entre PARP1 et BRCA1, qui constitue un traitement anticancéreux optimal car il cible spécifiquement les cellules tumorales. / Complex diseases such as cancer and Alzheimer's are caused by multiple molecular perturbations responsible for pathological cellular behavior. A major challenge of precision medicine is the identification of the molecular perturbations induced by the disease and the therapies from their consequences on cell phenotypes. We define a model of complex diseases, called behavioral reprogramming, that assimilates the molecular perturbations to alterations of the dynamic local functions of discrete dynamical systems inducing a reprogramming of the global dynamics of the network. This modeling framework relies on the one hand, on Control Boolean networks, which are Boolean networks containing control parameters modeling the perturbations and, on the other hand, the definition of reprogramming modes (Possibility, Necessity) expressing the objective of the behavioral reprogramming. From this framework, we demonstrate that the computation of the cores, namely, the minimal sets of action allowing reprogramming is a problem of abductive inference in propositional logic. Using historical methods computing the prime implicants of Boolean functions, we develop two methods computing all the reprogramming cores.Finally, we evaluate the modeling framework for the identification of perturbations responsible for the transformation of a healthy cell into a cancercell and the discovery of therapeutic targets ona model of breast cancer. In particular, we showthat the perturbations inferred by our methods a recompatible with biological knowledge by discriminating oncogenes and tumor suppressor genes and by recovering the causal of the BRCA1 gene. In addition, the method recovers the synthetic lethality phenomenon between PARP1 and BRCA1 that constitutes an optimal anti-cancer treatment because it specifically targets tumor cells.

With the transition from single-core to multi-core computing and CMOS technology reaching its physical limits, new computing architectures which are scalable, robust, and low-power are required. A promising alternative to conventional computing architectures are Cellular Automata (CA) networks and Random Boolean Networks (RBN), where simple computational nodes combine to form a network that is capable of performing a larger computational task. It has previously been shown that RBNs can offer superior characteristics over mesh networks in terms of robustness, information processing capabilities, and manufacturing costs while the locally connected computing elements of a CA network provide better scalability and low average interconnect length. This study presents a low level hardware analysis of these architectures using a framework which generates the HDL code and netlist of these networks for various network parameters. The HDL code and netlists are then used to simulate these new computing architectures to estimate the latency, area and power consumed when implemented on silicon and performing a pre-determined computation. We show that for RBNs, information processing is faster compared to a CA network, but CA networks are found to a have lower and better distribution of power dissipation than RBNs because of their regular structure. A well-established task to determine the latency of operation for these architectures is presented for a good understanding of the effect of non-local connections in a network. Programming the nodes for this purpose is done externally using a novel self-configuration algorithm requiring minimal hardware. Configuration for RBNs is done by sending in configuration packets through a randomly chosen node. Logic for identifying the topology for the network is implemented for the nodes in the RBN network to enable compilers to analyze and generate the configuration bit stream for that network. On the other hand, the configuration of the CA network is done by passing in configuration data through the inputs on one of the sides of the cell array and shifting it into the network. A study of the overhead of the network configuration and topology identification mechanisms are presented. An analysis of small-world networks in terms of interconnect power and information propagation capability has been presented. It has been shown that small-world networks, whose randomness lies between that of completely regular and completely irregular networks, are realistic while providing good information propagation capability. This study provides valuable information to help designers make decisions for various performance parameters for both RBN and CA networks, and thus to find the best design for the application under consideration.

In this manuscript we perform a rigorous mathematical investigation of the behavior opportunistic network models exhibit when two major real-world problems are taken into account. The first problem considered is obstruction. Here we model the network using an obstructed Gilbert graph which is a classical Gilbert graph but where there exist zones where no nodes are allowed to be placed. We take a look at percolation properties of this model, that is we investigate random graph configurations for which a component of infinite size has strictly positive probability to be created. The second problem considered in this thesis is mobility. Of course mobility in and of itself is not a problem but a feature in any network that follows the store-carry-forward paradigm. However it can be problematic to properly handle in a mathematical model. In the past this has been done by modelling movement by a series of static network configurations. However, with this technique it can be difficult to get a grasp on some of the time sensitive properties of the network. In this work we introduce the time bounded cylinder model which enables an analysis over a complete timeframe. We provide normal approximations for important properties of the model, like its covered volume and the number of isolated nodes. As we are using rigorous mathematics to tackle problems which computer scientists working in the field of distributed systems are faced with, we bring the two fields closer together.