Boolean networks as modelling framework
Florian eGreil
2012-08-01
Full Text Available In a network, the components of a given system are represented as nodes, the interactions are abstracted as links between the nodes. Boolean networks refer to a class of dynamics on networks, in fact it is the simplest possible dynamics where each node has a value 0 or 1. This allows to investigate extensively the dynamics both analytically and by numerical experiments. The present article focuses on the theoretical concept of relevant components and the immediate application in plant biology, references for more in-depths treatment of the mathematical details are also given.
Boolean network model predicts knockout mutant phenotypes of fission yeast.
Maria I Davidich
Full Text Available BOOLEAN NETWORKS (OR: networks of switches are extremely simple mathematical models of biochemical signaling networks. Under certain circumstances, Boolean networks, despite their simplicity, are capable of predicting dynamical activation patterns of gene regulatory networks in living cells. For example, the temporal sequence of cell cycle activation patterns in yeasts S. pombe and S. cerevisiae are faithfully reproduced by Boolean network models. An interesting question is whether this simple model class could also predict a more complex cellular phenomenology as, for example, the cell cycle dynamics under various knockout mutants instead of the wild type dynamics, only. Here we show that a Boolean network model for the cell cycle control network of yeast S. pombe correctly predicts viability of a large number of known mutants. So far this had been left to the more detailed differential equation models of the biochemical kinetics of the yeast cell cycle network and was commonly thought to be out of reach for models as simplistic as Boolean networks. The new results support our vision that Boolean networks may complement other mathematical models in systems biology to a larger extent than expected so far, and may fill a gap where simplicity of the model and a preference for an overall dynamical blueprint of cellular regulation, instead of biochemical details, are in the focus.
Modeling integrated cellular machinery using hybrid Petri-Boolean networks.
Natalie Berestovsky
Full Text Available The behavior and phenotypic changes of cells are governed by a cellular circuitry that represents a set of biochemical reactions. Based on biological functions, this circuitry is divided into three types of networks, each encoding for a major biological process: signal transduction, transcription regulation, and metabolism. This division has generally enabled taming computational complexity dealing with the entire system, allowed for using modeling techniques that are specific to each of the components, and achieved separation of the different time scales at which reactions in each of the three networks occur. Nonetheless, with this division comes loss of information and power needed to elucidate certain cellular phenomena. Within the cell, these three types of networks work in tandem, and each produces signals and/or substances that are used by the others to process information and operate normally. Therefore, computational techniques for modeling integrated cellular machinery are needed. In this work, we propose an integrated hybrid model (IHM that combines Petri nets and Boolean networks to model integrated cellular networks. Coupled with a stochastic simulation mechanism, the model simulates the dynamics of the integrated network, and can be perturbed to generate testable hypotheses. Our model is qualitative and is mostly built upon knowledge from the literature and requires fine-tuning of very few parameters. We validated our model on two systems: the transcriptional regulation of glucose metabolism in human cells, and cellular osmoregulation in S. cerevisiae. The model produced results that are in very good agreement with experimental data, and produces valid hypotheses. The abstract nature of our model and the ease of its construction makes it a very good candidate for modeling integrated networks from qualitative data. The results it produces can guide the practitioner to zoom into components and interconnections and investigate them
Dynamical modeling of the cholesterol regulatory pathway with Boolean networks
Corcos Laurent
2008-11-01
Full Text Available Abstract Background Qualitative dynamics of small gene regulatory networks have been studied in quite some details both with synchronous and asynchronous analysis. However, both methods have their drawbacks: synchronous analysis leads to spurious attractors and asynchronous analysis lacks computational efficiency, which is a problem to simulate large networks. We addressed this question through the analysis of a major biosynthesis pathway. Indeed the cholesterol synthesis pathway plays a pivotal role in dislypidemia and, ultimately, in cancer through intermediates such as mevalonate, farnesyl pyrophosphate and geranyl geranyl pyrophosphate, but no dynamic model of this pathway has been proposed until now. Results We set up a computational framework to dynamically analyze large biological networks. This framework associates a classical and computationally efficient synchronous Boolean analysis with a newly introduced method based on Markov chains, which identifies spurious cycles among the results of the synchronous simulation. Based on this method, we present here the results of the analysis of the cholesterol biosynthesis pathway and its physiological regulation by the Sterol Response Element Binding Proteins (SREBPs, as well as the modeling of the action of statins, inhibitor drugs, on this pathway. The in silico experiments show the blockade of the cholesterol endogenous synthesis by statins and its regulation by SREPBs, in full agreement with the known biochemical features of the pathway. Conclusion We believe that the method described here to identify spurious cycles opens new routes to compute large and biologically relevant models, thanks to the computational efficiency of synchronous simulation. Furthermore, to the best of our knowledge, we present here the first dynamic systems biology model of the human cholesterol pathway and several of its key regulatory control elements, hoping it would provide a good basis to perform in silico
Drossel, Barbara
2007-01-01
This review explains in a self-contained way the properties of random Boolean networks and their attractors, with a special focus on critical networks. Using small example networks, analytical calculations, phenomenological arguments, and problems to solve, the basic concepts are introduced and important results concerning phase diagrams, numbers of relevant nodes and attractor properties are derived.
Mapping Complex Networks: Exploring Boolean Modeling of Signal Transduction Pathways
Bhardwaj, Gaurav; Wells, Christine P.; Albert, Reka; van Rossum, Damian B.; Patterson, Randen L
2009-01-01
In this study, we explored the utility of a descriptive and predictive bionetwork model for phospholipase C-coupled calcium signaling pathways, built with non-kinetic experimental information. Boolean models generated from these data yield oscillatory activity patterns for both the endoplasmic reticulum resident inositol-1,4,5-trisphosphate receptor (IP3R) and the plasma-membrane resident canonical transient receptor potential channel 3 (TRPC3). These results are specific as randomization of ...
Relative stability of network states in Boolean network models of gene regulation in development.
Zhou, Joseph Xu; Samal, Areejit; d'Hérouël, Aymeric Fouquier; Price, Nathan D; Huang, Sui
2016-01-01
Progress in cell type reprogramming has revived the interest in Waddington's concept of the epigenetic landscape. Recently researchers developed the quasi-potential theory to represent the Waddington's landscape. The Quasi-potential U(x), derived from interactions in the gene regulatory network (GRN) of a cell, quantifies the relative stability of network states, which determine the effort required for state transitions in a multi-stable dynamical system. However, quasi-potential landscapes, originally developed for continuous systems, are not suitable for discrete-valued networks which are important tools to study complex systems. In this paper, we provide a framework to quantify the landscape for discrete Boolean networks (BNs). We apply our framework to study pancreas cell differentiation where an ensemble of BN models is considered based on the structure of a minimal GRN for pancreas development. We impose biologically motivated structural constraints (corresponding to specific type of Boolean functions) and dynamical constraints (corresponding to stable attractor states) to limit the space of BN models for pancreas development. In addition, we enforce a novel functional constraint corresponding to the relative ordering of attractor states in BN models to restrict the space of BN models to the biological relevant class. We find that BNs with canalyzing/sign-compatible Boolean functions best capture the dynamics of pancreas cell differentiation. This framework can also determine the genes' influence on cell state transitions, and thus can facilitate the rational design of cell reprogramming protocols. PMID:26965665
Autonomous Modeling, Statistical Complexity and Semi-annealed Treatment of Boolean Networks
Gong, Xinwei
This dissertation presents three studies on Boolean networks. Boolean networks are a class of mathematical systems consisting of interacting elements with binary state variables. Each element is a node with a Boolean logic gate, and the presence of interactions between any two nodes is represented by directed links. Boolean networks that implement the logic structures of real systems are studied as coarse-grained models of the real systems. Large random Boolean networks are studied with mean field approximations and used to provide a baseline of possible behaviors of large real systems. This dissertation presents one study of the former type, concerning the stable oscillation of a yeast cell-cycle oscillator, and two studies of the latter type, respectively concerning the statistical complexity of large random Boolean networks and an extension of traditional mean field techniques that accounts for the presence of short loops. In the cell-cycle oscillator study, a novel autonomous update scheme is introduced to study the stability of oscillations in small networks. A motif that corrects pulse-growing perturbations and a motif that grows pulses are identified. A combination of the two motifs is capable of sustaining stable oscillations. Examining a Boolean model of the yeast cell-cycle oscillator using an autonomous update scheme yields evidence that it is endowed with such a combination. Random Boolean networks are classified as ordered, critical or disordered based on their response to small perturbations. In the second study, random Boolean networks are taken as prototypical cases for the evaluation of two measures of complexity based on a criterion for optimal statistical prediction. One measure, defined for homogeneous systems, does not distinguish between the static spatial inhomogeneity in the ordered phase and the dynamical inhomogeneity in the disordered phase. A modification in which complexities of individual nodes are calculated yields vanishing
From Boolean Network Model to Continuous Model Helps in Design of Functional Circuits
Bin Shao; Xiang Liu; Dongliang Zhang; Jiayi Wu; Qi Ouyang
2015-01-01
Computational circuit design with desired functions in a living cell is a challenging task in synthetic biology. To achieve this task, numerous methods that either focus on small scale networks or use evolutionary algorithms have been developed. Here, we propose a two-step approach to facilitate the design of functional circuits. In the first step, the search space of possible topologies for target functions is reduced by reverse engineering using a Boolean network model. In the second step, ...
Reverse engineering Boolean networks: from Bernoulli mixture models to rule based systems.
Mehreen Saeed
Full Text Available A Boolean network is a graphical model for representing and analyzing the behavior of gene regulatory networks (GRN. In this context, the accurate and efficient reconstruction of a Boolean network is essential for understanding the gene regulation mechanism and the complex relations that exist therein. In this paper we introduce an elegant and efficient algorithm for the reverse engineering of Boolean networks from a time series of multivariate binary data corresponding to gene expression data. We call our method ReBMM, i.e., reverse engineering based on Bernoulli mixture models. The time complexity of most of the existing reverse engineering techniques is quite high and depends upon the indegree of a node in the network. Due to the high complexity of these methods, they can only be applied to sparsely connected networks of small sizes. ReBMM has a time complexity factor, which is independent of the indegree of a node and is quadratic in the number of nodes in the network, a big improvement over other techniques and yet there is little or no compromise in accuracy. We have tested ReBMM on a number of artificial datasets along with simulated data derived from a plant signaling network. We also used this method to reconstruct a network from real experimental observations of microarray data of the yeast cell cycle. Our method provides a natural framework for generating rules from a probabilistic model. It is simple, intuitive and illustrates excellent empirical results.
Exploring phospholipase C-coupled Ca(2+) signalling networks using Boolean modelling.
Bhardwaj, G; Wells, C P; Albert, R; van Rossum, D B; Patterson, R L
2011-05-01
In this study, the authors explored the utility of a descriptive and predictive bionetwork model for phospholipase C-coupled calcium signalling pathways, built with non-kinetic experimental information. Boolean models generated from these data yield oscillatory activity patterns for both the endoplasmic reticulum resident inositol-1,4,5-trisphosphate receptor (IP(3)R) and the plasma-membrane resident canonical transient receptor potential channel 3 (TRPC3). These results are specific as randomisation of the Boolean operators ablates oscillatory pattern formation. Furthermore, knock-out simulations of the IP(3)R, TRPC3 and multiple other proteins recapitulate experimentally derived results. The potential of this approach can be observed by its ability to predict previously undescribed cellular phenotypes using in vitro experimental data. Indeed, our cellular analysis of the developmental and calcium-regulatory protein, DANGER1a, confirms the counter-intuitive predictions from our Boolean models in two highly relevant cellular models. Based on these results, the authors theorise that with sufficient legacy knowledge and/or computational biology predictions, Boolean networks can provide a robust method for predictive modelling of any biological system. [Includes supplementary material]. PMID:21639591
Dynamical modeling of the cholesterol regulatory pathway with Boolean networks
Corcos Laurent; Kervizic Gwenael
2008-01-01
Abstract Background Qualitative dynamics of small gene regulatory networks have been studied in quite some details both with synchronous and asynchronous analysis. However, both methods have their drawbacks: synchronous analysis leads to spurious attractors and asynchronous analysis lacks computational efficiency, which is a problem to simulate large networks. We addressed this question through the analysis of a major biosynthesis pathway. Indeed the cholesterol synthesis pathway plays a pivo...
The receptor mosaic hypothesis of the engram: possible relevance of Boolean network modeling.
Zoli, M; Guidolin, D; Fuxe, K; Agnati, L F
1996-09-01
In the past 15 years, several lines of evidence have shown that receptors for chemical signals can interact in domains of the plasma membrane and possibly form molecular circuits encoding logical operators. In this frame, the receptor mosaic hypothesis of the engram was advanced. According to this proposal, aggregates of different receptor species (mosaics) may form in neuronal membranes (typically synapses) and constitute a memory trace (engram) of its activity. In the present paper, we present an attempt to model the functioning of aggregates of interacting receptors in membrane domains by means of random Boolean networks. PMID:8968825
Effect of memory in non-Markovian Boolean networks
Ebadi, Haleh; Ausloos, Marcel; Jafari, GholamReza
2016-01-01
One successful model of interacting biological systems is the Boolean network. The dynamics of a Boolean network, controlled with Boolean functions, is usually considered to be a Markovian (memory-less) process. However, both self organizing features of biological phenomena and their intelligent nature should raise some doubt about ignoring the history of their time evolution. Here, we extend the Boolean network Markovian approach: we involve the effect of memory on the dynamics. This can be explored by modifying Boolean functions into non-Markovian functions, for example, by investigating the usual non-Markovian threshold function, - one of the most applied Boolean functions. By applying the non-Markovian threshold function on the dynamical process of a cell cycle network, we discover a power law memory with a more robust dynamics than the Markovian dynamics.
Modeling and controlling the two-phase dynamics of the p53 network: a Boolean network approach
Although much empirical evidence has demonstrated that p53 plays a key role in tumor suppression, the dynamics and function of the regulatory network centered on p53 have not yet been fully understood. Here, we develop a Boolean network model to reproduce the two-phase dynamics of the p53 network in response to DNA damage. In particular, we map the fates of cells into two types of Boolean attractors, and we find that the apoptosis attractor does not exist for minor DNA damage, reflecting that the cell is reparable. As the amount of DNA damage increases, the basin of the repair attractor shrinks, accompanied by the rising of the apoptosis attractor and the expansion of its basin, indicating that the cell becomes more irreparable with more DNA damage. For severe DNA damage, the repair attractor vanishes, and the apoptosis attractor dominates the state space, accounting for the exclusive fate of death. Based on the Boolean network model, we explore the significance of links, in terms of the sensitivity of the two-phase dynamics, to perturbing the weights of links and removing them. We find that the links are either critical or ordinary, rather than redundant. This implies that the p53 network is irreducible, but tolerant of small mutations at some ordinary links, and this can be interpreted with evolutionary theory. We further devised practical control schemes for steering the system into the apoptosis attractor in the presence of DNA damage by pinning the state of a single node or perturbing the weight of a single link. Our approach offers insights into understanding and controlling the p53 network, which is of paramount importance for medical treatment and genetic engineering. (paper)
Modeling and controlling the two-phase dynamics of the p53 network: a Boolean network approach
Lin, Guo-Qiang; Ao, Bin; Chen, Jia-Wei; Wang, Wen-Xu; Di, Zeng-Ru
2014-12-01
Although much empirical evidence has demonstrated that p53 plays a key role in tumor suppression, the dynamics and function of the regulatory network centered on p53 have not yet been fully understood. Here, we develop a Boolean network model to reproduce the two-phase dynamics of the p53 network in response to DNA damage. In particular, we map the fates of cells into two types of Boolean attractors, and we find that the apoptosis attractor does not exist for minor DNA damage, reflecting that the cell is reparable. As the amount of DNA damage increases, the basin of the repair attractor shrinks, accompanied by the rising of the apoptosis attractor and the expansion of its basin, indicating that the cell becomes more irreparable with more DNA damage. For severe DNA damage, the repair attractor vanishes, and the apoptosis attractor dominates the state space, accounting for the exclusive fate of death. Based on the Boolean network model, we explore the significance of links, in terms of the sensitivity of the two-phase dynamics, to perturbing the weights of links and removing them. We find that the links are either critical or ordinary, rather than redundant. This implies that the p53 network is irreducible, but tolerant of small mutations at some ordinary links, and this can be interpreted with evolutionary theory. We further devised practical control schemes for steering the system into the apoptosis attractor in the presence of DNA damage by pinning the state of a single node or perturbing the weight of a single link. Our approach offers insights into understanding and controlling the p53 network, which is of paramount importance for medical treatment and genetic engineering.
Boolean network robotics: a proof of concept
Roli, Andrea; Pinciroli, Carlo; Birattari, Mauro
2011-01-01
Dynamical systems theory and complexity science provide powerful tools for analysing artificial agents and robots. Furthermore, they have been recently proposed also as a source of design principles and guidelines. Boolean networks are a prominent example of complex dynamical systems and they have been shown to effectively capture important phenomena in gene regulation. From an engineering perspective, these models are very compelling, because they can exhibit rich and complex behaviours, in spite of the compactness of their description. In this paper, we propose the use of Boolean networks for controlling robots' behaviour. The network is designed by means of an automatic procedure based on stochastic local search techniques. We show that this approach makes it possible to design a network which enables the robot to accomplish a task that requires the capability of navigating the space using a light stimulus, as well as the formation and use of an internal memory.
Boolean networks with reliable dynamics
Peixoto, Tiago P
2009-01-01
We investigated the properties of Boolean networks that follow a given reliable trajectory in state space. A reliable trajectory is defined as a sequence of states which is independent of the order in which the nodes are updated. We explored numerically the topology, the update functions, and the state space structure of these networks, which we constructed using a minimum number of links and the simplest update functions. We found that the clustering coefficient is larger than in random networks, and that the probability distribution of three-node motifs is similar to that found in gene regulation networks. Among the update functions, only a subset of all possible functions occur, and they can be classified according to their probability. More homogeneous functions occur more often, leading to a dominance of canalyzing functions. Finally, we studied the entire state space of the networks. We observed that with increasing systems size, fixed points become more dominant, moving the networks close to the frozen...
Enhancing Boolean networks with fuzzy operators and edge tuning
Poret, Arnaud; Monteiro Sousa, Claudio; Boissel, Jean-Pierre
2014-01-01
Quantitative modeling in systems biology can be difficult due to the scarcity of quantitative details about biological phenomenons, especially at the subcellular scale. An alternative to escape this difficulty is qualitative modeling since it requires few to no quantitative information. Among the qualitative modeling approaches, the Boolean network formalism is one of the most popular. However, Boolean models allow variables to be valued at only true or false, which can appear too simplistic ...
Representations of Boolean Functions by Perceptron Networks
Kůrková, Věra
Prague : Institute of Computer Science AS CR, 2014 - (Kůrková, V.; Bajer, L.; Peška, L.; Vojtáš, R.; Holeňa, M.; Nehéz, M.), s. 68-70 ISBN 978-80-87136-19-5. [ITAT 2014. European Conference on Information Technologies - Applications and Theory /14./. Demänovská dolina (SK), 25.09.2014-29.09.2014] R&D Projects: GA MŠk(CZ) LD13002 Institutional support: RVO:67985807 Keywords : perceptron networks * model complexity * Boolean functions Subject RIV: IN - Informatics, Computer Science
Forced synchronization of autonomous dynamical Boolean networks
We present the design of an autonomous time-delay Boolean network realized with readily available electronic components. Through simulations and experiments that account for the detailed nonlinear response of each circuit element, we demonstrate that a network with five Boolean nodes displays complex behavior. Furthermore, we show that the dynamics of two identical networks display near-instantaneous synchronization to a periodic state when forced by a common periodic Boolean signal. A theoretical analysis of the network reveals the conditions under which complex behavior is expected in an individual network and the occurrence of synchronization in the forced networks. This research will enable future experiments on autonomous time-delay networks using readily available electronic components with dynamics on a slow enough time-scale so that inexpensive data collection systems can faithfully record the dynamics
Forced synchronization of autonomous dynamical Boolean networks
Rivera-Durón, R. R., E-mail: roberto.rivera@ipicyt.edu.mx; Campos-Cantón, E., E-mail: eric.campos@ipicyt.edu.mx [División de Matemáticas Aplicadas, Instituto Potosino de Investigación Científica y Tecnológica A. C., Camino a la Presa San José 2055, Col. Lomas 4 Sección, C.P. 78216, San Luis Potosí, S.L.P. (Mexico); Campos-Cantón, I. [Facultad de Ciencias, Universidad Autónoma de San Luis Potosí, Álvaro Obregón 64, C.P. 78000, San Luis Potosí, S.L.P. (Mexico); Gauthier, Daniel J. [Department of Physics and Center for Nonlinear and Complex Systems, Duke University, Box 90305, Durham, North Carolina 27708 (United States)
2015-08-15
We present the design of an autonomous time-delay Boolean network realized with readily available electronic components. Through simulations and experiments that account for the detailed nonlinear response of each circuit element, we demonstrate that a network with five Boolean nodes displays complex behavior. Furthermore, we show that the dynamics of two identical networks display near-instantaneous synchronization to a periodic state when forced by a common periodic Boolean signal. A theoretical analysis of the network reveals the conditions under which complex behavior is expected in an individual network and the occurrence of synchronization in the forced networks. This research will enable future experiments on autonomous time-delay networks using readily available electronic components with dynamics on a slow enough time-scale so that inexpensive data collection systems can faithfully record the dynamics.
Model Checking of Boolean Process Models
Schneider, Christoph; Wehler, Joachim
2011-01-01
In the field of Business Process Management formal models for the control flow of business processes have been designed since more than 15 years. Which methods are best suited to verify the bulk of these models? The first step is to select a formal language which fixes the semantics of the models. We adopt the language of Boolean systems as reference language for Boolean process models. Boolean systems form a simple subclass of coloured Petri nets. Their characteristics are low tokens to mode...
The Influence of Canalization on the Robustness of Boolean Networks
Kadelka, Claus; Laubenbacher, Reinhard
2016-01-01
Time- and state-discrete dynamical systems are frequently used to model molecular networks. This paper provides a collection of mathematical and computational tools for the study of robustness in Boolean network models. The focus is on networks governed by $k$-canalizing functions, a recently introduced class of Boolean functions that contains the well-studied class of nested canalizing functions. The activities and sensitivity of a function quantify the impact of input changes on the function output. This paper generalizes the latter concept to $c$-sensitivity and provides formulas for the activities and $c$-sensitivity of general $k$-canalizing functions as well as canalizing functions with more precisely defined structure. A popular measure for the robustness of a network, the Derrida value, can be expressed as a weighted sum of the $c$-sensitivities of the governing canalizing functions, and can also be calculated for a stochastic extension of Boolean networks. These findings provide a computationally eff...
Caglar, Mehmet Umut; Pal, Ranadip
2011-03-01
Central dogma of molecular biology states that ``information cannot be transferred back from protein to either protein or nucleic acid''. However, this assumption is not exactly correct in most of the cases. There are a lot of feedback loops and interactions between different levels of systems. These types of interactions are hard to analyze due to the lack of cell level data and probabilistic - nonlinear nature of interactions. Several models widely used to analyze and simulate these types of nonlinear interactions. Stochastic Master Equation (SME) models give probabilistic nature of the interactions in a detailed manner, with a high calculation cost. On the other hand Probabilistic Boolean Network (PBN) models give a coarse scale picture of the stochastic processes, with a less calculation cost. Differential Equation (DE) models give the time evolution of mean values of processes in a highly cost effective way. The understanding of the relations between the predictions of these models is important to understand the reliability of the simulations of genetic regulatory networks. In this work the success of the mapping between SME, PBN and DE models is analyzed and the accuracy and affectivity of the control policies generated by using PBN and DE models is compared.
Boolean Factor Analysis by Attractor Neural Network
Frolov, A. A.; Húsek, Dušan; Muraviev, I. P.; Polyakov, P.Y.
2007-01-01
Roč. 18, č. 3 (2007), s. 698-707. ISSN 1045-9227 R&D Projects: GA AV ČR 1ET100300419; GA ČR GA201/05/0079 Institutional research plan: CEZ:AV0Z10300504 Keywords : recurrent neural network * Hopfield-like neural network * associative memory * unsupervised learning * neural network architecture * neural network application * statistics * Boolean factor analysis * dimensionality reduction * features clustering * concepts search * information retrieval Subject RIV: BB - Applied Statistics, Operational Research Impact factor: 2.769, year: 2007
Boolean network representation of contagion dynamics during a financial crisis
Caetano, Marco Antonio Leonel; Yoneyama, Takashi
2015-01-01
This work presents a network model for representation of the evolution of certain patterns of economic behavior. More specifically, after representing the agents as points in a space in which each dimension associated to a relevant economic variable, their relative "motions" that can be either stationary or discordant, are coded into a boolean network. Patterns with stationary averages indicate the maintenance of status quo, whereas discordant patterns represent aggregation of new agent into the cluster or departure from the former policies. The changing patterns can be embedded into a network representation, particularly using the concept of autocatalytic boolean networks. As a case study, the economic tendencies of the BRIC countries + Argentina were studied. Although Argentina is not included in the cluster formed by BRIC countries, it tends to follow the BRIC members because of strong commercial ties.
Algorithms for Finding Small Attractors in Boolean Networks
Hayashida Morihiro
2007-01-01
Full Text Available A Boolean network is a model used to study the interactions between different genes in genetic regulatory networks. In this paper, we present several algorithms using gene ordering and feedback vertex sets to identify singleton attractors and small attractors in Boolean networks. We analyze the average case time complexities of some of the proposed algorithms. For instance, it is shown that the outdegree-based ordering algorithm for finding singleton attractors works in time for , which is much faster than the naive time algorithm, where is the number of genes and is the maximum indegree. We performed extensive computational experiments on these algorithms, which resulted in good agreement with theoretical results. In contrast, we give a simple and complete proof for showing that finding an attractor with the shortest period is NP-hard.
Neural Network Boolean Factor Analysis and Applications
Húsek, Dušan; Frolov, A.; Polyakov, P.Y.; Snášel, V.
-: WSEAS Press, 2007 - (Katehakis, M.; And ina, D.; Mastorakis, M.), s. 30-35. (Electrical and Computer Engineering Series). ISBN 978-960-6766-21-3. [CIMMACS'07. WSEAS International Conference on Computational Intelligence, Man-Machine Systems and Cybernetics. Tenerife (ES), 14.12.2007-16.12.2007] R&D Projects: GA MŠk 1M0567; GA AV ČR 1ET100300414; GA ČR GA201/05/0079 Institutional research plan: CEZ:AV0Z10300504 Keywords : Hopfield neural network * boolean factor analysis * unsupervised learning * dimension reduction * data mining Subject RIV: BB - Applied Statistics, Operational Research
Solving the Satisfiability Problem Through Boolean Networks
Roli, Andrea; Milano, Michela
2011-01-01
In this paper we present a new approach to solve the satisfiability problem (SAT), based on boolean networks (BN). We define a mapping between a SAT instance and a BN, and we solve SAT problem by simulating the BN dynamics. We prove that BN fixed points correspond to the SAT solutions. The mapping presented allows to develop a new class of algorithms to solve SAT. Moreover, this new approach suggests new ways to combine symbolic and connectionist computation and provides a general framework f...
Solving the Satisfiability Problem Through Boolean Networks
Roli, Andrea
2011-01-01
In this paper we present a new approach to solve the satisfiability problem (SAT), based on boolean networks (BN). We define a mapping between a SAT instance and a BN, and we solve SAT problem by simulating the BN dynamics. We prove that BN fixed points correspond to the SAT solutions. The mapping presented allows to develop a new class of algorithms to solve SAT. Moreover, this new approach suggests new ways to combine symbolic and connectionist computation and provides a general framework for local search algorithms.
Densities of mixed volumes for Boolean models
Weil, Wolfgang
2001-01-01
In generalization of the well-known formulae for quermass densities of stationary and isotropic Boolean models, we prove corresponding results for densities of mixed volumes in the stationary situation and show how they can be used to determine the intensity of non-isotropic Boolean models Z in d-dimensional space for d = 2, 3, 4. We then consider non-stationary Boolean models and extend results of Fallert on quermass densities to densities of mixed volumes. In particular, we present explicit...
A more robust Boolean model describing inhibitor binding
Zhaoqian Steven XIE; Chao TANG
2008-01-01
From the first application of the Boolean model to the cell cycle regulation network of budding yeast, new regulative pathways have been discovered, par-ticularly in the G1/S transition circuit. This discovery called for finer modeling to study the essential biology, and the resulting outcomes are first introduced in the ar-ticle. A traditional Boolean network model set up for the new G1/S transition circuit shows that it cannot correctly simulate real biology unless the model parameters are fine tuned. The deficiency is caused by an overly coarse-grained description of the inhibitor binding process, which shall be overcome by a two-vector model proposed whose robustness is surveyed using random perturba-tions. Simulations show that the proposed two-vector model is much more robust in describing inhibitor binding processes within the Boolean framework.
ON REDUCED SCALAR EQUATIONS FOR SYNCHRONOUS BOOLEAN NETWORKS
Ali Muhammad Ali Rushdi; Adnan Ahmad Alsogati
2013-01-01
A total description of a synchronous Boolean network is typically achieved by a matrix recurrence relation. A simpler alternative is to use a scalar equation which is a possibly nonlinear equation that involves two or more instances of a single scalar variable and some Boolean operator(s). Further simplification is possible in terms of a linear reduced scalar equation which is the simplest two-term scalar equation that includes no Boolean operators and equates the value of a scalar variable a...
A SAT-based algorithm for finding attractors in synchronous Boolean networks.
Dubrova, Elena; Teslenko, Maxim
2011-01-01
This paper addresses the problem of finding attractors in synchronous Boolean networks. The existing Boolean decision diagram-based algorithms have limited capacity due to the excessive memory requirements of decision diagrams. The simulation-based algorithms can be applied to larger networks, however, they are incomplete. We present an algorithm, which uses a SAT-based bounded model checking to find all attractors in a Boolean network. The efficiency of the presented algorithm is evaluated by analyzing seven networks models of real biological processes, as well as 150,000 randomly generated Boolean networks of sizes between 100 and 7,000. The results show that our approach has a potential to handle an order of magnitude larger models than currently possible. PMID:21778527
Consistent stabilizability of switched Boolean networks.
Li, Haitao; Wang, Yuzhen
2013-10-01
This paper investigates the consistent stabilizability of switched Boolean networks (SBNs) by using the semi-tensor product method, and presents a number of new results. First, an algebraic expression of SBNs is obtained by the semi-tensor product, based on which the consistent stabilizability is then studied for SBNs and some necessary and sufficient conditions are presented for the design of free-form and state-feedback switching signals, respectively. Finally, the consistent stabilizability of SBNs with state constraints is considered and some necessary and sufficient conditions are proposed. The study of illustrative examples shows that the new results obtained in this paper are very effective in designing switching signals for the consistent stabilizability of SBNs. PMID:23787170
The value of less connected agents in Boolean networks
Epstein, Daniel; Bazzan, Ana L. C.
2013-11-01
In multiagent systems, agents often face binary decisions where one seeks to take either the minority or the majority side. Examples are minority and congestion games in general, i.e., situations that require coordination among the agents in order to depict efficient decisions. In minority games such as the El Farol Bar Problem, previous works have shown that agents may reach appropriate levels of coordination, mostly by looking at the history of past decisions. Not many works consider any kind of structure of the social network, i.e., how agents are connected. Moreover, when structure is indeed considered, it assumes some kind of random network with a given, fixed connectivity degree. The present paper departs from the conventional approach in some ways. First, it considers more realistic network topologies, based on preferential attachments. This is especially useful in social networks. Second, the formalism of random Boolean networks is used to help agents to make decisions given their attachments (for example acquaintances). This is coupled with a reinforcement learning mechanism that allows agents to select strategies that are locally and globally efficient. Third, we use agent-based modeling and simulation, a microscopic approach, which allows us to draw conclusions about individuals and/or classes of individuals. Finally, for the sake of illustration we use two different scenarios, namely the El Farol Bar Problem and a binary route choice scenario. With this approach we target systems that adapt dynamically to changes in the environment, including other adaptive decision-makers. Our results using preferential attachments and random Boolean networks are threefold. First we show that an efficient equilibrium can be achieved, provided agents do experimentation. Second, microscopic analysis show that influential agents tend to consider few inputs in their Boolean functions. Third, we have also conducted measurements related to network clustering and centrality
Self-organized networks of competing boolean agents
Paczuski; Bassler; Corral
2000-04-01
A model of Boolean agents competing in a market is presented where each agent bases his action on information obtained from a small group of other agents. The agents play a competitive game that rewards those in the minority. After a long time interval, the poorest player's strategy is changed randomly, and the process is repeated. Eventually the network evolves to a stationary but intermittent state where random mutation of the worst strategy can change the behavior of the entire network, often causing a switch in the dynamics between attractors of vastly different lengths. PMID:11019043
Towards a theory of modelling with Boolean automata networks - I. Theorisation and observations
Noual, Mathilde
2011-01-01
Although models are built on the basis of some observations of reality, the concepts that derive theoretically from their definitions as well as from their characteristics and properties are not necessarily direct consequences of these initial observations. Indeed, many of them rather follow from chains of theoretical inferences that are only based on the precise model definitions and rely strongly, in addition, on some consequential working hypotheses. Thus, it is important to address the question of which features of a model effectively carry some modelling meaning and which only result from the task of formalising observations of reality into a mathematical language. In this article, we address this question with a theoretical point view that sets our discussion strictly between the two stages of the modelling process that require knowledge of real systems, that is, between the initial stage that chooses a global theoretical framework to build the model and the final stage that exploits its formal predicti...
Propagation of external regulation and asynchronous dynamics in random Boolean networks
Mahmoudi, Hamed; Pagnani, Andrea; Weigt, Martin; Zecchina, Riccardo
2007-01-01
Boolean Networks and their dynamics are of great interest as abstract modeling schemes in various disciplines, ranging from biology to computer science. Whereas parallel update schemes have been studied extensively in past years, the level of understanding of asynchronous updates schemes is still very poor. In this paper we study the propagation of external information given by regulatory input variables into a random Boolean network. We compute both analytically and numerically the time evol...
Measuring Mutual Information in Random Boolean Networks
Luque, B; Luque, Bartolo; Ferrera, Antonio
1999-01-01
During the last few years an area of active research in the field of complex systems is that of their information storing and processing abilities. Common opinion has it that the most interesting beaviour of these systems is found ``at the edge of chaos'', which would seem to suggest that complex systems may have inherently non-trivial information proccesing abilities in the vicinity of sharp phase transitions. A comprenhensive, quantitative understanding of why this is the case is however still lacking. Indeed, even ``experimental'' (i.e., often numerical) evidence that this is so has been questioned for a number of systems. In this paper we will investigate, both numerically and analitically, the behavior of Random Boolean Networks (RBN's) as they undergo their order-disorder phase transition. We will use a simple mean field approximation to treat the problem, and without lack of generality we will concentrate on a particular value for the connectivity of the system. In spite of the simplicity of our argume...
Evolution and Controllability of Cancer Networks: A Boolean Perspective.
Srihari, Sriganesh; Raman, Venkatesh; Leong, Hon Wai; Ragan, Mark A
2014-01-01
Cancer forms a robust system capable of maintaining stable functioning (cell sustenance and proliferation) despite perturbations. Cancer progresses as stages over time typically with increasing aggressiveness and worsening prognosis. Characterizing these stages and identifying the genes driving transitions between them is critical to understand cancer progression and to develop effective anti-cancer therapies. In this work, we propose a novel model for the `cancer system' as a Boolean state space in which a Boolean network, built from protein-interaction and gene-expression data from different stages of cancer, transits between Boolean satisfiability states by "editing" interactions and "flipping" genes. Edits reflect rewiring of the PPI network while flipping of genes reflect activation or silencing of genes between stages. We formulate a minimization problem min flip to identify these genes driving the transitions. The application of our model (called BoolSpace) on three case studies-pancreatic and breast tumours in human and post spinal-cord injury (SCI) in rats-reveals valuable insights into the phenomenon of cancer progression: (i) interactions involved in core cell-cycle and DNA-damage repair pathways are significantly rewired in tumours, indicating significant impact to key genome-stabilizing mechanisms; (ii) several of the genes flipped are serine/threonine kinases which act as biological switches, reflecting cellular switching mechanisms between stages; and (iii) different sets of genes are flipped during the initial and final stages indicating a pattern to tumour progression. Based on these results, we hypothesize that robustness of cancer partly stems from "passing of the baton" between genes at different stages-genes from different biological processes and/or cellular components are involved in different stages of tumour progression thereby allowing tumour cells to evade targeted therapy, and therefore an effective therapy should target a "cover set" of
IMS Algorithm for Learning Representations in Boolean Neural Networks
Biswas, Nripendra N; Murthy, TVMK; Chandrasekhar, M.
1991-01-01
A new algorithm for learning representations in Boolean neural networks, where the inputs and outputs are binary bits, is presented. The algorithm has become feasible because of a newly discovered theorem which states that any non-linearly separable Boolean function can be expressed as a convergent series of linearly separable functions connected by the logical OR (+) and the logical INHIBIT (-) operators. The formation of the series is carried out by many important properties exhibited by th...
Polynomial-Time Algorithm for Controllability Test of a Class of Boolean Biological Networks
Koichi Kobayashi
2010-01-01
Full Text Available In recent years, Boolean-network-model-based approaches to dynamical analysis of complex biological networks such as gene regulatory networks have been extensively studied. One of the fundamental problems in control theory of such networks is the problem of determining whether a given substance quantity can be arbitrarily controlled by operating the other substance quantities, which we call the controllability problem. This paper proposes a polynomial-time algorithm for solving this problem. Although the algorithm is based on a sufficient condition for controllability, it is easily computable for a wider class of large-scale biological networks compared with the existing approaches. A key to this success in our approach is to give up computing Boolean operations in a rigorous way and to exploit an adjacency matrix of a directed graph induced by a Boolean network. By applying the proposed approach to a neurotransmitter signaling pathway, it is shown that it is effective.
Cho Kwang-Hyun; Choi Sun; Kwon Yung-Keun
2007-01-01
Abstract Background A number of studies on biological networks have been carried out to unravel the topological characteristics that can explain the functional importance of network nodes. For instance, connectivity, clustering coefficient, and shortest path length were previously proposed for this purpose. However, there is still a pressing need to investigate another topological measure that can better describe the functional importance of network nodes. In this respect, we considered a fee...
Simulating Quantitative Cellular Responses Using Asynchronous Threshold Boolean Network Ensembles
Shah Imran
2011-07-01
Full Text Available Abstract Background With increasing knowledge about the potential mechanisms underlying cellular functions, it is becoming feasible to predict the response of biological systems to genetic and environmental perturbations. Due to the lack of homogeneity in living tissues it is difficult to estimate the physiological effect of chemicals, including potential toxicity. Here we investigate a biologically motivated model for estimating tissue level responses by aggregating the behavior of a cell population. We assume that the molecular state of individual cells is independently governed by discrete non-deterministic signaling mechanisms. This results in noisy but highly reproducible aggregate level responses that are consistent with experimental data. Results We developed an asynchronous threshold Boolean network simulation algorithm to model signal transduction in a single cell, and then used an ensemble of these models to estimate the aggregate response across a cell population. Using published data, we derived a putative crosstalk network involving growth factors and cytokines - i.e., Epidermal Growth Factor, Insulin, Insulin like Growth Factor Type 1, and Tumor Necrosis Factor α - to describe early signaling events in cell proliferation signal transduction. Reproducibility of the modeling technique across ensembles of Boolean networks representing cell populations is investigated. Furthermore, we compare our simulation results to experimental observations of hepatocytes reported in the literature. Conclusion A systematic analysis of the results following differential stimulation of this model by growth factors and cytokines suggests that: (a using Boolean network ensembles with asynchronous updating provides biologically plausible noisy individual cellular responses with reproducible mean behavior for large cell populations, and (b with sufficient data our model can estimate the response to different concentrations of extracellular ligands. Our
Boolean modeling in systems biology: an overview of methodology and applications
Mathematical modeling of biological processes provides deep insights into complex cellular systems. While quantitative and continuous models such as differential equations have been widely used, their use is obstructed in systems wherein the knowledge of mechanistic details and kinetic parameters is scarce. On the other hand, a wealth of molecular level qualitative data on individual components and interactions can be obtained from the experimental literature and high-throughput technologies, making qualitative approaches such as Boolean network modeling extremely useful. In this paper, we build on our research to provide a methodology overview of Boolean modeling in systems biology, including Boolean dynamic modeling of cellular networks, attractor analysis of Boolean dynamic models, as well as inferring biological regulatory mechanisms from high-throughput data using Boolean models. We finally demonstrate how Boolean models can be applied to perform the structural analysis of cellular networks. This overview aims to acquaint life science researchers with the basic steps of Boolean modeling and its applications in several areas of systems biology. (paper)
Boolean Models of Biological Processes Explain Cascade-Like Behavior.
Chen, Hao; Wang, Guanyu; Simha, Rahul; Du, Chenghang; Zeng, Chen
2016-01-01
Biological networks play a key role in determining biological function and therefore, an understanding of their structure and dynamics is of central interest in systems biology. In Boolean models of such networks, the status of each molecule is either "on" or "off" and along with the molecules interact with each other, their individual status changes from "on" to "off" or vice-versa and the system of molecules in the network collectively go through a sequence of changes in state. This sequence of changes is termed a biological process. In this paper, we examine the common perception that events in biomolecular networks occur sequentially, in a cascade-like manner, and ask whether this is likely to be an inherent property. In further investigations of the budding and fission yeast cell-cycle, we identify two generic dynamical rules. A Boolean system that complies with these rules will automatically have a certain robustness. By considering the biological requirements in robustness and designability, we show that those Boolean dynamical systems, compared to an arbitrary dynamical system, statistically present the characteristics of cascadeness and sequentiality, as observed in the budding and fission yeast cell- cycle. These results suggest that cascade-like behavior might be an intrinsic property of biological processes. PMID:26821940
Binary higher order neural networks for realizing Boolean functions.
Zhang, Chao; Yang, Jie; Wu, Wei
2011-05-01
In order to more efficiently realize Boolean functions by using neural networks, we propose a binary product-unit neural network (BPUNN) and a binary π-ς neural network (BPSNN). The network weights can be determined by one-step training. It is shown that the addition " σ," the multiplication " π," and two kinds of special weighting operations in BPUNN and BPSNN can implement the logical operators " ∨," " ∧," and " ¬" on Boolean algebra 〈Z(2),∨,∧,¬,0,1〉 (Z(2)={0,1}), respectively. The proposed two neural networks enjoy the following advantages over the existing networks: 1) for a complete truth table of N variables with both truth and false assignments, the corresponding Boolean function can be realized by accordingly choosing a BPUNN or a BPSNN such that at most 2(N-1) hidden nodes are needed, while O(2(N)), precisely 2(N) or at most 2(N), hidden nodes are needed by existing networks; 2) a new network BPUPS based on a collaboration of BPUNN and BPSNN can be defined to deal with incomplete truth tables, while the existing networks can only deal with complete truth tables; and 3) the values of the weights are all simply -1 or 1, while the weights of all the existing networks are real numbers. Supporting numerical experiments are provided as well. Finally, we present the risk bounds of BPUNN, BPSNN, and BPUPS, and then analyze their probably approximately correct learnability. PMID:21427020
ON REDUCED SCALAR EQUATIONS FOR SYNCHRONOUS BOOLEAN NETWORKS
Ali Muhammad Ali Rushdi
2013-01-01
Full Text Available A total description of a synchronous Boolean network is typically achieved by a matrix recurrence relation. A simpler alternative is to use a scalar equation which is a possibly nonlinear equation that involves two or more instances of a single scalar variable and some Boolean operator(s. Further simplification is possible in terms of a linear reduced scalar equation which is the simplest two-term scalar equation that includes no Boolean operators and equates the value of a scalar variable at a latter instance t2 to its value at an earlier instance t1. This equation remains valid when the times t1 and t2 are both augmented by any integral multiple of the underlying time period. In other words, there are infinitely many versions of a reduced scalar equation, any of which is useful for deducing information about the cyclic behavior of the network. However, to obtain correct information about the transient behavior of the network, one must find the true reduced scalar equation for which instances t1 and t2 are minimal. This study investigates the nature, derivation and utilization of reduced scalar equations. It relies on Boolean-algebraic manipulations for the derivation of such equations and suggests that this derivation can be facilitated by seeking certain orthogonality relations among certain successive (albeit not necessarily consecutive instances of the same scalar variable. We demonstrate, contrary to previously published assumptions or assertions, that there is typically no common reduced scalar equation for all the scalar variables. Each variable usually satisfies its own distinct reduced scalar equation. We also demonstrate that the derivation of a reduced scalar equation is achieved not only by proving it but also by disproving an immediately preceding version of it when such a version might exist. We also demonstrate that, despite the useful insight supplied by the reduced scalar equations, they do not provide a total solution like the
Optimal Computation of Symmetric Boolean Functions in Collocated Networks
Kowshik, Hemant
2011-01-01
We consider collocated wireless sensor networks, where each node has a Boolean measurement and the goal is to compute a given Boolean function of these measurements. We first consider the worst case setting and study optimal block computation strategies for computing symmetric Boolean functions. We study three classes of functions: threshold functions, delta functions and interval functions. We provide exactly optimal strategies for the first two classes, and a scaling law order-optimal strategy with optimal preconstant for interval functions. We also extend the results to the case of integer measurements and certain integer-valued functions. We use lower bounds from communication complexity theory, and provide an achievable scheme using information theoretic tools. Next, we consider the case where nodes measurements are random and drawn from independent Bernoulli distributions. We address the problem of optimal function computation so as to minimize the expected total number of bits that are transmitted. In ...
Boolean Models of Biosurfactants Production in Pseudomonas fluorescens
Richard, Adrien; Rossignol, Gaelle; Comet, Jean-Paul; Bernot, Gilles; Guespin-Michel, Jannine; Merieau, Annabelle
2012-01-01
Cyclolipopeptides (CLPs) are biosurfactants produced by numerous Pseudomonas fluorescens strains. CLP production is known to be regulated at least by the GacA/GacS two-component pathway, but the full regulatory network is yet largely unknown. In the clinical strain MFN1032, CLP production is abolished by a mutation in the phospholipase C gene () and not restored by complementation. Their production is also subject to phenotypic variation. We used a modelling approach with Boolean networks, which takes into account all these observations concerning CLP production without any assumption on the topology of the considered network. Intensive computation yielded numerous models that satisfy these properties. All models minimizing the number of components point to a bistability in CLP production, which requires the presence of a yet unknown key self-inducible regulator. Furthermore, all suggest that a set of yet unexplained phenotypic variants might also be due to this epigenetic switch. The simplest of these Boolean networks was used to propose a biological regulatory network for CLP production. This modelling approach has allowed a possible regulation to be unravelled and an unusual behaviour of CLP production in P. fluorescens to be explained. PMID:22303435
Robust Boolean Operation for Sculptured Models
无
2000-01-01
To enhance the ability of current modeling system, an uniformed representation is designed to represent wire-frame, solid, surface models. We present an algorithm for Boolean operation between the models under this representation. Accuracy, efficiency and robustness are the main consideration. The geometric information is represented with trimmed parametric patches and trimmed parametric splines. The topological information is represented with an extended half-edge data structure. In the process of intersection calculation, hierarchy intersection method is applied for unified classification. Tracing the intersection curve to overcome degenerate cases that occur frequently in practice. The algorithm has been implemented as the modeling kernel of a feature based modeling system named GS-CAD98, which was developed on Windows/NT platform.
Comparison of Two Neural Networks Approaches to Boolean Matrix Factorization
Polyakov, P.Y.; Frolov, A. A.; Húsek, Dušan
Los Alamitos: IEEE Computer Society, 2009 - (Snášel, V.; Pokorný, J.; Pichappan, P.; El-Qawasmeh, E.), s. 316-321 ISBN 978-1-4244-4614-8. [NDT 2009. International Conference on Networked Digital Technologies /1./. Ostrava (CZ), 29.07.2009-31.07.2009] R&D Projects: GA ČR GA205/09/1079; GA MŠk(CZ) 1M0567 Institutional research plan: CEZ:AV0Z10300504 Keywords : data mining * artificial inteligence * neural networks * multivariate statistics * Boolean factor analysis * Hopfield-like neural networks * feed forward neural network Subject RIV: BB - Applied Statistics, Operational Research
Neural Network Based Boolean Factor Analysis of Parliament Voting
Frolov, A. A.; Polyakov, P.Y.; Húsek, Dušan; Řezanková, H.
Heidelberg : Springer, 2006 - (Rizzi, A.; Vichi, M.), s. 861-868 ISBN 3-7908-1708-2. [COMPSTAT 2006. Symposium /17./. Rome (IN), 28.08.2006-01.09.2006] R&D Projects: GA AV ČR 1ET100300419; GA ČR GA201/05/0079 Grant ostatní: RFBR(RU) 05-07-90049 Institutional research plan: CEZ:AV0Z10300504 Keywords : Boolean factor analysis * neural networks * social networks Subject RIV: BB - Applied Statistics, Operational Research
Chaos synchronization of two stochastically coupled random Boolean networks
Hung, Y.-C. [Department of Physics, National Sun Yat-sen University, Kaohsiung, Taiwan (China) and Nonlinear Science Group, Department of Physics, National Kaohsiung Normal University, Kaohsiung, Taiwan (China)]. E-mail: d9123801@student.nsysu.edu.tw; Ho, M.-C. [Nonlinear Science Group, Department of Physics, National Kaohsiung Normal University, Kaohsiung, Taiwan (China)]. E-mail: t1603@nknucc.nknu.edu.tw; Lih, J.-S. [Department of Physics and Geoscience, National Pingtung University of Education, Pingtung, Taiwan (China); Nonlinear Science Group, Department of Physics, National Kaohsiung Normal University, Kaohsiung, Taiwan (China); Jiang, I-M. [Department of Physics, National Sun Yat-sen University, Kaohsiung, Taiwan (China); Nonlinear Science Group, Department of Physics, National Kaohsiung Normal University, Kaohsiung, Taiwan (China)
2006-07-24
In this Letter, we study the chaos synchronization of two stochastically coupled random Boolean networks (RBNs). Instead of using the 'site-by-site and all-to-all' coupling, the coupling mechanism we consider here is that: the nth cell in a network is linked by an arbitrarily chosen cell in the other network with probability {rho}, and it possesses no links with probability 1-{rho}. The mechanism is useful to investigate the coevolution of biological species via horizontal genetic exchange. We show that the density evolution of networks can be described by two deterministic coupled polynomial maps. The complete synchronization occurs when the coupling parameter exceeds a critical value. Moreover, the reverse bifurcations in inhomogeneous condition are observed and under our discussion.
Evolution of a designless nanoparticle network into reconfigurable Boolean logic
Bose, S. K.; Lawrence, C. P.; Liu, Z.; Makarenko, K. S.; van Damme, R. M. J.; Broersma, H. J.; van der Wiel, W. G.
2015-12-01
Natural computers exploit the emergent properties and massive parallelism of interconnected networks of locally active components. Evolution has resulted in systems that compute quickly and that use energy efficiently, utilizing whatever physical properties are exploitable. Man-made computers, on the other hand, are based on circuits of functional units that follow given design rules. Hence, potentially exploitable physical processes, such as capacitive crosstalk, to solve a problem are left out. Until now, designless nanoscale networks of inanimate matter that exhibit robust computational functionality had not been realized. Here we artificially evolve the electrical properties of a disordered nanomaterials system (by optimizing the values of control voltages using a genetic algorithm) to perform computational tasks reconfigurably. We exploit the rich behaviour that emerges from interconnected metal nanoparticles, which act as strongly nonlinear single-electron transistors, and find that this nanoscale architecture can be configured in situ into any Boolean logic gate. This universal, reconfigurable gate would require about ten transistors in a conventional circuit. Our system meets the criteria for the physical realization of (cellular) neural networks: universality (arbitrary Boolean functions), compactness, robustness and evolvability, which implies scalability to perform more advanced tasks. Our evolutionary approach works around device-to-device variations and the accompanying uncertainties in performance. Moreover, it bears a great potential for more energy-efficient computation, and for solving problems that are very hard to tackle in conventional architectures.
Harmonic Analysis of Boolean Networks: Determinative Power and Perturbations
Heckel, Reinhard; Bossert, Martin
2011-01-01
Consider a large Boolean network with a feed forward structure. Given a probability distribution for the inputs, can one find-possibly small-collections of input nodes that determine the states of most other nodes in the network? To identify these nodes, a notion that quantifies the determinative power of an input over states in the network is needed. We argue that the mutual information (MI) between a subset of the inputs X = {X_1, ..., X_n} of node i and the function f_i(X)$ associated with node i quantifies the determinative power of this subset of inputs over node i. To study the relation of determinative power to sensitivity to perturbations, we relate the MI to measures of perturbations, such as the influence of a variable, in terms of inequalities. The result shows that, maybe surprisingly, an input that has large influence does not necessarily have large determinative power. The main tool for the analysis is Fourier analysis of Boolean functions. Whether a function is sensitive to perturbations or not...
Evolution of a designless nanoparticle network into reconfigurable Boolean logic.
Bose, S K; Lawrence, C P; Liu, Z; Makarenko, K S; van Damme, R M J; Broersma, H J; van der Wiel, W G
2015-12-01
Natural computers exploit the emergent properties and massive parallelism of interconnected networks of locally active components. Evolution has resulted in systems that compute quickly and that use energy efficiently, utilizing whatever physical properties are exploitable. Man-made computers, on the other hand, are based on circuits of functional units that follow given design rules. Hence, potentially exploitable physical processes, such as capacitive crosstalk, to solve a problem are left out. Until now, designless nanoscale networks of inanimate matter that exhibit robust computational functionality had not been realized. Here we artificially evolve the electrical properties of a disordered nanomaterials system (by optimizing the values of control voltages using a genetic algorithm) to perform computational tasks reconfigurably. We exploit the rich behaviour that emerges from interconnected metal nanoparticles, which act as strongly nonlinear single-electron transistors, and find that this nanoscale architecture can be configured in situ into any Boolean logic gate. This universal, reconfigurable gate would require about ten transistors in a conventional circuit. Our system meets the criteria for the physical realization of (cellular) neural networks: universality (arbitrary Boolean functions), compactness, robustness and evolvability, which implies scalability to perform more advanced tasks. Our evolutionary approach works around device-to-device variations and the accompanying uncertainties in performance. Moreover, it bears a great potential for more energy-efficient computation, and for solving problems that are very hard to tackle in conventional architectures. PMID:26389658
Coevolution of Information Processing and Topology in Hierarchical Adaptive Random Boolean Networks
Gorski, Piotr J; Holyst, Janusz A
2015-01-01
Random Boolean networks (RBNs) are frequently employed for modelling complex systems driven by information processing, e.g. for gene regulatory networks (GRNs). Here we propose a hierarchical adaptive RBN (HARBN) as a system consisting of distinct adaptive RBNs - subnetworks - connected by a set of permanent interlinks. Information measures and internal subnetworks topology of HARBN coevolve and reach steady-states that are specific for a given network structure. We investigate mean node information, mean edge information as well as a mean node degree as functions of model parameters and demonstrate HARBN's ability to describe complex hierarchical systems.
A Boolean Approach to Airline Business Model Innovation
Hvass, Kristian Anders
Research in business model innovation has identified its significance in creating a sustainable competitive advantage for a firm, yet there are few empirical studies identifying which combination of business model activities lead to success and therefore deserve innovative attention. This study...... analyzes the business models of North America low-cost carriers from 2001 to 2010 using a Boolean minimization algorithm to identify which combinations of business model activities lead to operational profitability. The research aim is threefold: complement airline literature in the realm of business model...... innovation, introduce Boolean minimization methods to the field, and propose alternative business model activities to North American carriers striving for positive operating results....
Detecting small attractors of large Boolean networks by function-reduction-based strategy.
Zheng, Qiben; Shen, Liangzhong; Shang, Xuequn; Liu, Wenbin
2016-04-01
Boolean networks (BNs) are widely used to model gene regulatory networks and to design therapeutic intervention strategies to affect the long-term behaviour of systems. A central aim of Boolean-network analysis is to find attractors that correspond to various cellular states, such as cell types or the stage of cell differentiation. This problem is NP-hard and various algorithms have been used to tackle it with considerable success. The idea is that a singleton attractor corresponds to n consistent subsequences in the truth table. To find these subsequences, the authors gradually reduce the entire truth table of Boolean functions by extending a partial gene activity profile (GAP). Not only does this process delete inconsistent subsequences in truth tables, it also directly determines values for some nodes not extended, which means it can abandon the partial GAPs that cannot lead to an attractor as early as possible. The results of simulation show that the proposed algorithm can detect small attractors with length p = 4 in BNs of up to 200 nodes with average indegree K = 2. PMID:26997659
Claudia Stötzel
Full Text Available In this paper, we present a systematic transition scheme for a large class of ordinary differential equations (ODEs into Boolean networks. Our transition scheme can be applied to any system of ODEs whose right hand sides can be written as sums and products of monotone functions. It performs an Euler-like step which uses the signs of the right hand sides to obtain the Boolean update functions for every variable of the corresponding discrete model. The discrete model can, on one hand, be considered as another representation of the biological system or, alternatively, it can be used to further the analysis of the original ODE model. Since the generic transformation method does not guarantee any property conservation, a subsequent validation step is required. Depending on the purpose of the model this step can be based on experimental data or ODE simulations and characteristics. Analysis of the resulting Boolean model, both on its own and in comparison with the ODE model, then allows to investigate system properties not accessible in a purely continuous setting. The method is exemplarily applied to a previously published model of the bovine estrous cycle, which leads to new insights regarding the regulation among the components, and also indicates strongly that the system is tailored to generate stable oscillations.
Algorithms and Complexity Analyses for Control of Singleton Attractors in Boolean Networks
Wai-Ki Ching
2008-09-01
Full Text Available A Boolean network (BN is a mathematical model of genetic networks. We propose several algorithms for control of singleton attractors in BN. We theoretically estimate the average-case time complexities of the proposed algorithms, and confirm them by computer experiments. The results suggest the importance of gene ordering. Especially, setting internal nodes ahead yields shorter computational time than setting external nodes ahead in various types of algorithms. We also present a heuristic algorithm which does not look for the optimal solution but for the solution whose computational time is shorter than that of the exact algorithms.
"Antelope": a hybrid-logic model checker for branching-time Boolean GRN analysis
Arellano Gustavo
2011-12-01
Full Text Available Abstract Background In Thomas' formalism for modeling gene regulatory networks (GRNs, branching time, where a state can have more than one possible future, plays a prominent role. By representing a certain degree of unpredictability, branching time can model several important phenomena, such as (a asynchrony, (b incompletely specified behavior, and (c interaction with the environment. Introducing more than one possible future for a state, however, creates a difficulty for ordinary simulators, because infinitely many paths may appear, limiting ordinary simulators to statistical conclusions. Model checkers for branching time, by contrast, are able to prove properties in the presence of infinitely many paths. Results We have developed Antelope ("Analysis of Networks through TEmporal-LOgic sPEcifications", http://turing.iimas.unam.mx:8080/AntelopeWEB/, a model checker for analyzing and constructing Boolean GRNs. Currently, software systems for Boolean GRNs use branching time almost exclusively for asynchrony. Antelope, by contrast, also uses branching time for incompletely specified behavior and environment interaction. We show the usefulness of modeling these two phenomena in the development of a Boolean GRN of the Arabidopsis thaliana root stem cell niche. There are two obstacles to a direct approach when applying model checking to Boolean GRN analysis. First, ordinary model checkers normally only verify whether or not a given set of model states has a given property. In comparison, a model checker for Boolean GRNs is preferable if it reports the set of states having a desired property. Second, for efficiency, the expressiveness of many model checkers is limited, resulting in the inability to express some interesting properties of Boolean GRNs. Antelope tries to overcome these two drawbacks: Apart from reporting the set of all states having a given property, our model checker can express, at the expense of efficiency, some properties that ordinary
Characterizing short-term stability for Boolean networks over any distribution of transfer functions
Seshadhri, C.; Smith, Andrew M.; Vorobeychik, Yevgeniy; Mayo, Jackson R.; Armstrong, Robert C.
2016-07-01
We present a characterization of short-term stability of Kauffman's N K (random) Boolean networks under arbitrary distributions of transfer functions. Given such a Boolean network where each transfer function is drawn from the same distribution, we present a formula that determines whether short-term chaos (damage spreading) will happen. Our main technical tool which enables the formal proof of this formula is the Fourier analysis of Boolean functions, which describes such functions as multilinear polynomials over the inputs. Numerical simulations on mixtures of threshold functions and nested canalyzing functions demonstrate the formula's correctness.
Critical line in undirected Kauffman Boolean networks - the role of percolation
We show that to describe correctly the position of the critical line in Kauffman random Boolean networks one must take into account percolation phenomena underlying the process of damage spreading. For this reason, since the issue of percolation transition is much simpler in random undirected networks than in the directed ones, we study the Kauffman model in undirected networks. We derive the mean field formula for the critical line in the giant components of these networks, and show that the critical line characterizing the whole network results from the fact that the ordered behavior of small clusters shields the chaotic behavior of the giant component. We also show a possible attitude towards the analytical description of the shielding effect. The theoretical derivations given in this paper very much tally with the numerical simulations done for classical random graphs
SAT-based Distributed Reactive Control Protocol Synthesis for Boolean Networks
Sahin, Yunus Emre; Ozay, Necmiye
2016-01-01
This paper considers the synthesis of distributed reactive control protocols for a Boolean network in a distributed manner. We start with a directed acyclic graph representing a network of Boolean subsystems and a global contract, given as an assumption-guarantee pair. Assumption captures the environment behavior, and guarantee is the requirements to be satisfied by the system. Local assumption-guarantee contracts, together with local control protocols ensuring these local contracts, are comp...
A Boolean Approach to Airline Business Model Innovation
Hvass, Kristian
2012-01-01
Research in business model innovation has identified its significance in creating a sustainable competitive advantage for a firm, yet there are few empirical studies identifying which combination of business model activities lead to success and therefore deserve innovative attention. This study analyzes the business models of North America low-cost carriers from 2001 to 2010 using a Boolean minimization algorithm to identify which combinations of business model activities le...
Damage spreading in spatial and small-world random boolean networks
Lu, Qiming [Los Alamos National Laboratory; Teuscher, Christof [Los Alamos National Laboratory
2008-01-01
Random Boolean Networks (RBNs) are often used as generic models for certain dynamics of complex systems, ranging from social networks, neural networks, to gene or protein interaction networks. Traditionally, RBNs are interconnected randomly and without considering any spatial arrangement of the links and nodes. However, most real-world networks are spatially extended and arranged with regular, small-world, or other non-random connections. Here we explore the RBN network topology between extreme local connections, random small-world, and random networks, and study the damage spreading with small perturbations. We find that spatially local connections change the scaling of the relevant component at very low connectivities ({bar K} << 1) and that the critical connectivity of stability K{sub s} changes compared to random networks. At higher {bar K}, this scaling remains unchanged. We also show that the relevant component of spatially local networks scales with a power-law as the system size N increases, but with a different exponent for local and small-world networks. The scaling behaviors are obtained by finite-size scaling. We further investigate the wiring cost of the networks. From an engineering perspective, our new findings provide the key trade-offs between damage spreading (robustness), the network wiring cost, and the network's communication characteristics.
Damage spreading in spatial and small-world random Boolean networks
Lu, Qiming; Teuscher, Christof
2014-02-01
The study of the response of complex dynamical social, biological, or technological networks to external perturbations has numerous applications. Random Boolean networks (RBNs) are commonly used as a simple generic model for certain dynamics of complex systems. Traditionally, RBNs are interconnected randomly and without considering any spatial extension and arrangement of the links and nodes. However, most real-world networks are spatially extended and arranged with regular, power-law, small-world, or other nonrandom connections. Here we explore the RBN network topology between extreme local connections, random small-world, and pure random networks, and study the damage spreading with small perturbations. We find that spatially local connections change the scaling of the Hamming distance at very low connectivities (K¯≪1) and that the critical connectivity of stability Ks changes compared to random networks. At higher K¯, this scaling remains unchanged. We also show that the Hamming distance of spatially local networks scales with a power law as the system size N increases, but with a different exponent for local and small-world networks. The scaling arguments for small-world networks are obtained with respect to the system sizes and strength of spatially local connections. We further investigate the wiring cost of the networks. From an engineering perspective, our new findings provide the key design trade-offs between damage spreading (robustness), the network's wiring cost, and the network's communication characteristics.
Boolean model of Yeast Apoptosis as a tool to study yeast and human apoptotic regulations
MarijaCvijovic
2012-12-01
Full Text Available Programmed cell death (PCD is an essential cellular mechanism that is evolutionary conserved, mediated through various pathways and acts by integrating different stimuli. Many diseases such as neurodegenerative diseases and cancers are found to be caused by, or associated with, regulations in the cell death pathways. Yeast Saccharomyces cerevisiae, is a unicellular eukaryotic organism that shares with human cells components and pathways of the PCD and is therefore used as a model organism. Boolean modelling is becoming promising approach to capture qualitative behaviour and describe essential properties of such complex networks. Here we present large literature-based and to our knowledge first Boolean model that combines pathways leading to apoptosis (a type of PCD in yeast. Analysis of the yeast model confirmed experimental findings of anti-apoptotic role of Bir1p and pro-apoptotic role of Stm1p and revealed activation of the stress protein kinase Hog proposing the maximal level of activation upon heat stress. In addition we extended the yeast model and created an in silico humanized yeast in which human pro- and anti-apoptotic regulators Bcl-2 family and Valosin-contain protein (VCP are included in the model. We showed that accumulation of Bax in in silico humanized yeast shows apoptotic markers and that VCP is essential target of Akt Signaling. The presented Boolean model provides comprehensive description of yeast apoptosis network behaviour. Extended model of humanized yeast gives new insights of how complex human disease like neurodegenration can initially be tested.
Damage Spreading in Spatial and Small-world Random Boolean Networks
Lu, Qiming [Fermilab; Teuscher, Christof [Portland State U.
2014-02-18
The study of the response of complex dynamical social, biological, or technological networks to external perturbations has numerous applications. Random Boolean Networks (RBNs) are commonly used a simple generic model for certain dynamics of complex systems. Traditionally, RBNs are interconnected randomly and without considering any spatial extension and arrangement of the links and nodes. However, most real-world networks are spatially extended and arranged with regular, power-law, small-world, or other non-random connections. Here we explore the RBN network topology between extreme local connections, random small-world, and pure random networks, and study the damage spreading with small perturbations. We find that spatially local connections change the scaling of the relevant component at very low connectivities ($\\bar{K} \\ll 1$) and that the critical connectivity of stability $K_s$ changes compared to random networks. At higher $\\bar{K}$, this scaling remains unchanged. We also show that the relevant component of spatially local networks scales with a power-law as the system size N increases, but with a different exponent for local and small-world networks. The scaling behaviors are obtained by finite-size scaling. We further investigate the wiring cost of the networks. From an engineering perspective, our new findings provide the key design trade-offs between damage spreading (robustness), the network's wiring cost, and the network's communication characteristics.
Decisional Processes with Boolean Neural Network: the Emergence of Mental Schemes
Barnabei, Graziano; Conversano, Ciro; Lensi, Elena
2010-01-01
Human decisional processes result from the employment of selected quantities of relevant information, generally synthesized from environmental incoming data and stored memories. Their main goal is the production of an appropriate and adaptive response to a cognitive or behavioral task. Different strategies of response production can be adopted, among which haphazard trials, formation of mental schemes and heuristics. In this paper, we propose a model of Boolean neural network that incorporates these strategies by recurring to global optimization strategies during the learning session. The model characterizes as well the passage from an unstructured/chaotic attractor neural network typical of data-driven processes to a faster one, forward-only and representative of schema-driven processes. Moreover, a simplified version of the Iowa Gambling Task (IGT) is introduced in order to test the model. Our results match with experimental data and point out some relevant knowledge coming from psychological domain.
Decisional Processes with Boolean Neural Network: The Emergence of Mental Schemes
Human decisional processes result from the employment of selected quantities of relevant information, generally synthesized from environmental incoming data and stored memories. Their main goal is the production of an appropriate and adaptive response to a cognitive or behavioral task. Different strategies of response production can be adopted, among which haphazard trials, formation of mental schemes and heuristics. In this paper, we propose a model of Boolean neural network that incorporates these strategies by recurring to global optimization strategies during the learning session. The model characterizes as well the passage from an unstructured/chaotic attractor neural network typical of data-driven processes to a faster one, forward-only and representative of schema-driven processes. Moreover, a simplified version of the Iowa Gambling Task (IGT) is introduced in order to test the model. Our results match with experimental data and point out some relevant knowledge coming from psychological domain. (authors)
MILES FORMULAE FOR BOOLEAN MODELS OBSERVED ON LATTICES
Joachim Ohser
2011-05-01
Full Text Available The densities of the intrinsic volumes – in 3D the volume density, surface density, the density of the integral of the mean curvature and the density of the Euler number – are a very useful collection of geometric characteristics of random sets. Combining integral and digital geometry we develop a method for efficient and simultaneous calculation of the intrinsic volumes of random sets observed in binary images in arbitrary dimensions. We consider isotropic and reflection invariant Boolean models sampled on homogeneous lattices and compute the expectations of the estimators of the intrinsic volumes. It turns out that the estimator for the surface density is proved to be asymptotically unbiased and thusmultigrid convergent for Boolean models with convex grains. The asymptotic bias of the estimators for the densities of the integral of the mean curvature and of the Euler number is assessed for Boolean models of balls of random diameters. Miles formulae with corresponding correction terms are derived for the 3D case.
Direct relations between morphology and transport in Boolean models.
Scholz, Christian; Wirner, Frank; Klatt, Michael A; Hirneise, Daniel; Schröder-Turk, Gerd E; Mecke, Klaus; Bechinger, Clemens
2015-10-01
We study the relation of permeability and morphology for porous structures composed of randomly placed overlapping circular or elliptical grains, so-called Boolean models. Microfluidic experiments and lattice Boltzmann simulations allow us to evaluate a power-law relation between the Euler characteristic of the conducting phase and its permeability. Moreover, this relation is so far only directly applicable to structures composed of overlapping grains where the grain density is known a priori. We develop a generalization to arbitrary structures modeled by Boolean models and characterized by Minkowski functionals. This generalization works well for the permeability of the void phase in systems with overlapping grains, but systematic deviations are found if the grain phase is transporting the fluid. In the latter case our analysis reveals a significant dependence on the spatial discretization of the porous structure, in particular the occurrence of single isolated pixels. To link the results to percolation theory we performed Monte Carlo simulations of the Euler characteristic of the open cluster, which reveals different regimes of applicability for our permeability-morphology relations close to and far away from the percolation threshold. PMID:26565348
Direct relations between morphology and transport in Boolean models
Scholz, Christian; Wirner, Frank; Klatt, Michael A.; Hirneise, Daniel; Schröder-Turk, Gerd E.; Mecke, Klaus; Bechinger, Clemens
2015-10-01
We study the relation of permeability and morphology for porous structures composed of randomly placed overlapping circular or elliptical grains, so-called Boolean models. Microfluidic experiments and lattice Boltzmann simulations allow us to evaluate a power-law relation between the Euler characteristic of the conducting phase and its permeability. Moreover, this relation is so far only directly applicable to structures composed of overlapping grains where the grain density is known a priori. We develop a generalization to arbitrary structures modeled by Boolean models and characterized by Minkowski functionals. This generalization works well for the permeability of the void phase in systems with overlapping grains, but systematic deviations are found if the grain phase is transporting the fluid. In the latter case our analysis reveals a significant dependence on the spatial discretization of the porous structure, in particular the occurrence of single isolated pixels. To link the results to percolation theory we performed Monte Carlo simulations of the Euler characteristic of the open cluster, which reveals different regimes of applicability for our permeability-morphology relations close to and far away from the percolation threshold.
Learning and Unlearning in Hopfield-Like Neural Network Performing Boolean Factor Analysis
Frolov, A. A.; Húsek, Dušan; Muraviev, I. P.; Polyakov, P.Y.
Berlin : Springer, 2010 - (Koronacki, J.; Ras, Z.; Wierzchon, S.; Kacprzyk, J.), s. 501-518 ISBN 978-3-642-05176-0. - (Studies in Computational Intelligence. 262) Institutional research plan: CEZ:AV0Z10300504 Keywords : Boolean factor analysis * Hopfield-like neural network * spurious attractors * statistics * bingy data Subject RIV: IN - Informatics, Computer Science
Analysis and control of Boolean networks a semi-tensor product approach
Cheng, Daizhan; Li, Zhiqiang
2010-01-01
This book presents a new approach to the investigation of Boolean control networks, using the semi-tensor product (STP), which can express a logical function as a conventional discrete-time linear system. This makes it possible to analyze basic control problems.
Lahoz-Beltra, R; Hameroff, S R; Dayhoff, J E
1993-01-01
Adaptive behaviors and dynamic activities within living cells are organized by the cytoskeleton: intracellular networks of interconnected protein polymers which include microtubules (MTs), actin, intermediate filaments, microtubule associated proteins (MAPs) and other protein structures. Cooperative interactions among cytoskeletal protein subunit conformational states have been used to model signal transmission and information processing. In the present work we present a theoretical model for molecular computing in which Boolean logic is implemented in parallel networks of individual MTs interconnected by MAPs. Conformational signals propagate on MTs as in data buses and in the model MAPs are considered as Boolean operators, either as bit-lines (like MTs) where a signal can be transported unchanged between MTs ('BUS-MAP'), or as bit-lines where a Boolean operation is performed in one of the two MAP-MT attachments ('LOGIC-MAP'). Three logic MAPs have been defined ('NOT-MAP, 'AND-MAP', 'XOR-MAP') and used to demonstrate addition, subtraction and other arithmetic operations. Although our choice of Boolean logic is arbitrary, the simulations demonstrate symbolic manipulation in a connectionist system and suggest that MT-MAP networks can perform computation in living cells and are candidates for future molecular computing devices. PMID:8318677
A Boolean delay equation model of ENSO variability
Saunders, Amira; Ghil, Michael
2001-12-01
Boolean delay equations (BDEs) provide a mathematical framework to formulate and analyze conceptual models of complex multi-component systems. This framework is used here to construct a simple conceptual model for the El-Niño/Southern Oscillation (ENSO) phenomenon. ENSO involves the coupling of atmospheric and oceanic processes that are far from being completely understood. Our BDE model uses Boolean variables to represent key atmospheric and oceanic quantities and equations that involve logical operators to describe their evolution. Two distinct time-delay parameters, one for the local atmosphere-ocean coupling effects and the other for oceanic wave propagation, are introduced. Over a range of physically relevant delay values, this truly minimal model captures two essential features of ENSO’s interannual variability - its regularity and its tendency to phase-lock to the annual cycle. Oscillations with average cycle length that is an integer multiple of the seasonal cycle are prevalent and range from 2 to 7 years. Transition zones - where the average period lengths are noninteger rational multiples of the forcing period - exhibit Devil’s staircases, a signature of the quasi-periodic (QP) route to chaos. Our BDE model thus validates results from previous studies of the interaction of the seasonal cycle with ENSO’s “delayed oscillator”. It gives therewith support to the view that the observed irregularity results predominantly from low-order chaotic processes rather than from stochastic weather noise. Moreover, in the transition zone between the two integer periodicities of 2 and 3 years, a heretofore unsuspected, self-similar “fractal sunburst” pattern emerges in phase-parameter space. This pattern provides a distinct and more complex scenario than the QP route to chaos found in earlier, more detailed ENSO models. Period selection in this 2-3-year transitional region seems to play a key role in ENSO’s irregularity, as well as in the appearance of
Combinatorics of Boolean automata circuits dynamics
Demongeot, Jacques; Noual, Mathilde; Sené, Sylvain
2012-01-01
International audience In line with fields of theoretical computer science and biology that study Boolean automata networks to model regulation networks, we present some results concerning the dynamics of networks whose underlying structures are oriented cycles, that is, Boolean automata circuits. In the context of biological regulation, former studies have highlighted the importance of circuits on the asymptotic dynamical behaviour of the biological networks that contain them. Our work fo...
Improving the User Query for the Boolean Model Using Genetic Algorithms
Nassar, Mohammad Othman; Mashagba, Eman Al
2011-01-01
The Use of genetic algorithms in the Information retrieval (IR) area, especially in optimizing a user query in Arabic data collections is presented in this paper. Very little research has been carried out on Arabic text collections. Boolean model have been used in this research. To optimize the query using GA we used different fitness functions, different mutation strategies to find which is the best strategy and fitness function that can be used with Boolean model when the data collection is the Arabic language. Our results show that the best GA strategy for the Boolean model is the GA (M2, Precision) method.
Improving the User Query for the Boolean Model UsingGenetic Algorithms
Mohammad Othman Nassar
2011-09-01
Full Text Available The Use of genetic algorithms in the Information retrieval (IR area, especially in optimizing a user query in Arabic data collections is presented in this paper. Very little research has been carried out on Arabic text collections. Boolean model have been used in this research. To optimize the query using GA we used different fitness functions, different mutation strategies to find which is the best strategy and fitness function that can be used with Boolean model when the data collection is the Arabic language. Our results show that the best GA strategy for the Boolean model is the GA (M2, Precision method.
Detecting a Singleton Attractor in a Boolean Network Utilizing SAT Algorithms
Tamura, Takeyuki; Akutsu, Tatsuya
The Boolean network (BN) is a mathematical model of genetic networks. It is known that detecting a singleton attractor, which is also called a fixed point, is NP-hard even for AND/OR BNs (i.e., BNs consisting of AND/OR nodes), where singleton attractors correspond to steady states. Though a naive algorithm can detect a singleton attractor for an AND/OR BN in O(n 2n) time, no O((2-ε)n) (ε > 0) time algorithm was known even for an AND/OR BN with non-restricted indegree, where n is the number of nodes in a BN. In this paper, we present an O(1.787n) time algorithm for detecting a singleton attractor of a given AND/OR BN, along with related results. We also show that detection of a singleton attractor in a BN with maximum indegree two is NP-hard and can be polynomially reduced to a satisfiability problem.
Boolean Modeling of Cellular and Molecular Pathways Involved in Influenza Infection
Christopher S. Anderson
2016-01-01
Full Text Available Systems virology integrates host-directed approaches with molecular profiling to understand viral pathogenesis. Self-contained statistical approaches that combine expression profiles of genes with the available databases defining the genes involved in the pathways (gene-sets have allowed characterization of predictive gene-signatures associated with outcome of the influenza virus (IV infection. However, such enrichment techniques do not take into account interactions among pathways that are responsible for the IV infection pathogenesis. We investigate dendritic cell response to seasonal H1N1 influenza A/New Caledonia/20/1999 (NC infection and infer the Boolean logic rules underlying the interaction network of ligand induced signaling pathways and transcription factors. The model reveals several novel regulatory modes and provides insights into mechanism of cross talk between NFκB and IRF mediated signaling. Additionally, the logic rule underlying the regulation of IL2 pathway that was predicted by the Boolean model was experimentally validated. Thus, the model developed in this paper integrates pathway analysis tools with the dynamic modeling approaches to reveal the regulation between signaling pathways and transcription factors using genome-wide transcriptional profiles measured upon influenza infection.
Random Boolean Networks and Attractors of their Intersecting Circuits
Demongeot, Jacques; Elena, Adrien; Noual, Mathilde; Sené, Sylvain
2011-01-01
International audience The multi-scale strategy in studying biological regulatory networks analysis is based on two level of analysis. The first level is structural and consists in examining the architecture of the interaction graph underlying the network and the second level is functional and analyse the regulatory properties of the network. We apply this dual approach to the "immunetworks" involved in the control of the immune system. As a result, we show that the small number of attract...
HSP70 mediates survival in apoptotic cells – Boolean network prediction and experimental validation
Suhas Vasaikar
2015-08-01
Full Text Available Neuronal stress or injury results in the activation of proteins, which regulate the balance between survival and apoptosis. However, the complex mechanism of cell signalling involving cell death and survival, activated in response to cellular stress is not yet completely understood. To bring more clarity about these mechanisms, a Boolean network was constructed that represented the apoptotic pathway in neuronal cells. FasL and neurotrophic growth factor (NGF were considered as inputs in the absence and presence of heat shock proteins known to shift the balance towards survival by rescuing pro-apoptotic cells. The probabilities of survival, DNA repair and apoptosis as cellular fates, in the presence of either the growth factor or FasL, revealed a survival bias encoded in the network. Boolean predictions tested by measuring the mRNA expression level of caspase-3, caspase-8 and BAX in neuronal Neuro2a (N2a cell line with NGF and FasL as external input, showed positive correlation with the observed experimental results for survival and apoptotic states. It was observed that HSP70 contributed more towards rescuing cells from apoptosis in comparison to HSP27, HSP40 and HSP90. Overexpression of HSP70 in N2a transfected cells showed reversal of cellular fate from FasL-induced apoptosis to survival. Further, the pro-survival role of the proteins BCL2, IAP, cFLIP and NFκB determined by vertex perturbation analysis was experimentally validated through protein inhibition experiments using EM20-25, Embelin and Wedelolactone, which resulted in 1.27-fold, 1.26-fold and 1.46-fold increase in apoptosis of N2a cells. The existence of a one-to-one correspondence between cellular fates and attractor states shows that Boolean networks may be employed with confidence in qualitative analytical studies of biological networks.
The behavior of noise-resilient Boolean networks with diverse topologies
The dynamics of noise-resilient Boolean networks with majority functions and diverse topologies is investigated. A wide class of possible topological configurations is parametrized as a stochastic blockmodel. For this class of networks, the dynamics always undergoes a phase transition from a non-ergodic regime, where a memory of its past states is preserved, to an ergodic regime, where no such memory exists and every microstate is equally probable. Both the average error on the network and the critical value of noise where the transition occurs are investigated analytically, and compared to numerical simulations. The results for 'partially dense' networks, comprising relatively few, but dynamically important nodes, which have a number of inputs that greatly exceeds the average for the entire network, give very general upper bounds on the maximum resilience against noise attainable on globally sparse systems
Variances as order parameter and complexity measure for random Boolean networks
Luque, Bartolo [Departamento de Matematica Aplicada y EstadIstica, Escuela Superior de Ingenieros Aeronauticos, Universidad Politecnica de Madrid, Plaza Cardenal Cisneros 3, Madrid 28040 (Spain); Ballesteros, Fernando J [Observatori Astronomic, Universitat de Valencia, Ed. Instituts d' Investigacio, Pol. La Coma s/n, E-46980 Paterna, Valencia (Spain); Fernandez, Manuel [Departamento de Matematica Aplicada y EstadIstica, Escuela Superior de Ingenieros Aeronauticos, Universidad Politecnica de Madrid, Plaza Cardenal Cisneros 3, Madrid 28040 (Spain)
2005-02-04
Several order parameters have been considered to predict and characterize the transition between ordered and disordered phases in random Boolean networks, such as the Hamming distance between replicas or the stable core, which have been successfully used. In this work, we propose a natural and clear new order parameter: the temporal variance. We compute its value analytically and compare it with the results of numerical experiments. Finally, we propose a complexity measure based on the compromise between temporal and spatial variances. This new order parameter and its related complexity measure can be easily applied to other complex systems.
Húsek, Dušan; Frolov, A. A.; Polyakov, P.Y.; Řezanková, H.; Snášel, V.
Lisabon : Instituto Nacional de Estatística, 2008 - (Gomes, M.; Pinto Martins, J.; Silva, J.), s. 3739-3742 ISBN 978-972-673-992-0. [ISI 2007. Session of the International Statistical Institute /56./. Lisboa (PT), 22.08.2007-29.08.2007] R&D Projects: GA AV ČR 1ET100300414 Grant ostatní: RFBR(RU) 05-07-90049 Institutional research plan: CEZ:AV0Z10300504 Keywords : Boolean factor analysis * document classification * automatic concepts search * unsupervised learning * neural network Subject RIV: BB - Applied Statistics, Operational Research
Neural Network Based Boolean Factor Analysis: Efficient Tool for Automated Topics Search.
Húsek, Dušan; Frolov, A. A.; Polyakov, P.Y.; Řezanková, H.
Amman: Applied Science Private University, 2006 - (Issa, G.; El-Qawasmeh, E.; Raho, G.), s. 321-327 ISBN 9957-8592-0-X. [CSIT 2006. International Multiconference on Computer Science and Information Technology /4./. Amman (JO), 05.04.2006-07.04.2006] R&D Projects: GA AV ČR 1ET100300419 Institutional research plan: CEZ:AV0Z10300504 Keywords : Boolean factor analysis * neural networks * associative memory * clustering * web searching * semantic web * information retrieval * document indexing * document classification * document processing * data mining * machine learning Subject RIV: BB - Applied Statistics, Operational Research
高阶布尔网络的结构%Structure of higher order Boolean networks*
李志强; 赵寅; 程代展
2011-01-01
The higher order Boolean (control) network is introduced and its topological structure is studied.Using semi-tensor product of matrices,its dynamics is converted into two algebraic forms,which are standard discrete-time dynamic systems.The one-to-one correspondence of the network dynamics and its first algebraic form is proved,and certain topological structures,including fixed points,cycles,and transient time,of higher order Boolean (control) networks are revealed.The relationship between the original system and its second algebraic form is also studied.%介绍高阶布尔（控制）网络,并研究了其拓扑结构.以矩阵的半张量积作为工具,把高阶布尔网络的动态过程转化为2种标准离散事件动态系统的代数形式.证明了高阶布尔网络和第1代数形式的一一对应关系,并由此得到其拓扑结构（不动点、极限圈以及暂态期等）.还研究了高阶布尔网络系统与它第2代数形式的关系.
Lovrics, Anna
2014-11-14
We have assembled a network of cell-fate determining transcription factors that play a key role in the specification of the ventral neuronal subtypes of the spinal cord on the basis of published transcriptional interactions. Asynchronous Boolean modelling of the network was used to compare simulation results with reported experimental observations. Such comparison highlighted the need to include additional regulatory connections in order to obtain the fixed point attractors of the model associated with the five known progenitor cell types located in the ventral spinal cord. The revised gene regulatory network reproduced previously observed cell state switches between progenitor cells observed in knock-out animal models or in experiments where the transcription factors were overexpressed. Furthermore the network predicted the inhibition of Irx3 by Nkx2.2 and this prediction was tested experimentally. Our results provide evidence for the existence of an as yet undescribed inhibitory connection which could potentially have significance beyond the ventral spinal cord. The work presented in this paper demonstrates the strength of Boolean modelling for identifying gene regulatory networks.
Local digital estimators of intrinsic volumes for Boolean models and in the design based setting
Svane, Anne Marie
In order to estimate the specific intrinsic volumes of a planar Boolean model from a binary image, we consider local digital algorithms based on weigted sums of 2×2 configuration counts. For Boolean models with balls as grains, explicit formulas for the bias of such algorithms are derived......, resulting in a set of linear equations that the weights must satisfy in order to minimize the bias in high resolution. These results generalize to larger classes of random sets, as well as to the design based situation, where a fixed set is observed on a stationary isotropic lattice. Finally, the formulas...... for the bias obtained for Boolean models are applied to existing algorithms in order to compare their accuracy....
On the number of attractors of Boolean automata circuits
Demongeot, Jacques; Noual, Mathilde; Sené, Sylvain
2009-01-01
In line with fields of theoretical computer science and biology that study Boolean automata networks often seen as models of regulation networks, we present some results concerning the dynamics of networks whose underlying interaction graphs are circuits, that is Boolean automata circuits. In the context of biological regulation, former studies have highlighted the importance of circuits on the asymptotic dynamical behaviour of the biological networks that contain them. Our work focuses on th...
Attractor Neural Network Combined with Likelihood Maximization Algorithm for Boolean Factor Analysis
Frolov, A.; Húsek, Dušan; Polyakov, P.Y.
Vol. 1. Berlin: Springer, 2012 - (Wang, J.; Yen, G.; Polycarpou, M.), s. 1-10. (Lecture Notes in Computer Science. 7367). ISBN 978-3-642-31345-5. ISSN 0302-9743. [ISNN 2012. International Symposium on Neural Networks /9./. Shenyang (CN), 11.07.2012-14.07.2012] R&D Projects: GA ČR GAP202/10/0262 Grant ostatní: GA MŠk(CZ) ED1.1.00/02.0070 Institutional research plan: CEZ:AV0Z10300504 Keywords : Associative Neural Network * Likelihood Maximization * Boolean Factor Analysis * Binary Matrix factorization * Noise XOR Mixing * Plato Problem * Information Gain * Bars problem * Data Mining * Dimension Reduction * Hebbian Learning * Anti-Hebbian Learning Subject RIV: IN - Informatics, Computer Science
Boolean nested canalizing functions: a comprehensive analysis
Li, Yuan; Murrugarra, David; Aguilar, Boris; Laubenbacher, Reinhard
2012-01-01
Boolean network models of molecular regulatory networks have been used successfully in computational systems biology. The Boolean functions that appear in published models tend to have special properties, in particular the property of being nested canalizing, a property inspired by the concept of canalization in evolutionary biology. It has been shown that networks comprised of nested canalizing functions have dynamic properties that make them suitable for modeling molecular regulatory networks, namely a small number of (large) attractors, as well as relatively short limit cycles. This paper contains a detailed analysis of this class of functions, based on a novel normal form as polynomial functions over the Boolean field. The concept of layer is introduced that stratifies variables into different classes depending on their level of dominance. Using this layer concept a closed form formula is derived for the number of nested canalizing functions with a given number of variables. Additional metrics analyzed in...
Application of fuzzy logic to Boolean models for digital soil assessment
Gruijter, de J.J.; Walvoort, D.J.J.; Bragato, G.
2011-01-01
Boolean models based on expert knowledge are often used to classify soils into a limited number of classes of a difficult-to-measure soil attribute. Although the primary data used for these classifications contain information on whether the soil is a typical class member or a boundary case between t
Applying Boolean discrete methods in the production of a real-valued probabilistic programming model
Nix, Jonathan Darren
2016-01-01
In this paper we explore the application of some notable Boolean methods, namely the Disjunctive Normal Form representation of logic table expansions, and apply them to a real-valued logic model which utilizes quantities on the range [0,1] to produce a probabilistic programming of a game character's logic in mathematical form.
On a Boolean-valued Model of the Strict Implication System(Continuous)
LI Na; LIU Hua-ke
2004-01-01
The reference [4] proved the consistency of S 1 and S 2 among Lewis'five strict implicationsystems in the modal logic by using the method of the Boolean-valued model. But, in this method, the consistency of S 3 , S 4 and S 5 in Lewis'five strictimplication systems is not decided. This paper makes use of the properties : (1) the equivalence of the modal systems S 3 andP 3 , S 4 and P 4 ; (2) the modal systems P 3 and P 4 all contained the modal axiom T(□p) ; (3) the modal axiom T is correspondence to the reflexiveproperty in VB . Hence, the paper proves: (a) |A S 31|=1 ; (b) |A S 41|=1 ;(c) |A S 51|=1 in the model (where B is a complete Boolean algebra, R is reflexive property in VB ). Therefore, the paper finallyproves that the Boolean-valued model VB of the ZFC axiomsystem in set theory is also a Boolean-valued model of Lewis'the strict implication system S 3 , S 4 and S 5 .
Yih-Lon Lin
2013-01-01
Full Text Available If the given Boolean function is linearly separable, a robust uncoupled cellular neural network can be designed as a maximal margin classifier. On the other hand, if the given Boolean function is linearly separable but has a small geometric margin or it is not linearly separable, a popular approach is to find a sequence of robust uncoupled cellular neural networks implementing the given Boolean function. In the past research works using this approach, the control template parameters and thresholds are restricted to assume only a given finite set of integers, and this is certainly unnecessary for the template design. In this study, we try to remove this restriction. Minterm- and maxterm-based decomposition algorithms utilizing the soft margin and maximal margin support vector classifiers are proposed to design a sequence of robust templates implementing an arbitrary Boolean function. Several illustrative examples are simulated to demonstrate the efficiency of the proposed method by comparing our results with those produced by other decomposition methods with restricted weights.
Strahler, Alan H.; Jupp, David L. B.
1990-01-01
Geometric-optical discrete-element mathematical models for forest canopies have been developed using the Boolean logic and models of Serra. The geometric-optical approach is considered to be particularly well suited to describing the bidirectional reflectance of forest woodland canopies, where the concentration of leaf material within crowns and the resulting between-tree gaps make plane-parallel, radiative-transfer models inappropriate. The approach leads to invertible formulations, in which the spatial and directional variance provides the means for remote estimation of tree crown size, shape, and total cover from remotedly sensed imagery.
Stratification and enumeration of Boolean functions by canalizing depth
He, Qijun; Macauley, Matthew
2016-01-01
Boolean network models have gained popularity in computational systems biology over the last dozen years. Many of these networks use canalizing Boolean functions, which has led to increased interest in the study of these functions. The canalizing depth of a function describes how many canalizing variables can be recursively "picked off", until a non-canalizing function remains. In this paper, we show how every Boolean function has a unique algebraic form involving extended monomial layers and a well-defined core polynomial. This generalizes recent work on the algebraic structure of nested canalizing functions, and it yields a stratification of all Boolean functions by their canalizing depth. As a result, we obtain closed formulas for the number of n-variable Boolean functions with depth k, which simultaneously generalizes enumeration formulas for canalizing, and nested canalizing functions.
Stratification and enumeration of Boolean functions by canalizing depth
He, Qijun
2015-01-01
Boolean network models have gained popularity in computational systems biology over the last dozen years. Many of these networks use canalizing Boolean functions, which has led to increased interest in the study of these functions. The canalizing depth of a function describes how many canalizing variables can be recursively picked off, until a non-canalizing function remains. In this paper, we show how every Boolean function has a unique algebraic form involving extended monomial layers and a well-defined core polynomial. This generalizes recent work on the algebraic structure of nested canalizing functions, and it yields a stratification of all Boolean functions by their canalizing depth. As a result, we obtain closed formulas for the number of n-variable Boolean functions with depth k, which simultaneously generalizes enumeration formulas for canalizing, and nested canalizing functions.
Hu, Mingxiao; Shen, Liangzhong; Zan, Xiangzhen; Shang, Xuequn; Liu, Wenbin
2016-01-01
Boolean networks are widely used to model gene regulatory networks and to design therapeutic intervention strategies to affect the long-term behavior of systems. In this paper, we investigate the less-studied one-bit perturbation, which falls under the category of structural intervention. Previous works focused on finding the optimal one-bit perturbation to maximally alter the steady-state distribution (SSD) of undesirable states through matrix perturbation theory. However, the application of the SSD is limited to Boolean networks with about ten genes. In 2007, Xiao et al. proposed to search the optimal one-bit perturbation by altering the sizes of the basin of attractions (BOAs). However, their algorithm requires close observation of the state-transition diagram. In this paper, we propose an algorithm that efficiently determines the BOA size after a perturbation. Our idea is that, if we construct the basin of states for all states, then the size of the BOA of perturbed networks can be obtained just by updating the paths of the states whose transitions have been affected. Results from both synthetic and real biological networks show that the proposed algorithm performs better than the exhaustive SSD-based algorithm and can be applied to networks with about 25 genes. PMID:27196530
Boolean modeling of neural systems with point-process inputs and outputs.
Marmarelis, Vasilis Z; Zanos, Theodoros P; Courellis, Spiros H; Berger, Theodore W
2006-01-01
This paper presents a novel modeling approach for neural systems with point-process inputs and outputs (binary time-series of 0's and 1's) that utilizes Boolean operators of modulo-2 multiplication and addition, corresponding to the logical AND and OR operations respectively. The form of the employed mathematical model is akin to a "Boolean-Volterra" model that contains the product terms of all relevant input lags in a hierarchical order, where terms of order higher than first represent nonlinear interactions among the various lagged values of each input point-process or among lagged values of various inputs (if multiple inputs exist) as they reflect on the output. The coefficients of this Boolean model are also binary variables that indicate the presence or absence of the respective term in each specific model/system. Simulations are used to explore the properties of such models and the feasibility of accurate estimation of such models from short data-records in the presence of noise (i.e. spurious spikes). The results demonstrate the feasibility of obtaining reliable estimates of such models, even in the presence of considerable noise in the input and/or output, thus making the proposed approach an attractive candidate for modeling neural systems in a practical context. PMID:17946091
Modeling boolean decision rules applied to multiple-observer decision strategies.
Maguire, W
1996-01-01
A model that derives multiple-observer decision strategy ROC curves for boolean decision rules applied to binary decisions of two or three observers is presented. It is assumed that covert decision variables consistent with ROC models of observer performance underlie decisions and that readers' decision criteria are in a fixed relationship. The specific parameters of individual ROC curves and the correlational structure that describes interobserver agreement have dramatic effects upon the relative benefits to be derived from different boolean strategies. A common strategy employed in clinical practice, in which the overall decision is positive if any observer makes a positive decision, is most effective when the readers are of similar ability, when they adopt similar decision criteria, when interreader agreement is greater for negative than for positive cases, and when the individual ROC slope is observer decision strategies can be evaluated using the model equations. A bootstrap method for testing model-associated hypotheses is described. PMID:8717599
Zhu, Zheng; Andresen, Juan Carlos; Moore, M A; Katzgraber, Helmut G
2014-02-01
We study the equilibrium and nonequilibrium properties of Boolean decision problems with competing interactions on scale-free networks in an external bias (magnetic field). Previous studies at zero field have shown a remarkable equilibrium stability of Boolean variables (Ising spins) with competing interactions (spin glasses) on scale-free networks. When the exponent that describes the power-law decay of the connectivity of the network is strictly larger than 3, the system undergoes a spin-glass transition. However, when the exponent is equal to or less than 3, the glass phase is stable for all temperatures. First, we perform finite-temperature Monte Carlo simulations in a field to test the robustness of the spin-glass phase and show that the system has a spin-glass phase in a field, i.e., exhibits a de Almeida-Thouless line. Furthermore, we study avalanche distributions when the system is driven by a field at zero temperature to test if the system displays self-organized criticality. Numerical results suggest that avalanches (damage) can spread across the whole system with nonzero probability when the decay exponent of the interaction degree is less than or equal to 2, i.e., that Boolean decision problems on scale-free networks with competing interactions can be fragile when not in thermal equilibrium. PMID:25353433
Frolov, A. A.; Húsek, Dušan; Muraviev, I. P.; Polyakov, P.Y.
2010-01-01
Roč. 73, č. 7-9 (2010), s. 1394-1404. ISSN 0925-2312 R&D Projects: GA ČR GA205/09/1079; GA MŠk(CZ) 1M0567 Institutional research plan: CEZ:AV0Z10300504 Keywords : Boolean factor analysis * Hopfield neural Network * unsupervised learning * dimension reduction * data mining Subject RIV: IN - Informatics, Computer Science Impact factor: 1.429, year: 2010
PARAMETER ESTIMATION IN NON-HOMOGENEOUS BOOLEAN MODELS: AN APPLICATION TO PLANT DEFENSE RESPONSE
Maria Angeles Gallego
2014-11-01
Full Text Available Many medical and biological problems require to extract information from microscopical images. Boolean models have been extensively used to analyze binary images of random clumps in many scientific fields. In this paper, a particular type of Boolean model with an underlying non-stationary point process is considered. The intensity of the underlying point process is formulated as a fixed function of the distance to a region of interest. A method to estimate the parameters of this Boolean model is introduced, and its performance is checked in two different settings. Firstly, a comparative study with other existent methods is done using simulated data. Secondly, the method is applied to analyze the longleaf data set, which is a very popular data set in the context of point processes included in the R package spatstat. Obtained results show that the new method provides as accurate estimates as those obtained with more complex methods developed for the general case. Finally, to illustrate the application of this model and this method, a particular type of phytopathological images are analyzed. These images show callose depositions in leaves of Arabidopsis plants. The analysis of callose depositions, is very popular in the phytopathological literature to quantify activity of plant immunity.
Computational complexity of Boolean functions
Boolean functions are among the fundamental objects of discrete mathematics, especially in those of its subdisciplines which fall under mathematical logic and mathematical cybernetics. The language of Boolean functions is convenient for describing the operation of many discrete systems such as contact networks, Boolean circuits, branching programs, and some others. An important parameter of discrete systems of this kind is their complexity. This characteristic has been actively investigated starting from Shannon's works. There is a large body of scientific literature presenting many fundamental results. The purpose of this survey is to give an account of the main results over the last sixty years related to the complexity of computation (realization) of Boolean functions by contact networks, Boolean circuits, and Boolean circuits without branching. Bibliography: 165 titles.
Techniques for solving Boolean equation systems
Keinänen, Misa
2006-01-01
Boolean equation systems are ordered sequences of Boolean equations decorated with least and greatest fixpoint operators. Boolean equation systems provide a useful framework for formal verification because various specification and verification problems, for instance, μ-calculus model checking can be represented as the problem of solving Boolean equation systems. The general problem of solving a Boolean equation system is a computationally hard task, and no polynomial time solution technique ...
Parameter Learning of Boolean Bayesian Networks%布尔型贝叶斯网络参数学习
吴永广; 周兴旺
2015-01-01
布尔型贝叶斯网络是一类由布尔型变量组成的网络，它能够以线性多变量函数描述，使计算和处理上灵活高效。通过运用连接树算法对络进行分块化处理的方法，可以提高算法的效率，然后以传统的最大似然估计方法对布尔型网络的参数进行学习。服从同一分布律的贝叶斯网络参数学习算法发展比较成熟，这类以狄利克雷或者高斯分布为基础的算法在应用领域中难以发挥其应有的价值。相比之下，基于布尔型贝叶斯网络下的参数学习更贴近于应用，在人工智能和数据挖掘等领域有很好的发展前景。%Boolean Bayesian network is a class of Bayesian networks which are made up of Boolean varia-bles. The method to describe the network with a multi-linear function is flexible and efficient to compute and process variables. By introducing Junction Tree algorithm,the network can be divided into blocks which can make it easy to calculate. Then the traditional maximum likelihood estimation method was used for learning Boolean networks. Parameter learning algorithm following the same distribution is more ma-ture,but this kind of algorithm based on Dirichlet or Gaussian distribution is difficult to play its proper val-ue in practice. In contrast,parameter learning based on Boolean networks gets close to applications. It has good prospects for development in areas such as artificial intelligence and data mining.
A Boolean Analysis Predicting Industry Change: Innovation, Imitation & Business Models
Hvass, Kristian Anders
2008-01-01
The deregulated scheduled passenger airline industry is in a constant state of motion as managers continually adapt their business models to meet the challenging market environment. Such adaptation has led to a variety of airlines populating the industry; from the birth of low-cost carriers to the transformation of state-owned behemoths to lean and successful carriers. These dynamics challenge airline managers to continuously acclimate their business models and to understand industry evolu...
On the Number of Attractors of Positive and Negative Boolean Automata Circuits.
Demongeot, Jacques; Noual, Mathilde; Sené, Sylvain
2010-01-01
International audience In line with fields of theoretical computer science and biology that study Boolean automata networks often seen as models of regulation networks, we present some results concerning the dynamics of networks whose underlying interaction graphs are circuits, that is, Boolean automata circuits. In the context of biological regulation, former studies have highlighted the importance of circuits on the asymptotic dynamical behaviour of the biological networks that contain t...
Húsek, Dušan; Moravec, P.; Snášel, V.; Frolov, A.; Řezanková, H.; Polyakov, P.Y.
Berlin : Springer, 2007 - (Ghosh, A.; De, R.), s. 235-243 ISBN 978-3-540-77045-9. - (Lecture Notes in Computer Science. 4815). [PReMI 2007. International Conference /2./. Kolkata (IN), 18.12.2007-22.12.2007] R&D Projects: GA MŠk(CZ) 1M0567; GA AV ČR 1ET100300419 Institutional research plan: CEZ:AV0Z10300504 Keywords : Boolean factor analysis * neural network * dimension reduction * cluster analysis Subject RIV: BB - Applied Statistics, Operational Research
Boolean implication networks derived from large scale, whole genome microarray datasets
Sahoo, Debashis; Dill, David L.; Gentles, Andrew J.; Tibshirani, Robert; Plevritis, Sylvia K.
2008-01-01
We describe a method for extracting Boolean implications (if-then relationships) in very large amounts of gene expression microarray data. A meta-analysis of data from thousands of microarrays for humans, mice, and fruit flies finds millions of implication relationships between genes that would be missed by other methods. These relationships capture gender differences, tissue differences, development, and differentiation. New relationships are discovered that are preserved across all three sp...
A solution to the surface intersection problem. [Boolean functions in geometric modeling
Timer, H. G.
1977-01-01
An application-independent geometric model within a data base framework should support the use of Boolean operators which allow the user to construct a complex model by appropriately combining a series of simple models. The use of these operators leads to the concept of implicitly and explicitly defined surfaces. With an explicitly defined model, the surface area may be computed by simply summing the surface areas of the bounding surfaces. For an implicitly defined model, the surface area computation must deal with active and inactive regions. Because the surface intersection problem involves four unknowns and its solution is a space curve, the parametric coordinates of each surface must be determined as a function of the arc length. Various subproblems involved in the general intersection problem are discussed, and the mathematical basis for their solution is presented along with a program written in FORTRAN IV for implementation on the IBM 370 TSO system.
Boolean Differential Operators
Catumba, Jorge; Diaz, Rafael
2012-01-01
We consider four combinatorial interpretations for the algebra of Boolean differential operators. We show that each interpretation yields an explicit matrix representation for Boolean differential operators.
Marmarelis, Vasilis Z; Zanos, Theodoros P; Berger, Theodore W
2009-08-01
This paper presents a new modeling approach for neural systems with point-process (spike) inputs and outputs that utilizes Boolean operators (i.e. modulo 2 multiplication and addition that correspond to the logical AND and OR operations respectively, as well as the AND_NOT logical operation representing inhibitory effects). The form of the employed mathematical models is akin to a "Boolean-Volterra" model that contains the product terms of all relevant input lags in a hierarchical order, where terms of order higher than first represent nonlinear interactions among the various lagged values of each input point-process or among lagged values of various inputs (if multiple inputs exist) as they reflect on the output. The coefficients of this Boolean-Volterra model are also binary variables that indicate the presence or absence of the respective term in each specific model/system. Simulations are used to explore the properties of such models and the feasibility of their accurate estimation from short data-records in the presence of noise (i.e. spurious spikes). The results demonstrate the feasibility of obtaining reliable estimates of such models, with excitatory and inhibitory terms, in the presence of considerable noise (spurious spikes) in the outputs and/or the inputs in a computationally efficient manner. A pilot application of this approach to an actual neural system is presented in the companion paper (Part II). PMID:19517238
Memory-Based Boolean Game and Self-Organized Phenomena on Networks
HUANG Zi-Gang; WU Zhi-Xi; GUAN Jian-Yue; WANG Ying-Hai
2006-01-01
@@ We study a memory-based Boolean game (MBBG) taking place on a regular ring, wherein each agent acts according to its local optimal states of the last M time steps recorded in memory, and the agents in the minority are rewarded. One free parameter p between 0 and 1 is introduced to denote the strength of the agent willing to make a decision according to its memory. It is found that giving proper willing strength p, the MBBG system can spontaneously evolve to a state of performance better than the random game; while for larger p, the herd behaviour emerges to reduce the system profit. By analysing the dependence of dynamics of the system on the memory capacity M, we find that a higher memory capacity favours the emergence of the better performance state, and effectively restrains the herd behaviour, thus increases the system profit. Considering the high cost of long-time memory, the enhancement of memory capacity for restraining the herd behaviour is also discussed,and M = 5 is suggested to be a good choice.
Boolean operations of STL models based on edge-facet intersection
无
2007-01-01
For the data processing of the Rapid Prototyping Manufacturing, Boolean operation can offer a versatile tool for editing or modifying the STL model, adding the artificial construction, and creating the complex assistant support structure to meet the special technical requests. The topological structure of STL models was built firstly in order to obtain the neighborhood relationship among the triangular facets. The intersection test between every edge of one solid and every facet of another solid Was taken to get the intersection points. According to the matching relationship of the triangle index recorded in the data structure of the intersection points, the intersection segments array and the intersection loop were traced out. Each intersected triangle was subdivided by the Constrained Delaunay Triangulations. The intersected surfaces were divided into several surface patches along the intersection loops. The inclusion prediction between the surface patch and the other solid was taken by testing whether the candidate point Was inside or outside the solid region of the slice. Detecting the loops for determination of the valid intersection lines greatly increases the efficiency and the reliability of the process.
Max Billib
2011-12-01
Full Text Available With population increase, lack of conventional fresh water resources and uncertainties due to climate change, there is growing interest in the arid and semi-arid areas to increase groundwater recharge with recycled water. Finding the best locations for artificial recharge of groundwater in such areas is one of the most crucial design steps to guarantee the long life and the sustainability of these projects. This study presents two ways to go about performing analysis; creating a suitability map to find out the suitability of every location on the map and another way is querying the created data sets to obtain a Boolean result of true or false map. These techniques have been applied on Sadat Industrial City which is located in a semi arid area in the western desert fringes of The Nile delta in the north west of Egypt. Thematic layers for number of parameters were prepared from some maps and satellite images and they have been classified, weighted and integrated in ArcGIS environment. By the means of the overlay weighted model in ArcGIS a suitability map which is classified into number of priority zones was obtained and it could be compared with the obtained true-false map of Boolean logic. Both methods suggested mostly the northern parts of the city for groundwater recharge; however the weighted model could give more accurate suitability map while Boolean logic suggested wider ranges of areas. This study recommends Boolean logic as a first estimator for locating the best locations as it is easier and not time consuming, while the overlay weighted model for more accurate results.
Fault Tolerant Boolean Satisfiability
Roy, A
2011-01-01
A delta-model is a satisfying assignment of a Boolean formula for which any small alteration, such as a single bit flip, can be repaired by flips to some small number of other bits, yielding a new satisfying assignment. These satisfying assignments represent robust solutions to optimization problems (e.g., scheduling) where it is possible to recover from unforeseen events (e.g., a resource becoming unavailable). The concept of delta-models was introduced by Ginsberg, Parkes and Roy (AAAI 1998), where it was proved that finding delta-models for general Boolean formulas is NP-complete. In this paper, we extend that result by studying the complexity of finding delta-models for classes of Boolean formulas which are known to have polynomial time satisfiability solvers. In particular, we examine 2-SAT, Horn-SAT, Affine-SAT, dual-Horn-SAT, 0-valid and 1-valid SAT. We see a wide variation in the complexity of finding delta-models, e.g., while 2-SAT and Affine-SAT have polynomial time tests for delta-models, testing w...
Boolean gates on actin filaments
Siccardi, Stefano; Tuszynski, Jack A.; Adamatzky, Andrew
2016-01-01
Actin is a globular protein which forms long polar filaments in the eukaryotic cytoskeleton. Actin networks play a key role in cell mechanics and cell motility. They have also been implicated in information transmission and processing, memory and learning in neuronal cells. The actin filaments have been shown to support propagation of voltage pulses. Here we apply a coupled nonlinear transmission line model of actin filaments to study interactions between voltage pulses. To represent digital information we assign a logical TRUTH value to the presence of a voltage pulse in a given location of the actin filament, and FALSE to the pulse's absence, so that information flows along the filament with pulse transmission. When two pulses, representing Boolean values of input variables, interact, then they can facilitate or inhibit further propagation of each other. We explore this phenomenon to construct Boolean logical gates and a one-bit half-adder with interacting voltage pulses. We discuss implications of these findings on cellular process and technological applications.
Investigating Boolean Matrix Factorization
Snášel, V.; Platoš, J.; Krömer, P.; Húsek, Dušan; Neruda, Roman; Frolov, A. A.
- : ACM, 2008 - (Ding, C.; Li, T.; Zhu, S.), s. 18-25 ISBN 978-1-60558-307-5. [DMMT'08. Workshop in Conjunction with SIGKDD 2008 /14./. Las Vegas (US), 24.08.2008-24.08.2008] Institutional research plan: CEZ:AV0Z10300504 Keywords : Boolean factor analysis * nonnegative matrix factorization * neural networks * information retrieval * data mining * binary data Subject RIV: BB - Applied Statistics, Operational Research http://users.cs.fiu.edu/~taoli/kdd08-workshop/DMMT08-Proceedings.pdf
Montanaro, Ashley; Osborne, Tobias J.
2008-01-01
In this paper we introduce the study of quantum boolean functions, which are unitary operators f whose square is the identity: f^2 = I. We describe several generalisations of well-known results in the theory of boolean functions, including quantum property testing; a quantum version of the Goldreich-Levin algorithm for finding the large Fourier coefficients of boolean functions; and two quantum versions of a theorem of Friedgut, Kalai and Naor on the Fourier spectra of boolean functions. In o...
Boolean reasoning the logic of boolean equations
Brown, Frank Markham
2012-01-01
A systematic treatment of Boolean reasoning, this concise, newly revised edition combines the works of early logicians with recent investigations, including previously unpublished research results. Brown begins with an overview of elementary mathematical concepts and outlines the theory of Boolean algebras. Two concluding chapters deal with applications. 1990 edition.
Andersen, Henrik Reif; Hulgaard, Henrik
2002-01-01
This paper presents a new data structure called boolean expression diagrams (BEDs) for representing and manipulating Boolean functions. BEDs are a generalization of binary decision diagrams (BDDs) which can represent any Boolean circuit in linear space. Two algorithms are described for transforming...
布尔表达式的化简与并行排序网络验证%Boolean expression simplification and parallel sort network validation
王德才; 徐建国; 吴哲辉; 罗永亮; 王传民
2009-01-01
To design an effective tool that can be used to verify the correctness of a parallel sorting network, a Boolean expression sim-plification algorithm based on the [0,1] theory and Boolean function of the characteristics and the nature is put forward, based on this algorithm a validation tool is designed. The characteristics and the nature of [0,1] theory and Boolean function are discussed and the natures that are helpful to simplify of the operation are pointed out. The tool can be used for the design of parallel sorting networks based on the parameters of the network graphics, and it can automatically generate the Boolean expressions and simplify it. The tool's output will be helpful to analyze the network, and it can also be used to design and optimize the sort network. Finally, the validity of the tool is demonstrated by the application.%为设计出能够验证并行排序网络正确性的有效工具,根据[0,1]原理和布尔函数的特点和性质,提出一种布尔表达式的化简算法,并根据此算法设计出验证工具.对[0,1]原理和布尔函数的特点和性质进行了讨论,指出有利于化简操作的性质.设计出的工具能够根据并行排序网络的参数显示网络图形、自动生成布尔表达式并实现化简验证,工具的输出有利于对排序网络的分析,也可以用于辅助排序网络的设计和优化.实验结果表明了该工具的有效性.
Fault Tolerant Boolean Satisfiability
Roy, A
2011-01-01
A delta-model is a satisfying assignment of a Boolean formula for which any small alteration, such as a single bit flip, can be repaired by flips to some small number of other bits, yielding a new satisfying assignment. These satisfying assignments represent robust solutions to optimization problems (e.g., scheduling) where it is possible to recover from unforeseen events (e.g., a resource becoming unavailable). The concept of delta-models was introduced by Ginsberg, Parkes and Roy (AAAI 1998...
Controllability and observability of Boolean control networks%布尔控制网络的能控性与能观性
李志强; 宋金利
2013-01-01
Using the semi-tensor product,we convert the Boolean control network to its algebraic form.From the structure matrix of Boolean control network,the controllability and observability of the Boolean control network are discussed.A novel necessary and sufficient condition for controllability,which improves the recent results,is given.The new controllability condition eliminates the redundant computation of controllability matrix.The highest power of matrix is reduced from 2m+n to 2 n.Also,a sufficient condition for observability is obtained,which can be computed easily.A numerical example is presented to show the applicability of our controllability and observability condition.%利用矩阵的半张量积,布尔控制网络被转化为离散时间系统.本文从离散时间系统的结构矩阵出发,讨论了逻辑控制系统的能控能观性条件,得到了一个新的能控性条件.新的条件简化了原有能控性矩阵的计算复杂性,矩阵的最高阶数由原来的2m+n降到了2n.另外,还得到了检验布尔控制网络能观性的条件.与原有条件相比,新的条件更容易计算检验.最后,给出一个实例,检验给出的能控能观性判断条件的正确性.
Solomon, Alan D
2012-01-01
REA's Essentials provide quick and easy access to critical information in a variety of different fields, ranging from the most basic to the most advanced. As its name implies, these concise, comprehensive study guides summarize the essentials of the field covered. Essentials are helpful when preparing for exams, doing homework and will remain a lasting reference source for students, teachers, and professionals. Boolean Algebra includes set theory, sentential calculus, fundamental ideas of Boolean algebras, lattices, rings and Boolean algebras, the structure of a Boolean algebra, and Boolean
Fast Gr\\"obner Basis Computation for Boolean Polynomials
Hinkelmann, Franziska
2010-01-01
We introduce the Macaulay2 package BooleanGB, which computes a Gr\\"obner basis for Boolean polynomials using a binary representation rather than symbolic. We compare the runtime of several Boolean models from systems in biology and give an application to Sudoku.
"Antelope": a hybrid-logic model checker for branching-time Boolean GRN analysis
Arellano Gustavo; Argil Julián; Azpeitia Eugenio; Benítez Mariana; Carrillo Miguel; Góngora Pedro; Rosenblueth David A.; Alvarez-Buylla Elena R
2011-01-01
Abstract Background In Thomas' formalism for modeling gene regulatory networks (GRNs), branching time, where a state can have more than one possible future, plays a prominent role. By representing a certain degree of unpredictability, branching time can model several important phenomena, such as (a) asynchrony, (b) incompletely specified behavior, and (c) interaction with the environment. Introducing more than one possible future for a state, however, creates a difficulty for ordinary simulat...
Monotone Boolean functions are an important object in discrete mathematics and mathematical cybernetics. Topics related to these functions have been actively studied for several decades. Many results have been obtained, and many papers published. However, until now there has been no sufficiently complete monograph or survey of results of investigations concerning monotone Boolean functions. The object of this survey is to present the main results on monotone Boolean functions obtained during the last 50 years
Tucker, Jerry H.; Tapia, Moiez A.; Bennett, A. Wayne
1988-01-01
The concept of Boolean integration is developed, and different Boolean integral operators are introduced. Given the changes in a desired function in terms of the changes in its arguments, the ways of 'integrating' (i.e. realizing) such a function, if it exists, are presented. The necessary and sufficient conditions for integrating, in different senses, the expression specifying the changes are obtained. Boolean calculus has applications in the design of logic circuits and in fault analysis.
Andersen, Henrik Reif; Hulgaard, Henrik
This paper presents a new data structure called Boolean Expression Diagrams (BEDs) for representing and manipulating Boolean functions. BEDs are a generalization of Binary Decision Diagrams (BDDs) which can represent any Boolean circuit in linear space and still maintain many of the desirable...... properties of BDDs. Two algorithms are described for transforming a BED into a reduced ordered BDD. One closely mimics the BDD apply-operator while the other can exploit the structural information of the Boolean expression. The efficacy of the BED representation is demonstrated by verifying that the...
Mikko Niilo-Rämä
2014-06-01
Full Text Available A novel estimator for estimating the mean length of fibres is proposed for censored data observed in square shaped windows. Instead of observing the fibre lengths, we observe the ratio between the intensity estimates of minus-sampling and plus-sampling. It is well-known that both intensity estimators are biased. In the current work, we derive the ratio of these biases as a function of the mean length assuming a Boolean line segment model with exponentially distributed lengths and uniformly distributed directions. Having the observed ratio of the intensity estimators, the inverse of the derived function is suggested as a new estimator for the mean length. For this estimator, an approximation of its variance is derived. The accuracies of the approximations are evaluated by means of simulation experiments. The novel method is compared to other methods and applied to real-world industrial data from nanocellulose crystalline.
Analysis and Control of Boolean Networks:A Semi-tensor Product Approach%布尔网络的分析与控制-矩阵半张量积方法
程代展; 齐洪胜; 赵寅
2011-01-01
布尔网络是描述基因调控网络的一个有力工具.由于系统生物学的发展,布尔网络的分析与控制成为生物学与系统控制学科的交叉热点.本文综述作者用其原创的矩阵半张量积方法在布尔网络的分析与控制中得到的一系列结果.内容包括:布尔网络的拓扑结构,布尔控制网络的能控、能观性与实现,布尔网络的稳定性和布尔控制网络的镇定,布尔控制网络的干扰解耦,布尔(控制)网络的辨识,以及布尔网络的最优控制等.%Boolean network is a powerful tool for describing gene regulatory network. With the development of the systems biology, the analysis and control of Boolean networks become a hot topic for multidisciplinary research. This paper surveys some recent results obtained in the analysis and control of Boolean networks using semi-tensor product of matrices. The contents of this paper include the topological structure of Boolean networks, the controllability and observability, realization, stability and stabilization, disturbance decoupling, identification, and optimal control of Boolean (control) networks.
Image Restoration Research Based on Boolean Cloud Model Algorithm%基于布尔云模型算法的图像修复研究
王宝红; 郭水旺; 季钢
2013-01-01
Aiming at the deficiencies of the existing image restoration algorithm,Boolean cloud model algorithm is used.First the cloud model is constructed,cloud entropy to determine cloud Boolean relations,clouds appear,Boolean logic to calculate each cloud droplet collection of mutual information entropy,entropy of different results to determine value.Followed by the input and Boolean cloud state function determines the cloud model decision by input Boolean function can produce new clouds again,optimize cloud states choose different cloud entropy dynamic changes.Finally,the algorithm processes.simulation results show operator to connect natural repair image,smoothness,to maintain the overall continuous,and PSNR value.%针对现有图像修复算法的不足,采用布尔云模型算法.首先构造云模型,利用云熵确定云布尔关系.不同的云团值出现时,布尔逻辑计算每个云滴集合的互信息熵.通过比较熵的不同来确定结果值；接着在受输入和布尔函数决定后产生云态,云模型在受输入和布尔函数决定后,可以再次产生新的云团.对云态进行选择优化,其不同的云熵动态变化,最后给出了算法流程.仿真结果显示算法对修复图像连接自然,有光滑性,保持了整体连续,并且PSNR值较大.
New Measure of Boolean Factor Analysis Quality
Frolov, A. A.; Húsek, Dušan; Polyakov, P.Y.
Vol. 1. Heidelberg: Springer, 2011 - (Dobnikar, A.; Lotrič, U.; Šter, B.), s. 100-109. (Lecture Notes in Computer Science. 6593). ISBN 978-3-642-20281-0. ISSN 0302-9743. [ICANNGA'2011. International Conference /10./. Ljubljana (SI), 14.04.2011-16.04.2011] R&D Projects: GA ČR GAP202/10/0262; GA ČR GA205/09/1079 Institutional research plan: CEZ:AV0Z10300504 Keywords : Boolean factor analysis * information gain * expectation-maximization * associative memory * neural network application * Boolean matrix factorization * bars problem * Hopfield neural network Subject RIV: IN - Informatics, Computer Science
Boolean filters of distributive lattices
M. Sambasiva Rao
2013-07-01
Full Text Available In this paper we introduce the notion of Boolean filters in a pseudo-complemented distributive lattice and characterize the class of all Boolean filters. Further a set of equivalent conditions are derived for a proper filter to become a prime Boolean filter. Also a set of equivalent conditions is derived for a pseudo-complemented distributive lattice to become a Boolean algebra. Finally, a Boolean filter is characterized in terms of congruences.
An autocatalytic network model for stock markets
Caetano, Marco Antonio Leonel; Yoneyama, Takashi
2015-02-01
The stock prices of companies with businesses that are closely related within a specific sector of economy might exhibit movement patterns and correlations in their dynamics. The idea in this work is to use the concept of autocatalytic network to model such correlations and patterns in the trends exhibited by the expected returns. The trends are expressed in terms of positive or negative returns within each fixed time interval. The time series derived from these trends is then used to represent the movement patterns by a probabilistic boolean network with transitions modeled as an autocatalytic network. The proposed method might be of value in short term forecasting and identification of dependencies. The method is illustrated with a case study based on four stocks of companies in the field of natural resource and technology.
Two Expectation-Maximization Algorithms for Boolean Factor Analysis
Frolov, A. A.; Húsek, Dušan; Polyakov, P.Y.
2014-01-01
Roč. 130, 23 April (2014), s. 83-97. ISSN 0925-2312 R&D Projects: GA ČR GAP202/10/0262 Grant ostatní: GA MŠk(CZ) ED1.1.00/02.0070; GA MŠk(CZ) EE.2.3.20.0073 Institutional research plan: CEZ:AV0Z10300504 Keywords : Boolean Factor analysis * Binary Matrix factorization * Neural networks * Binary data model * Dimension reduction * Bars problem Subject RIV: IN - Informatics, Computer Science Impact factor: 2.083, year: 2014
Collaborative networks: Reference modeling
L.M. Camarinha-Matos; H. Afsarmanesh
2008-01-01
Collaborative Networks: Reference Modeling works to establish a theoretical foundation for Collaborative Networks. Particular emphasis is put on modeling multiple facets of collaborative networks and establishing a comprehensive modeling framework that captures and structures diverse perspectives of
Inadmissible Class of Boolean Functions under Stuck-at Faults
Das, Debesh K.; Chowdhury, Debabani; Bhattacharya, Bhargab B; Sasao, Tsutomu
2013-01-01
Many underlying structural and functional factors that determine the fault behavior of a combinational network, are not yet fully understood. In this paper, we show that there exists a large class of Boolean functions, called root functions, which can never appear as faulty response in irredundant two-level circuits even when any arbitrary multiple stuck-at faults are injected. Conversely, we show that any other Boolean function can appear as a faulty response from an irredundant realization ...
Geometric Operators on Boolean Functions
Frisvad, Jeppe Revall; Falster, Peter
2007-01-01
In truth-functional propositional logic, any propositional formula represents a Boolean function (according to some valuation of the formula). We describe operators based on Decartes' concept of constructing coordinate systems, for translation of a propositional formula to the image of a Boolean function. With this image of a Boolean function corresponding to a propositional formula, we prove that the orthogonal projection operator leads to a theorem describing all rules of inference in propo...
Algorithms for Weighted Boolean Optimization
Manquinho, Vasco; Marques-Silva, Joao; Planes Cid, Jordi
2009-01-01
The Pseudo-Boolean Optimization (PBO) and Maximum Satisfiability (MaxSAT) problems are natural optimization extensions of Boolean Satisfiability (SAT). In the recent past, different algorithms have been proposed for PBO and for MaxSAT, despite the existence of straightforward mappings from PBO to MaxSAT and viceversa. This papers proposes Weighted Boolean Optimization (WBO), a new uni- fied framework that aggregates and extends PBO and MaxSAT. In addition, the paper proposes...
Boolean Delay Equations: A Simple Way of Looking at Interactions and Extreme Events
Ghil, Michael
2013-04-01
Boolean Delay Equations (BDEs) are semi-discrete dynamical models with Boolean-valued variables that evolve in continuous time. Systems of BDEs can be classified into conservative or dissipative, in a manner that parallels the classification of ordinary or partial differential equations. Solutions to certain conservative BDEs exhibit growth of complexity in time; such BDEs can be seen therefore as metaphors for biological evolution or human history. Dissipative BDEs are structurally stable and exhibit multiple equilibria and limit cycles, as well as more complex, fractal solution sets, such as Devil's staircases and ``fractal sunbursts.'' BDE systems have been used as highly idealized models of climate change on several time scales, as well as in earthquake modeling and prediction, and in genetics. BDEs with an infinite number of variables on a regular spatial grid have been called "partial BDEs" and we discuss connections with other types of discrete dynamical systems, including cellular automata and Boolean networks. We present recent BDE work on damage propagation in networks, with an emphasis on production-chain models. This formalism turns out to be well adapted to investigating propagation of an initial damage due to a climatic or other natural disaster. It thus serves to study economic impacts of extreme events, as well as extreme disruption of a network of interactions.
基于布尔语义的Gentzen推导模型%Gentzen Deduction Model Based on Boolean Logic Semantics
陈博; 眭跃飞
2015-01-01
Deduction systems are important arts of searching technology. This paper gives a new correspondence between the propositional logic and Boolean algebra, where an inequation is corresponding to a Gentzen sequent, so that the inequation is true in every Boolean algebra if and only if the Gentzen sequent is provable. In information retrieval, the information inference can effectively turn into the operation on poset. Precisely, the logical language for the propositional logic contains operators Ø'Ù'Ú;the terms instead of formulas are defined (a|Øt|t1 Ù t2|t1 Ú t2 , where a is an element) and used to represent elements in Boolean algebra. This paper defines an assignment v using Boolean algebra as its domain, and assigns the terms to be the element in Boolean algebra. The sequence ΓÞΔ is satisfied if tv £tv. Finally, this paper gives a Gentzen system to prove the soundness and completeness theorem.%布尔模型是信息检索系统的一种基础模型。给出了命题逻辑和布尔代数间的一种新的对应关系，其中布尔代数中的不等式对应Gentzen系统中的矢列式，使得当一个不等式在任意布尔代数中为真，当且仅当它所对应的矢列式是可证的。并且使得在信息检索中，针对信息的推理可以有效地转为偏序集上的运算。讨论的命题逻辑语言的运算符为Ø、Ù、Ú；并且定义了项（a|Øt|t1Ù t2|t1Ú t2'其中a是一个元素）来替代原先的公式和表示布尔代数中的元素。此外，定义了以布尔代数为论域的赋值v，将命题逻辑中的项赋值为布尔代数中的元素，并且如果tv £t v ，则矢列式ΓÞ D为真。最后给出了Gentzen系统下的可靠性和完备性定理的证明。tÎΓtÎΔ
Pugacheva, E
2015-01-01
In the offered review some key issues of social network analysis are discussed. This is a brief summary of social network characteristics, models of network formation, and the network perspective. The aim of this overview is to contribute to interdisciplinary dialogue among researchers in physics, mathematics, sociology, who share a common interest in understanding the network phenomena.
硬件加速的渐进式多边形模型布尔运算%GPU-Accelerated Progressive Boolean Operations on Polygonal Models
赵汉理; 孟庆如; 金小刚; 黄辉; 王明
2015-01-01
多边形模型的布尔运算中包含复杂的求交计算以及多边形重建过程，精度控制和处理效率是其中的关键。为了降低布尔运算复杂度，提出一种适合硬件加速的基于渐进式布尔运算的多层次细节网格模型生成方法。该方法采用分层深度图像来近似表示多边形实体的封闭边界，将多边形的求交计算简化为坐标轴平行的采样点的实体内外部判断；为了免去各层次细节模型的重复采样过程，渐进式地将边界采样点归并到低分辨率下的立方体中；运用特征保持的多边形重建算法将相同立方体内的边界采样点转换成多边形顶点，根据邻接关系生成网格模型。上述算法使用支持图形硬件加速的CUDA编程并行实现。实验结果表明了算法的可行性。%Boolean operations on polygonal models involve the complex intersection calculations and po-lygonal reconstruction, where the precision control and processing efficiency are two key problems. To re-duce the Boolean operation complexity, this paper proposes a progressive and GPU accelerated Boolean op-eration approach to generate levels-of-detail polygonal models. Layered depth images are employed to ap-proximate the enclosed boundaries of polygons and the intersection calculations are performed as the in/out classification of axis-aligned sampling points. To avoid the additional sampling process for levels-of-detail models, the boundary points are progressively merged into low-resolution cubes. The feature-preserving dual contouring algorithm is adopted to convert boundary points into a mesh model. The proposed algorithm can be implementation in parallel on GPU with the hardware-supported CUDA. Finally, experimental results show the feasibility of the proposed approach.
Symmetry in Boolean Satisfiability
Fadi A. Aloul
2010-06-01
Full Text Available This paper reviews recent approaches on how to accelerate Boolean Satisfiability (SAT search by exploiting symmetries in the problem space. SAT search algorithms traverse an exponentially large search space looking for an assignment that satisfies a set of constraints. The presence of symmetries in the search space induces equivalence classes on the set of truth assignments. The goal is to use symmetries to avoid traversing all assignments by constraining the search to visit a few representative assignments in each equivalence class. This can lead to a significant reduction in search runtime without affecting the completeness of the search.
Boolean Orthogonalizing Combination Methods
Yavuz Can
2015-05-01
Full Text Available In this paper a new logical operation method called “ presented. It is used to calculate the difference, but also the complement of a function as well as the EXOR and EXNOR of two minterms respectively two ternary respectively two ternary-vector logical operation method called “orthogonal OR advantages of both methods are their results, which are already available form that has an essential advantage for continuing calculations. Since it applies, an orthogonal disjunctive normal form is equal to orthogonal antivalence normal form, subsequent Boolean differential calculus will be simplified.
Approximate Reasoning with Fuzzy Booleans
Broek, van den P.M.; Noppen, J.A.R.
2004-01-01
This paper introduces, in analogy to the concept of fuzzy numbers, the concept of fuzzy booleans, and examines approximate reasoning with the compositional rule of inference using fuzzy booleans. It is shown that each set of fuzzy rules is equivalent to a set of fuzzy rules with singleton crisp ante
Geometric Operators on Boolean Functions
Frisvad, Jeppe Revall; Falster, Peter
of a few geometric operators working on the images of Boolean functions. The operators we describe, arise from the niche area of array-based logic and have previously been tightly bound to an array-based representation of Boolean functions. We redefine the operators in an abstract form to make them...
Linear Programming Formulation of the Boolean Satisfiability Problem
Diaby, Moustapha
2008-01-01
In this paper, we present a new, graph-based modeling approach and a polynomial-sized linear programming (LP) formulation of the Boolean satisfiability problem (SAT). The approach is illustrated with a numerical example.
Cryptographic Boolean functions and applications
Cusick, Thomas W
2009-01-01
Boolean functions are the building blocks of symmetric cryptographic systems. Symmetrical cryptographic algorithms are fundamental tools in the design of all types of digital security systems (i.e. communications, financial and e-commerce).Cryptographic Boolean Functions and Applications is a concise reference that shows how Boolean functions are used in cryptography. Currently, practitioners who need to apply Boolean functions in the design of cryptographic algorithms and protocols need to patch together needed information from a variety of resources (books, journal articles and other sources). This book compiles the key essential information in one easy to use, step-by-step reference. Beginning with the basics of the necessary theory the book goes on to examine more technical topics, some of which are at the frontier of current research.-Serves as a complete resource for the successful design or implementation of cryptographic algorithms or protocols using Boolean functions -Provides engineers and scient...
Cardinal invariants on Boolean algebras
Monk, J Donald
2014-01-01
This book is concerned with cardinal number valued functions defined for any Boolean algebra. Examples of such functions are independence, which assigns to each Boolean algebra the supremum of the cardinalities of its free subalgebras, and cellularity, which gives the supremum of cardinalities of sets of pairwise disjoint elements. Twenty-one such functions are studied in detail, and many more in passing. The questions considered are the behaviour of these functions under algebraic operations such as products, free products, ultraproducts, and their relationships to one another. Assuming familiarity with only the basics of Boolean algebras and set theory, through simple infinite combinatorics and forcing, the book reviews current knowledge about these functions, giving complete proofs for most facts. A special feature of the book is the attention given to open problems, of which 185 are formulated. Based on Cardinal Functions on Boolean Algebras (1990) and Cardinal Invariants on Boolean Algebras (1996) by the...
Boolean delay equations: A simple way of looking at complex systems
Ghil, Michael; Zaliapin, Ilya; Coluzzi, Barbara
2008-12-01
Boolean Delay Equations (BDEs) are semi-discrete dynamical models with Boolean-valued variables that evolve in continuous time. Systems of BDEs can be classified into conservative or dissipative, in a manner that parallels the classification of ordinary or partial differential equations. Solutions to certain conservative BDEs exhibit growth of complexity in time; such BDEs can be seen therefore as metaphors for biological evolution or human history. Dissipative BDEs are structurally stable and exhibit multiple equilibria and limit cycles, as well as more complex, fractal solution sets, such as Devil’s staircases and “fractal sunbursts.” All known solutions of dissipative BDEs have stationary variance. BDE systems of this type, both free and forced, have been used as highly idealized models of climate change on interannual, interdecadal and paleoclimatic time scales. BDEs are also being used as flexible, highly efficient models of colliding cascades of loading and failure in earthquake modeling and prediction, as well as in genetics. In this paper we review the theory of systems of BDEs and illustrate their applications to climatic and solid-earth problems. The former have used small systems of BDEs, while the latter have used large hierarchical networks of BDEs. We moreover introduce BDEs with an infinite number of variables distributed in space (“partial BDEs”) and discuss connections with other types of discrete dynamical systems, including cellular automata and Boolean networks. This research-and-review paper concludes with a set of open questions.
语义特征建模系统中布尔算法的研究%Research on Boolean Operation in Semantic Feature Modeling System
金瑛浩; 孙立镌
2012-01-01
To improve the efficiency of boolean operations in semantic feature modeling system,a semantic representation based method was proposed. It represents feature models with semantic representation, manages feature elements by cellular model,improves detect efficiency of features interaction and builds new the feature entity by splitting inter-sectant cells and semantic faces. This method can not only build the boolean entity rapidly and exactly, but also avoid errors such as holes and losing geometry faces. Experiments on computer show that this new method is more adaptable and practicable.%为了提高语义特征建模系统中布尔操作的运行效率,提出了一种基于语义表示法的布尔操作算法.该算法用语义表示法表示特征模型,用细胞元模型组织和管理特征元素,用语义面替代几何面来提高特征的交互检测效率,通过细胞分裂和语义面分解来生成新实体.该算法不仅可以快速准确地生成布尔实体,还可以避免几何面的丢失及“孔洞”等错误的发生.实验证明,该算法具有广泛的使用前景和实用价值.
A unified biological modeling and simulation system for analyzing biological reaction networks
Yu, Seok Jong; Tung, Thai Quang; Park, Junho; Lim, Jongtae; Yoo, Jaesoo
2013-12-01
In order to understand the biological response in a cell, a researcher has to create a biological network and design an experiment to prove it. Although biological knowledge has been accumulated, we still don't have enough biological models to explain complex biological phenomena. If a new biological network is to be created, integrated modeling software supporting various biological models is required. In this research, we design and implement a unified biological modeling and simulation system, called ezBioNet, for analyzing biological reaction networks. ezBioNet designs kinetic and Boolean network models and simulates the biological networks using a server-side simulation system with Object Oriented Parallel Accelerator Library framework. The main advantage of ezBioNet is that a user can create a biological network by using unified modeling canvas of kinetic and Boolean models and perform massive simulations, including Ordinary Differential Equation analyses, sensitivity analyses, parameter estimates and Boolean network analysis. ezBioNet integrates useful biological databases, including the BioModels database, by connecting European Bioinformatics Institute servers through Web services Application Programming Interfaces. In addition, we employ Eclipse Rich Client Platform, which is a powerful modularity framework to allow various functional expansions. ezBioNet is intended to be an easy-to-use modeling tool and a simulation system for understanding the control mechanism by monitoring the change of each component in a biological network. The simulation result can be managed and visualized on ezBioNet, which is available free of charge at http://ezbionet.sourceforge.net or http://ezbionet.cbnu.ac.kr.
Boolean Equi-propagation for Optimized SAT Encoding
Metodi, Amit; Lagoon, Vitaly; Stuckey, Peter J
2011-01-01
We present an approach to propagation based solving, Boolean equi-propagation, where constraints are modelled as propagators of information about equalities between Boolean literals. Propagation based solving applies this information as a form of partial evaluation resulting in optimized SAT encodings. We demonstrate for a variety of benchmarks that our approach results in smaller CNF encodings and leads to speed-ups in solving times.
On Kolmogorov's superpositions and Boolean functions
Beiu, V.
1998-12-31
The paper overviews results dealing with the approximation capabilities of neural networks, as well as bounds on the size of threshold gate circuits. Based on an explicit numerical (i.e., constructive) algorithm for Kolmogorov's superpositions they will show that for obtaining minimum size neutral networks for implementing any Boolean function, the activation function of the neurons is the identity function. Because classical AND-OR implementations, as well as threshold gate implementations require exponential size (in the worst case), it will follow that size-optimal solutions for implementing arbitrary Boolean functions require analog circuitry. Conclusions and several comments on the required precision are ending the paper.
A Note on the Inversion Complexity of Boolean Functions in Boolean Formulas
Morizumi, Hiroki
2008-01-01
In this note, we consider the minimum number of NOT operators in a Boolean formula representing a Boolean function. In circuit complexity theory, the minimum number of NOT gates in a Boolean circuit computing a Boolean function $f$ is called the inversion complexity of $f$. In 1958, Markov determined the inversion complexity of every Boolean function and particularly proved that $\\lceil \\log_2(n+1) \\rceil$ NOT gates are sufficient to compute any Boolean function on $n$ variables. As far as we...
Boolean Factor Analysis by Expectation-Maximization Method
Frolov, A. A.; Húsek, Dušan; Polyakov, P.Y.
Heidelberg : Springer, 2013 - (Kudělka, M.; Pokorný, J.; Snášel, V.; Abraham, A.), s. 243-254 ISBN 978-3-642-31602-9. ISSN 2194-5357. - (Advances in Intelligent Systems and Computing. 179). [IHCI 2011. International Conference on Intelligent Human Computer Interaction /3./. Prague (CZ), 29.08.2011-31.08.2011] R&D Projects: GA ČR GAP202/10/0262; GA ČR GA205/09/1079 Grant ostatní: GA MŠk(CZ) ED1.1.00/02.0070 Institutional research plan: CEZ:AV0Z10300504 Keywords : neural networks * hidden pattern search * Boolean factor analysis * generative model * information redundancy * exceptation-maximization Subject RIV: IN - Informatics, Computer Science
Andersen, Kasper Winther
Three main topics are presented in this thesis. The first and largest topic concerns network modelling of functional Magnetic Resonance Imaging (fMRI) and Diffusion Weighted Imaging (DWI). In particular nonparametric Bayesian methods are used to model brain networks derived from resting state f...... for their ability to reproduce node clustering and predict unseen data. Comparing the models on whole brain networks, BCD and IRM showed better reproducibility and predictability than IDM, suggesting that resting state networks exhibit community structure. This also points to the importance of using models, which...... allow for complex interactions between all pairs of clusters. In addition, it is demonstrated how the IRM can be used for segmenting brain structures into functionally coherent clusters. A new nonparametric Bayesian network model is presented. The model builds upon the IRM and can be used to infer...
Modeling Epidemic Network Failures
Ruepp, Sarah Renée; Fagertun, Anna Manolova
2013-01-01
This paper presents the implementation of a failure propagation model for transport networks when multiple failures occur resulting in an epidemic. We model the Susceptible Infected Disabled (SID) epidemic model and validate it by comparing it to analytical solutions. Furthermore, we evaluate...... the SID model’s behavior and impact on the network performance, as well as the severity of the infection spreading. The simulations are carried out in OPNET Modeler. The model provides an important input to epidemic connection recovery mechanisms, and can due to its flexibility and versatility be used...... to evaluate multiple epidemic scenarios in various network types....
Artificial neural network modelling
Samarasinghe, Sandhya
2016-01-01
This book covers theoretical aspects as well as recent innovative applications of Artificial Neural networks (ANNs) in natural, environmental, biological, social, industrial and automated systems. It presents recent results of ANNs in modelling small, large and complex systems under three categories, namely, 1) Networks, Structure Optimisation, Robustness and Stochasticity 2) Advances in Modelling Biological and Environmental Systems and 3) Advances in Modelling Social and Economic Systems. The book aims at serving undergraduates, postgraduates and researchers in ANN computational modelling. .
Generalized join-hemimorphisms on Boolean algebras
Sergio Celani
2003-01-01
We introduce the notions of generalized join-hemimorphism and generalized Boolean relation as an extension of the notions of join-hemimorphism and Boolean relation, respectively. We prove a duality between these two notions. We will also define a generalization of the notion of Boolean algebra with operators by considering a finite family of Boolean algebras endowed with a generalized join-hemimorphism. Finally, we define suitable notions of subalgebra, congruences, Boole...
Boolean Operations on Conic Polygons
Yong-Xi Gong; Yu Liu; Lun Wu; Yu-Bo Xie
2009-01-01
An algorithm for Boolean operations on conic polygons is proposed. Conic polygons are polygons consisting of conic segments or bounded conics with directions. Preliminaries of Boolean operations on general polygons are presented. In our algorithm, the intersection points and the topological relationships between two conic polygons are computed. Boundaries are obtained by tracking path and selecting uncrossed boundaries following rule tables to build resulting conic polygons.We define a set of rules for the intersection, union, and subtraction operations on conic polygons. The algorithm considers degeneration cases such as homology, complement, interior, and exterior. The algorithm is also evaluated and implemented.
Cardinal invariants on Boolean algebras
Monk, J Donald
2009-01-01
Deals with cardinal number valued functions defined for any Boolean algebra. This title considers the behavior of these functions under algebraic operations such as products, free products, ultraproducts, and their relationships to one another. It covers topics such as ultraproducts and Fedorchukis theorem
Boolean-Valued Belief Functions
Kramosil, Ivan
2002-01-01
Roč. 31, č. 2 (2002), s. 153-181. ISSN 0308-1079 R&D Projects: GA AV ČR IAA1030803 Institutional research plan: AV0Z1030915 Keywords : Dempster-Schafer theory * Boolean algebra Subject RIV: BA - General Mathematics Impact factor: 0.241, year: 2002
Evolutionary Design of Boolean Functions
WANG Zhang-yi; ZHANG Huan-guo; QIN Zhong-ping; MENG Qing-shu
2005-01-01
We use evolutionary computing to synthesize Boolean functions randomly. By using specific crossover and mutation operator in evolving process and modifying search space and fitness function, we get some high non-linearity functions which have other good cryptography characteristics such as autocorrelation etc. Comparing to other heuristic search techniques, evolutionary computing approach is more effective because of global search strategy and implicit parallelism.
Ordered Boolean List (OBL): reducing the footprint for evaluating Boolean expressions.
Rossignac, Jaroslaw Jarek
2011-09-01
An Expanded Boolean Expression (EBE) does not contain any XOR or EQUAL operators. The occurrence of each variable is a different literal. We provide a linear time algorithm that converts an EBE of n literals into a logically equivalent Ordered Boolean List (OBL) and show how to use the OBL to evaluate the EBE in n steps and O(log log n) space, if the values of the literals are each read once in the order prescribed by the OBL. (An evaluation workspace of 5 bits suffices for all EBEs of up to six billion literals.) The primary application is the SIMD architecture, where the same EBE is evaluated in parallel for different input vectors when rendering solid models on the GPU directly from their Constructive Solid Geometry (CSG) representation. We compare OBL to the Reduced Ordered Binary Decision Diagram (ROBDD) and suggest possible applications of OBL to logic verification and to circuit design. PMID:21737862
Method of Boolean operation based on 3D grid model%三维网格模型的布尔运算方法
陈学工; 杨兰; 黄伟; 季兴
2011-01-01
提出了一种基于三维网格模型的布尔运算方法.首先通过基于方向包围盒(OBB)层次包围盒树的碰撞检测算法,得到实体的相交三角形对;接下来求出两相交三角形之间的交线,建立与三角形的交线拓扑关系;通过分类处理三种交线类型来对相交三角形进行区域划分,得到一系列多边形,并对多边形进行三角剖分形成结果区域;最后根据体的包含关系构建关系邻接表,判断多边形区域的相对于其他实体的内外关系并通过网格模型的拓扑关系,定位表面三角网格区域;同时根据交、并、差等布尔操作,对结果区域进行取舍,得到最终结果.实验结果表明相交部分的岩性与实体的岩性相吻合,验证了该算法的正确性以及可行性.%A kind of Boolean operational method based on a three-dimensional grid model was proposed. Firstly, through collision detection algorithm based on hierarchical bounding box tree of Oriented Bounding Box (ORB), the intersecting triangles could be got. Through the intersection test of the triangles, the intersecting lines could be obtained and the intersecting lines topology relations with the triangles could be established. Secondly, a regional division for the intersecting triangles was made through processing the three types of intersecting lines, so as to get a series of polygons, and carry out Delaunay triangulations for polygon to get the result area. Lastly, relation adjacency list was constructed based on solid containing relations, the polygon's internal relation and external relation with other entities were judged, and the triangles were located according to the mesh model topology relations. Simultaneously, according to such Boolean operations as the intersection, union, and differences, according to the grid model topology relations were judged, the position of the triangles were judged and then the final results could be obtained. Experimental results show that this
Implementing Boolean Matrix Factorization
Neruda, Roman; Snášel, V.; Platoš, J.; Krömer, P.; Húsek, Dušan; Frolov, A. A.
Vol. Part I. Berlin : Springer, 2008 - (Kůrková, V.; Neruda, R.; Koutník, J.), s. 543-552 ISBN 978-3-540-87535-2. - (Lecture Notes in Computer Science. 5163). [ICANN 2008. International Conference on Artificial Neural Network s /18./. Prague (CZ), 03.09.2008-06.09.2008] Institutional research plan: CEZ:AV0Z10300504 Keywords : factor analysis * genetic algorithm * neural network s Subject RIV: IN - Informatics, Computer Science
Learning Boolean functions with concentrated spectra
Mixon, Dustin G.; Peterson, Jesse
2015-08-01
This paper discusses the theory and application of learning Boolean functions that are concentrated in the Fourier domain. We first estimate the VC dimension of this function class in order to establish a small sample complexity of learning in this case. Next, we propose a computationally efficient method of empirical risk minimization, and we apply this method to the MNIST database of handwritten digits. These results demonstrate the effectiveness of our model for modern classification tasks. We conclude with a list of open problems for future investigation.
Network Reliability Algorithm Based on Pathset Matrix and Boolean Operation%基于路集矩阵与布尔运算的网络可靠度算法
高会生; 展敬宇; 王博颖; 李潇睿
2012-01-01
This paper analyzes the network reliability algorithm based on pathset matrix, and there exists a serious combination explosion problem in this algorithm. Aiming at this problem, it proposes a network reliability algorithm based on pathset matrix and boolean operation. The concept of bit vector is introduced. In addition, the pre-process of special pathsets and count of all-one bit vectors are also implied. Experimental results show that it not only increases the memory utilization, reduce the redundancy but also relieve the combination explosion problem in some degree.%分析基于路集矩阵与布尔运算的网络可靠度算法,指出其存在组合爆炸问题.为此,提出一种改进算法,引入位矢量以减少内存需求,对特殊路集进行预处理并统计全1位矢量.实验结果表明,改进算法可提高内存利用率、减少冗余运算,能在一定程度上缓解组合爆炸问题.
Exploiting Surroundedness for Saliency Detection: A Boolean Map Approach.
Zhang, Jianming; Sclaroff, Stan
2016-05-01
We demonstrate the usefulness of surroundedness for eye fixation prediction by proposing a Boolean Map based Saliency model (BMS). In our formulation, an image is characterized by a set of binary images, which are generated by randomly thresholding the image's feature maps in a whitened feature space. Based on a Gestalt principle of figure-ground segregation, BMS computes a saliency map by discovering surrounded regions via topological analysis of Boolean maps. Furthermore, we draw a connection between BMS and the Minimum Barrier Distance to provide insight into why and how BMS can properly captures the surroundedness cue via Boolean maps. The strength of BMS is verified by its simplicity, efficiency and superior performance compared with 10 state-of-the-art methods on seven eye tracking benchmark datasets. PMID:26336114
Terse Integer Linear Programs for Boolean Optimization
Christoph Buchheim
2009-05-01
Full Text Available We present a new polyhedral approach to nonlinear Boolean optimization. Compared to other methods, it produces much smaller integer programming models, making it more efficient from a practical point of view. We mainly obtain this by two different ideas: first, we do not require the objective function to be in any normal form. The transformation into a normal form usually leads to the introduction of many additional variables or constraints. Second, we reduce the problem to the degree-two case in a very efficient way, by slightly extending the dimension of the original variable space. The resulting model turns out to be closely related to the maximum cut problem; we show that the corresponding polytope is a face of a suitable cut polytope in most cases. In particular, our separation problem reduces to the one for the maximum cut problem. In practice, the approach appears to be very competitive for unconstrained Boolean optimization problems. First experimental results, which have been obtained for some particularly hard instances of the Max-SAT Evaluation 2007, show that our very general implementation can outperform even special-purpose Max-SAT solvers. The software is accessible online under “we.logoptimize.it”.
Cost-Optimal Execution of Trees of Boolean Operators with Shared Streams
Casanova, Henri; Lim, Lipyeow; Robert, Yves; Vivien, Frédéric; Zaidouni, Dounia
2013-01-01
The processing of queries expressed as trees of boolean operators applied to predicates on sensor data streams has several applications in mobile computing. Sensor data must be retrieved from the sensors to a query processing device, such as a smartphone, over one or more network interfaces. Retrieving a data item incurs a cost, e.g., an energy expense that depletes the smartphone's battery. Since the query tree contains boolean operators, part of the tree can be shortcircuited depending on t...
A Network-of-Networks Model for Electrical Infrastructure Networks
Halappanavar, Mahantesh; Hogan, Emilie; Duncan, Daniel; Zhenyu,; Huang,; Hines, Paul D H
2015-01-01
Modeling power transmission networks is an important area of research with applications such as vulnerability analysis, study of cascading failures, and location of measurement devices. Graph-theoretic approaches have been widely used to solve these problems, but are subject to several limitations. One of the limitations is the ability to model a heterogeneous system in a consistent manner using the standard graph-theoretic formulation. In this paper, we propose a {\\em network-of-networks} approach for modeling power transmission networks in order to explicitly incorporate heterogeneity in the model. This model distinguishes between different components of the network that operate at different voltage ratings, and also captures the intra and inter-network connectivity patterns. By building the graph in this fashion we present a novel, and fundamentally different, perspective of power transmission networks. Consequently, this novel approach will have a significant impact on the graph-theoretic modeling of powe...
Neural Network Model For Fast Learning And Retrieval
Arsenault, Henri H.; Macukow, Bohdan
1989-05-01
An approach to learning in a multilayer neural network is presented. The proposed network learns by creating interconnections between the input layer and the intermediate layer. In one of the new storage prescriptions proposed, interconnections are excitatory (positive) only and the weights depend on the stored patterns. In the intermediate layer each mother cell is responsible for one stored pattern. Mutually interconnected neurons in the intermediate layer perform a winner-take-all operation, taking into account correlations between stored vectors. The performance of networks using this interconnection prescription is compared with two previously proposed schemes, one using inhibitory connections at the output and one using all-or-nothing interconnections. The network can be used as a content-addressable memory or as a symbolic substitution system that yields an arbitrarily defined output for any input. The training of a model to perform Boolean logical operations is also described. Computer simulations using the network as an autoassociative content-addressable memory show the model to be efficient. Content-addressable associative memories and neural logic modules can be combined to perform logic operations on highly corrupted data.
Laomettachit, Teeraphan; Chen, Katherine C.; Baumann, William T.
2016-01-01
To understand the molecular mechanisms that regulate cell cycle progression in eukaryotes, a variety of mathematical modeling approaches have been employed, ranging from Boolean networks and differential equations to stochastic simulations. Each approach has its own characteristic strengths and weaknesses. In this paper, we propose a “standard component” modeling strategy that combines advantageous features of Boolean networks, differential equations and stochastic simulations in a framework that acknowledges the typical sorts of reactions found in protein regulatory networks. Applying this strategy to a comprehensive mechanism of the budding yeast cell cycle, we illustrate the potential value of standard component modeling. The deterministic version of our model reproduces the phenotypic properties of wild-type cells and of 125 mutant strains. The stochastic version of our model reproduces the cell-to-cell variability of wild-type cells and the partial viability of the CLB2-dbΔ clb5Δ mutant strain. Our simulations show that mathematical modeling with “standard components” can capture in quantitative detail many essential properties of cell cycle control in budding yeast. PMID:27187804
Teeraphan Laomettachit
Full Text Available To understand the molecular mechanisms that regulate cell cycle progression in eukaryotes, a variety of mathematical modeling approaches have been employed, ranging from Boolean networks and differential equations to stochastic simulations. Each approach has its own characteristic strengths and weaknesses. In this paper, we propose a "standard component" modeling strategy that combines advantageous features of Boolean networks, differential equations and stochastic simulations in a framework that acknowledges the typical sorts of reactions found in protein regulatory networks. Applying this strategy to a comprehensive mechanism of the budding yeast cell cycle, we illustrate the potential value of standard component modeling. The deterministic version of our model reproduces the phenotypic properties of wild-type cells and of 125 mutant strains. The stochastic version of our model reproduces the cell-to-cell variability of wild-type cells and the partial viability of the CLB2-dbΔ clb5Δ mutant strain. Our simulations show that mathematical modeling with "standard components" can capture in quantitative detail many essential properties of cell cycle control in budding yeast.
Laomettachit, Teeraphan; Chen, Katherine C; Baumann, William T; Tyson, John J
2016-01-01
To understand the molecular mechanisms that regulate cell cycle progression in eukaryotes, a variety of mathematical modeling approaches have been employed, ranging from Boolean networks and differential equations to stochastic simulations. Each approach has its own characteristic strengths and weaknesses. In this paper, we propose a "standard component" modeling strategy that combines advantageous features of Boolean networks, differential equations and stochastic simulations in a framework that acknowledges the typical sorts of reactions found in protein regulatory networks. Applying this strategy to a comprehensive mechanism of the budding yeast cell cycle, we illustrate the potential value of standard component modeling. The deterministic version of our model reproduces the phenotypic properties of wild-type cells and of 125 mutant strains. The stochastic version of our model reproduces the cell-to-cell variability of wild-type cells and the partial viability of the CLB2-dbΔ clb5Δ mutant strain. Our simulations show that mathematical modeling with "standard components" can capture in quantitative detail many essential properties of cell cycle control in budding yeast. PMID:27187804
Quantum algorithms for testing Boolean functions
Erika Andersson
2010-06-01
Full Text Available We discuss quantum algorithms, based on the Bernstein-Vazirani algorithm, for finding which variables a Boolean function depends on. There are 2^n possible linear Boolean functions of n variables; given a linear Boolean function, the Bernstein-Vazirani quantum algorithm can deterministically identify which one of these Boolean functions we are given using just one single function query. The same quantum algorithm can also be used to learn which input variables other types of Boolean functions depend on, with a success probability that depends on the form of the Boolean function that is tested, but does not depend on the total number of input variables. We also outline a procedure to futher amplify the success probability, based on another quantum algorithm, the Grover search.
Boolean Reasoning with Graphs of Partitions
Goossens, Daniel
2010-01-01
version longue du papier court "A Dynamic Boolean Knowledge Base" accepté à ICTAI 2010. This paper presents an implemented architecture for easy learning, reorganizing and navigation into a Boolean knowledge base. As the base grows with new definitions and constraints, it is normalized by the closure of a completion operator. This normalization allows arbitrary formats for Boolean expressions. It ensures basic reasoning abilities and spontaneously organizes intermingled taxonomies of conce...
Inverse fracture network modelling
The basic problem in analyzing flow and transport in fractured rock is that the flow may be largely governed by a poorly connected network of fractures. Flow in such a system cannot be modeled with traditional modelling techniques. Fracture network models also have a limitation, in that they are based on geological data on fracture geometry even though it is known that only a small portion of fractures observed is hydraulically active. This paper discusses a new technique developed for treating the problem as well as presents a modelling example carried out to apply it. The approach is developed in Lawrence Berkeley Laboratory and it treats the fracture zone as an 'equivalent discontinuum'. The discontinuous nature of the problem is represented through flow on a partially filled lattice. An equivalent discontinuum model is constructed by adding and removing conductive elements through a statistical inverse technique called 'simulated annealing'. The fracture network model is 'annealed' until the modified systems behaves like the observed. The further development of the approach continues at LBL and in a joint LBL/VTT collaboration project the possibilities to apply the technique in Finnish conditions are investigated
Estimation of Boolean Factor Analysis Performance by Informational Gain
Frolov, A.; Húsek, Dušan; Polyakov, P.Y.
Berlin : Springer, 2010 - (Snášel, V.; Szczepaniak, P.; Abraham, A.; Kacprzyk, J.), s. 83-94 ISBN 978-3-642-10686-6. - (Advances in Intelligent and Soft Computing. 67). [AWIC 2009. Atlantic Web Intelligence Conference /6./. Prague (CZ), 09.09.2009-11.09.2009] Institutional research plan: CEZ:AV0Z10300504 Keywords : Boolean factor analysis * informational gain * Hopfield-like network Subject RIV: IN - Informatics, Computer Science
Progress in Applications of Boolean Functions
Sasao, Tsutomu
2010-01-01
This book brings together five topics on the application of Boolean functions. They are 1. Equivalence classes of Boolean functions: The number of n-variable functions is large, even for values as small as n = 6, and there has been much research on classifying functions. There are many classifications, each with their own distinct merit. 2. Boolean functions for cryptography: The process of encrypting/decrypting plain text messages often depends on Boolean functions with specific properties. For example, highly nonlinear functions are valued because they are less susceptible to linear attacks.
Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators
Drucker, Andrew
2012-01-01
We study the circuit complexity of Boolean operators, i.e., collections of Boolean functions defined over a common input. Our focus is the well-studied model in which arbitrary Boolean functions are allowed as gates, and in which a circuit's complexity is measured by its depth and number of wires. We show sharp limitations of several existing lower-bound methods for this model. First, we study an information-theoretic lower-bound method due to Cherukhin, that yields bounds of form $\\Omega_d(n...
Duality methods in networks, computer science models, and disordered condensed matter systems
Mitchell, Joseph Dan
In this thesis, I explore lattice independent duality and systems to which it can be applied. I first demonstrate classical duality on models in an external field, including the Ising, Potts, and x -- y models, showing in particular how this modifies duality to be lattice independent and applicable to networks. I then present a novel application of duality on the boolean satsifiability problem, one of the most important problems in computational complexity, through mapping to a low temperature Ising model. This establishes the equivalence between boolean satisfiability and a problem of enumerating the positive solutions to a Diophantine system of equations. I continue by combining duality with a prominent tool for models on networks, belief propagation, deriving a new message passing procedure, dual belief propagation. In the final part of my thesis, I shift to propose and examine a semiclassical model, the two-component Coulomb glass model, which can explain the giant magnetoresistance peak present in disordered films near a superconductor-insulator transition as the effect of competition between single particle and localized pair transport. I numerically analyze the density of states and transport properties of this model.
Boolean Search: Current State and Perspectives.
Frants, Valery I.; Shapiro, Jacob; Taksa, Isak; Voiskunskii, Vladimir G.
1999-01-01
Discusses the use of Boolean logic in information-retrieval systems and analyzes existing criticisms of operational systems. Considers users' ability to use and understand Boolean operators, ranking, the quality of query formulations, and negative effects of criticism; and concludes that criticism is directed at the methodology employed in…
Version Spaces and Generalized Monotone Boolean Functions
J.C. Bioch (Cor); T. Ibaraki
2002-01-01
textabstractWe consider generalized monotone functions f: X --> {0,1} defined for an arbitrary binary relation <= on X by the property x <= y implies f(x) <= f(y). These include the standard monotone (or positive) Boolean functions, regular Boolean functions and other interesting functions as speci
Coevolutionary modeling in network formation
Al-Shyoukh, Ibrahim
2014-12-03
Network coevolution, the process of network topology evolution in feedback with dynamical processes over the network nodes, is a common feature of many engineered and natural networks. In such settings, the change in network topology occurs at a comparable time scale to nodal dynamics. Coevolutionary modeling offers the possibility to better understand how and why network structures emerge. For example, social networks can exhibit a variety of structures, ranging from almost uniform to scale-free degree distributions. While current models of network formation can reproduce these structures, coevolutionary modeling can offer a better understanding of the underlying dynamics. This paper presents an overview of recent work on coevolutionary models of network formation, with an emphasis on the following three settings: (i) dynamic flow of benefits and costs, (ii) transient link establishment costs, and (iii) latent preferential attachment.
Goldberg, S R; Evans, T S
2014-01-01
The distribution of the number of academic publications as a function of citation count for a given year is remarkably similar from year to year. We measure this similarity as a width of the distribution and find it to be approximately constant from year to year. We show that simple citation models fail to capture this behaviour. We then provide a simple three parameter citation network model using a mixture of local and global search processes which can reproduce the correct distribution over time. We use the citation network of papers from the hep-th section of arXiv to test our model. For this data, around 20% of citations use global information to reference recently published papers, while the remaining 80% are found using local searches. We note that this is consistent with other studies though our motivation is very different from previous work. Finally, we also find that the fluctuations in the size of an academic publication's bibliography is important for the model. This is not addressed in most mode...
A Network Synthesis Model for Generating Protein Interaction Network Families
Sayed Mohammad Ebrahim Sahraeian; Byung-Jun Yoon
2012-01-01
In this work, we introduce a novel network synthesis model that can generate families of evolutionarily related synthetic protein-protein interaction (PPI) networks. Given an ancestral network, the proposed model generates the network family according to a hypothetical phylogenetic tree, where the descendant networks are obtained through duplication and divergence of their ancestors, followed by network growth using network evolution models. We demonstrate that this network synthesis model ca...
Network model with structured nodes
Frisco, Pierluigi
2011-08-01
We present a network model in which words over a specific alphabet, called structures, are associated to each node and undirected edges are added depending on some distance measure between different structures. This model shifts the underlying principle of network generation from a purely mathematical one to an information-based one. It is shown how this model differs from the Barábasi-Albert and duplication models and how it can generate networks with topological features similar to biological networks: power law degree distribution, low average path length, clustering coefficient independent from the network size, etc. Two biological networks: S. cerevisiae gene network and E. coli protein-protein interaction network, are replicated using this model.
Expectation-Maximization Approach to Boolean Factor Analysis
Frolov, A. A.; Húsek, Dušan; Polyakov, P.Y.
Piscataway: IEEE, 2011, s. 559-566. ISBN 978-1-4244-9636-5. [IJCNN 2011. International Joint Conference on Neural Networks. San Jose (US), 31.07.2011-05.08.2011] R&D Projects: GA ČR GAP202/10/0262; GA ČR GA205/09/1079; GA MŠk(CZ) 1M0567 Institutional research plan: CEZ:AV0Z10300504 Keywords : Boolean factor analysis * bars problem * dendritic inhibition * expectation-maximization * neural network application * statistics Subject RIV: IN - Informatics, Computer Science
A neighbourhood evolving network model
Many social, technological, biological and economical systems are best described by evolved network models. In this short Letter, we propose and study a new evolving network model. The model is based on the new concept of neighbourhood connectivity, which exists in many physical complex networks. The statistical properties and dynamics of the proposed model is analytically studied and compared with those of Barabasi-Albert scale-free model. Numerical simulations indicate that this network model yields a transition between power-law and exponential scaling, while the Barabasi-Albert scale-free model is only one of its special (limiting) cases. Particularly, this model can be used to enhance the evolving mechanism of complex networks in the real world, such as some social networks development
Mining and modeling character networks
Bonato, Anthony; Elenberg, Ethan R; Gleich, David F; Hou, Yangyang
2016-01-01
We investigate social networks of characters found in cultural works such as novels and films. These character networks exhibit many of the properties of complex networks such as skewed degree distribution and community structure, but may be of relatively small order with a high multiplicity of edges. Building on recent work of beveridge, we consider graph extraction, visualization, and network statistics for three novels: Twilight by Stephanie Meyer, Steven King's The Stand, and J.K. Rowling's Harry Potter and the Goblet of Fire. Coupling with 800 character networks from films found in the http://moviegalaxies.com/ database, we compare the data sets to simulations from various stochastic complex networks models including random graphs with given expected degrees (also known as the Chung-Lu model), the configuration model, and the preferential attachment model. Using machine learning techniques based on motif (or small subgraph) counts, we determine that the Chung-Lu model best fits character networks and we ...
Mining TCGA data using Boolean implications.
Subarna Sinha
Full Text Available Boolean implications (if-then rules provide a conceptually simple, uniform and highly scalable way to find associations between pairs of random variables. In this paper, we propose to use Boolean implications to find relationships between variables of different data types (mutation, copy number alteration, DNA methylation and gene expression from the glioblastoma (GBM and ovarian serous cystadenoma (OV data sets from The Cancer Genome Atlas (TCGA. We find hundreds of thousands of Boolean implications from these data sets. A direct comparison of the relationships found by Boolean implications and those found by commonly used methods for mining associations show that existing methods would miss relationships found by Boolean implications. Furthermore, many relationships exposed by Boolean implications reflect important aspects of cancer biology. Examples of our findings include cis relationships between copy number alteration, DNA methylation and expression of genes, a new hierarchy of mutations and recurrent copy number alterations, loss-of-heterozygosity of well-known tumor suppressors, and the hypermethylation phenotype associated with IDH1 mutations in GBM. The Boolean implication results used in the paper can be accessed at http://crookneck.stanford.edu/microarray/TCGANetworks/.
Generalizing Boolean Satisfiability II: Theory
Dixon, H E; Luks, E M; Parkes, A J; 10.1613/jair.1555
2011-01-01
This is the second of three planned papers describing ZAP, a satisfiability engine that substantially generalizes existing tools while retaining the performance characteristics of modern high performance solvers. The fundamental idea underlying ZAP is that many problems passed to such engines contain rich internal structure that is obscured by the Boolean representation used; our goal is to define a representation in which this structure is apparent and can easily be exploited to improve computational performance. This paper presents the theoretical basis for the ideas underlying ZAP, arguing that existing ideas in this area exploit a single, recurring structure in that multiple database axioms can be obtained by operating on a single axiom using a subgroup of the group of permutations on the literals in the problem. We argue that the group structure precisely captures the general structure at which earlier approaches hinted, and give numerous examples of its use. We go on to extend the Davis-Putnam-Logemann-...
Local Correction of Boolean Functions
Alon, Noga
2011-01-01
A Boolean function f over n variables is said to be q-locally correctable if, given a black-box access to a function g which is "close" to an isomorphism f_sigma of f, we can compute f_sigma(x) for any x in Z_2^n with good probability using q queries to g. We observe that any k-junta, that is, any function which depends only on k of its input variables, is O(2^k)-locally correctable. Moreover, we show that there are examples where this is essentially best possible, and locally correcting some k-juntas requires a number of queries which is exponential in k. These examples, however, are far from being typical, and indeed we prove that for almost every k-junta, O(k log k) queries suffice.
Boolean Delay Equations: A simple way of looking at complex systems
Ghil, Michael; Zaliapin, Ilya; Coluzzi, Barbara
2006-01-01
Boolean Delay Equations (BDEs) are semi-discrete dynamical models with Boolean-valued variables that evolve in continuous time. Systems of BDEs can be classified into conservative or dissipative, in a manner that parallels the classification of ordinary or partial differential equations. Solutions to certain conservative BDEs exhibit growth of complexity in time. They represent therewith metaphors for biological evolution or human history. Dissipative BDEs are structurally stable and exhibit ...
Analysis of Boolean Functions based on Interaction Graphs and their influence in System Biology
Das, Jayanta Kumar; Rout, Ranjeet Kumar; Choudhury, Pabitra Pal
2014-01-01
Interaction graphs provide an important qualitative modeling approach for System Biology. This paper presents a novel approach for construction of interaction graph with the help of Boolean function decomposition. Each decomposition part (Consisting of 2-bits) of the Boolean functions has some important significance. In the dynamics of a biological system, each variable or node is nothing but gene or protein. Their regulation has been explored in terms of interaction graphs which are generate...
Translating Pseudo-Boolean Constraints into CNF
Aavani, Amir
2011-01-01
A Pseudo-Boolean constraint is a linear constraint over Boolean variables. This kind of constraints has been widely used in expressing NP-complete problems. This paper introduces a new algorithm for translating Pseudo-Boolean constraints into CNF clauses. The CNF produced by the proposed encoding has small size, and we also characterize the constraints for which one can expect the SAT solvers to perform well on the produced CNF. We show that there are many constraints for which the proposed encoding has a good performance.
Modeling Dynamics of Information Networks
Rosvall, Martin; Sneppen, Kim
2003-01-01
We propose an information-based model for network dynamics in which imperfect information leads to networks where the different vertices have widely different number of edges to other vertices, and where the topology has hierarchical features. The possibility to observe scale free networks is linked to a minimally connected system where hubs remain dynamic.
Boolean Logic with Fault Tolerant Coding
Alagoz, B. Baykant
2009-01-01
Error detectable and error correctable coding in Hamming space was researched to discover possible fault tolerant coding constellations, which can implement Boolean logic with fault tolerant property. Basic logic operators of the Boolean algebra were developed to apply fault tolerant coding in the logic circuits. It was shown that application of three-bit fault tolerant codes have provided the digital system skill of auto-recovery without need for designing additional-fault tolerance mechanisms.
Sensitivity versus block sensitivity of Boolean functions
Virza, Madars
2010-01-01
Determining relationship between sensitivity and block sensitivity of Boolean functions is of interest for computational complexity theory. We construct a sequence of Boolean functions with bs(f) = 1/2 (s(f))^2+ 1/2 s(f). The best known separation previously was bs(f) = 1/2 (s(f))^2 due to Rubinstein (1995). We also report results of computer search for functions with at most 12 variables.
Developing Personal Network Business Models
Saugstrup, Dan; Henten, Anders
2006-01-01
The aim of the paper is to examine the issue of business modeling in relation to personal networks, PNs. The paper builds on research performed on business models in the EU 1ST MAGNET1 project (My personal Adaptive Global NET). The paper presents the Personal Network concept and briefly reports on...
Complex Networks in Psychological Models
Wedemann, R. S.; Carvalho, L. S. A. V. D.; Donangelo, R.
We develop schematic, self-organizing, neural-network models to describe mechanisms associated with mental processes, by a neurocomputational substrate. These models are examples of real world complex networks with interesting general topological structures. Considering dopaminergic signal-to-noise neuronal modulation in the central nervous system, we propose neural network models to explain development of cortical map structure and dynamics of memory access, and unify different mental processes into a single neurocomputational substrate. Based on our neural network models, neurotic behavior may be understood as an associative memory process in the brain, and the linguistic, symbolic associative process involved in psychoanalytic working-through can be mapped onto a corresponding process of reconfiguration of the neural network. The models are illustrated through computer simulations, where we varied dopaminergic modulation and observed the self-organizing emergent patterns at the resulting semantic map, interpreting them as different manifestations of mental functioning, from psychotic through to normal and neurotic behavior, and creativity.
Internet Network Resource Information Model
陈传峰; 李增智; 唐亚哲; 刘康平
2002-01-01
The foundation of any network management systens is a database that con-tains information about the network resources relevant to the management tasks. A networkinformation model is an abstraction of network resources, including both managed resources andmanaging resources. In the SNMP-based management framework, management information isdefined almost exclusively from a "device" viewpoint, namely, managing a network is equiva-lent to managing a collection of individual nodes. Aiming at making use of recent advances indistributed computing and in object-oriented analysis and design, the Internet management ar-chitecture can also be based on the Open Distributed Processing Reference Model (RM-ODP).The purpose of this article is to provide an Internet Network Resource Information Model.First, a layered management information architecture will be discussed. Then the Internetnetwork resource information model is presented. The information model is specified usingObject-Z.
Telecommunications network modelling, planning and design
Evans, Sharon
2003-01-01
Telecommunication Network Modelling, Planning and Design addresses sophisticated modelling techniques from the perspective of the communications industry and covers some of the major issues facing telecommunications network engineers and managers today. Topics covered include network planning for transmission systems, modelling of SDH transport network structures and telecommunications network design and performance modelling, as well as network costs and ROI modelling and QoS in 3G networks.
Modeling of fluctuating reaction networks
Full Text:Various dynamical systems are organized as reaction networks, where the population size of one component affects the populations of all its neighbors. Such networks can be found in interstellar surface chemistry, cell biology, thin film growth and other systems. I cases where the populations of reactive species are large, the network can be modeled by rate equations which provide all reaction rates within mean field approximation. However, in small systems that are partitioned into sub-micron size, these populations strongly fluctuate. Under these conditions rate equations fail and the master equation is needed for modeling these reactions. However, the number of equations in the master equation grows exponentially with the number of reactive species, severely limiting its feasibility for complex networks. Here we present a method which dramatically reduces the number of equations, thus enabling the incorporation of the master equation in complex reaction networks. The method is examplified in the context of reaction network on dust grains. Its applicability for genetic networks will be discussed. 1. Efficient simulations of gas-grain chemistry in interstellar clouds. Azi Lipshtat and Ofer Biham, Phys. Rev. Lett. 93 (2004), 170601. 2. Modeling of negative autoregulated genetic networks in single cells. Azi Lipshtat, Hagai B. Perets, Nathalie Q. Balaban and Ofer Biham, Gene: evolutionary genomics (2004), In press
Neural network modeling of emotion
Levine, Daniel S.
2007-03-01
This article reviews the history and development of computational neural network modeling of cognitive and behavioral processes that involve emotion. The exposition starts with models of classical conditioning dating from the early 1970s. Then it proceeds toward models of interactions between emotion and attention. Then models of emotional influences on decision making are reviewed, including some speculative (not and not yet simulated) models of the evolution of decision rules. Through the late 1980s, the neural networks developed to model emotional processes were mainly embodiments of significant functional principles motivated by psychological data. In the last two decades, network models of these processes have become much more detailed in their incorporation of known physiological properties of specific brain regions, while preserving many of the psychological principles from the earlier models. Most network models of emotional processes so far have dealt with positive and negative emotion in general, rather than specific emotions such as fear, joy, sadness, and anger. But a later section of this article reviews a few models relevant to specific emotions: one family of models of auditory fear conditioning in rats, and one model of induced pleasure enhancing creativity in humans. Then models of emotional disorders are reviewed. The article concludes with philosophical statements about the essential contributions of emotion to intelligent behavior and the importance of quantitative theories and models to the interdisciplinary enterprise of understanding the interactions of emotion, cognition, and behavior.
Duality theories for Boolean algebras with operators
Givant, Steven
2014-01-01
In this new text, Steven Givant—the author of several acclaimed books, including works co-authored with Paul Halmos and Alfred Tarski—develops three theories of duality for Boolean algebras with operators. Givant addresses the two most recognized dualities (one algebraic and the other topological) and introduces a third duality, best understood as a hybrid of the first two. This text will be of interest to graduate students and researchers in the fields of mathematics, computer science, logic, and philosophy who are interested in exploring special or general classes of Boolean algebras with operators. Readers should be familiar with the basic arithmetic and theory of Boolean algebras, as well as the fundamentals of point-set topology.
Algorithms for Boolean Function Query Properties
Aaronson, Scott
2001-01-01
We present new algorithms to compute fundamental properties of a Boolean function given in truth-table form. Specifically, we give an O(N^2.322 log N) algorithm for block sensitivity, an O(N^1.585 log N) algorithm for `tree decomposition,' and an O(N) algorithm for `quasisymmetry.' These algorithms are based on new insights into the structure of Boolean functions that may be of independent interest. We also give a subexponential-time algorithm for the space-bounded quantum query complexity of...
A finite alternation result for reversible boolean circuits
Selinger, Peter
2016-01-01
We say that a reversible boolean function on n bits has alternation depth d if it can be written as the sequential composition of d reversible boolean functions, each of which acts only on the top n-1 bits or on the bottom n-1 bits. We show that every reversible boolean function of n >= 4 bits has alternation depth 9.
Simplified models of biological networks.
Sneppen, Kim; Krishna, Sandeep; Semsey, Szabolcs
2010-01-01
The function of living cells is controlled by complex regulatory networks that are built of a wide diversity of interacting molecular components. The sheer size and intricacy of molecular networks of even the simplest organisms are obstacles toward understanding network functionality. This review discusses the achievements and promise of a bottom-up approach that uses well-characterized subnetworks as model systems for understanding larger networks. It highlights the interplay between the structure, logic, and function of various types of small regulatory circuits. The bottom-up approach advocates understanding regulatory networks as a collection of entangled motifs. We therefore emphasize the potential of negative and positive feedback, as well as their combinations, to generate robust homeostasis, epigenetics, and oscillations. PMID:20192769
Advances in theoretical models of network science
FANG Jin-qing; BI Qiao; LI Yong
2007-01-01
In this review article, we will summarize the main advances in network science investigated by the CIAE Group of Complex Network in this field. Several theoretical models of network science were proposed and their topological and dynamical properties are reviewed and compared with the other models. Our models mainly include a harmonious unifying hybrid preferential model, a large unifying hybrid network model, a quantum interference network, a hexagonal nanowire network, and a small-world network with the same degree. The models above reveal some new phenomena and findings, which are useful for deeply understanding and investigating complex networks and their applications.
Security models for heterogeneous networking.
Mapp, Glenford E.; Aiash, Mahdi; Lasebae, Aboubaker; Phan, Raphael
2010-01-01
Security for Next Generation Networks (NGNs) is an attractive topic for many research groups. The Y-Comm security group believes that a new security approach is needed to address the security challenges in 4G networks. This paper sheds light on our approach of providing security for the Y-Comm architecture as an example of 4G communication frameworks. Our approach proposes a four-layer security integrated module to protect data and three targeted security models to protect different network e...
Comparison of Seven Methods for Boolean Factor Analysis and Their Evaluation by Information Gain
Frolov, A.; Húsek, Dušan; Polyakov, P.Y.
2016-01-01
Roč. 27, č. 3 (2016), s. 538-550. ISSN 2162-237X R&D Projects: GA MŠk ED1.1.00/02.0070 Institutional support: RVO:67985807 Keywords : associative memory * bars problem (BP) * Boolean factor analysis (BFA) * data mining * dimension reduction * Hebbian learning rule * information gain * likelihood maximization (LM) * neural network application * recurrent neural network * statistics Subject RIV: IN - Informatics, Computer Science Impact factor: 4.291, year: 2014
A Multilayer Model of Computer Networks
Shchurov, Andrey A.
2015-01-01
The fundamental concept of applying the system methodology to network analysis declares that network architecture should take into account services and applications which this network provides and supports. This work introduces a formal model of computer networks on the basis of the hierarchical multilayer networks. In turn, individual layers are represented as multiplex networks. The concept of layered networks provides conditions of top-down consistency of the model. Next, we determined the...
Some Aspects of Boolean Valued Analysis
Kusraev, A. G.; Kutateladze, S. S.
2015-01-01
This is a survey of some recent applications of Boolean valued analysis to operator theory and harmonic analysis. Under consideration are pseudoembedding operators, the noncommutative Wickstead problem, the Radon-Nikodym Theorem for JB-algebras, and the Bochner Theorem for lattice-valued positive definite mappings on locally compact groups.
Demonstrating Boolean Logic Using Simple Electrical Circuits
McElhaney, Kevin W.
2004-01-01
While exploring the subject of geometric proofs, boolean logic operators AND and OR can be used to allow students to visualize their true-or-false patterns. An activity in the form of constructing electrical circuits is illustrated to explain the concept.
Boolean Queries Optimization by Genetic Algorithms
Húsek, Dušan; Owais, S.S.J.; Krömer, P.; Snášel, Václav
2005-01-01
Roč. 15, - (2005), s. 395-409. ISSN 1210-0552 R&D Projects: GA AV ČR 1ET100300414 Institutional research plan: CEZ:AV0Z10300504 Keywords : evolutionary algorithms * genetic algorithms * genetic programming * information retrieval * Boolean query Subject RIV: BB - Applied Statistics, Operational Research
Evolutionary Algorithms for Boolean Queries Optimization
Húsek, Dušan; Snášel, Václav; Neruda, Roman; Owais, S.S.J.; Krömer, P.
2006-01-01
Roč. 3, č. 1 (2006), s. 15-20. ISSN 1790-0832 R&D Projects: GA AV ČR 1ET100300414 Institutional research plan: CEZ:AV0Z10300504 Keywords : evolutionary algorithms * genetic algorithms * information retrieval * Boolean query Subject RIV: BA - General Mathematics
A complexity theory based on Boolean algebra
Skyum, Sven; Valiant, Leslie
1985-01-01
A projection of a Boolean function is a function obtained by substituting for each of its variables a variable, the negation of a variable, or a constant. Reducibilities among computational problems under this relation of projection are considered. It is shown that much of what is of everyday rel...
A Boolean Map Theory of Visual Attention
Huang, Liqiang; Pashler, Harold
2007-01-01
A theory is presented that attempts to answer two questions. What visual contents can an observer consciously access at one moment? Answer: only one feature value (e.g., green) per dimension, but those feature values can be associated (as a group) with multiple spatially precise locations (comprising a single labeled Boolean map). How can an…
Discrete Logic Modelling Optimization to Contextualize Prior Knowledge Networks Using PRUNET.
Rodriguez, Ana; Crespo, Isaac; Androsova, Ganna; del Sol, Antonio
2015-01-01
High-throughput technologies have led to the generation of an increasing amount of data in different areas of biology. Datasets capturing the cell's response to its intra- and extra-cellular microenvironment allows such data to be incorporated as signed and directed graphs or influence networks. These prior knowledge networks (PKNs) represent our current knowledge of the causality of cellular signal transduction. New signalling data is often examined and interpreted in conjunction with PKNs. However, different biological contexts, such as cell type or disease states, may have distinct variants of signalling pathways, resulting in the misinterpretation of new data. The identification of inconsistencies between measured data and signalling topologies, as well as the training of PKNs using context specific datasets (PKN contextualization), are necessary conditions to construct reliable, predictive models, which are current challenges in the systems biology of cell signalling. Here we present PRUNET, a user-friendly software tool designed to address the contextualization of a PKNs to specific experimental conditions. As the input, the algorithm takes a PKN and the expression profile of two given stable steady states or cellular phenotypes. The PKN is iteratively pruned using an evolutionary algorithm to perform an optimization process. This optimization rests in a match between predicted attractors in a discrete logic model (Boolean) and a Booleanized representation of the phenotypes, within a population of alternative subnetworks that evolves iteratively. We validated the algorithm applying PRUNET to four biological examples and using the resulting contextualized networks to predict missing expression values and to simulate well-characterized perturbations. PRUNET constitutes a tool for the automatic curation of a PKN to make it suitable for describing biological processes under particular experimental conditions. The general applicability of the implemented algorithm
Discrete Logic Modelling Optimization to Contextualize Prior Knowledge Networks Using PRUNET.
Ana Rodriguez
Full Text Available High-throughput technologies have led to the generation of an increasing amount of data in different areas of biology. Datasets capturing the cell's response to its intra- and extra-cellular microenvironment allows such data to be incorporated as signed and directed graphs or influence networks. These prior knowledge networks (PKNs represent our current knowledge of the causality of cellular signal transduction. New signalling data is often examined and interpreted in conjunction with PKNs. However, different biological contexts, such as cell type or disease states, may have distinct variants of signalling pathways, resulting in the misinterpretation of new data. The identification of inconsistencies between measured data and signalling topologies, as well as the training of PKNs using context specific datasets (PKN contextualization, are necessary conditions to construct reliable, predictive models, which are current challenges in the systems biology of cell signalling. Here we present PRUNET, a user-friendly software tool designed to address the contextualization of a PKNs to specific experimental conditions. As the input, the algorithm takes a PKN and the expression profile of two given stable steady states or cellular phenotypes. The PKN is iteratively pruned using an evolutionary algorithm to perform an optimization process. This optimization rests in a match between predicted attractors in a discrete logic model (Boolean and a Booleanized representation of the phenotypes, within a population of alternative subnetworks that evolves iteratively. We validated the algorithm applying PRUNET to four biological examples and using the resulting contextualized networks to predict missing expression values and to simulate well-characterized perturbations. PRUNET constitutes a tool for the automatic curation of a PKN to make it suitable for describing biological processes under particular experimental conditions. The general applicability of the
Target-Centric Network Modeling
Mitchell, Dr. William L.; Clark, Dr. Robert M.
In Target-Centric Network Modeling: Case Studies in Analyzing Complex Intelligence Issues, authors Robert Clark and William Mitchell take an entirely new approach to teaching intelligence analysis. Unlike any other book on the market, it offers case study scenarios using actual intelligence...... reporting formats, along with a tested process that facilitates the production of a wide range of analytical products for civilian, military, and hybrid intelligence environments. Readers will learn how to perform the specific actions of problem definition modeling, target network modeling, and...... collaborative sharing in the process of creating a high-quality, actionable intelligence product. The case studies reflect the complexity of twenty-first century intelligence issues by dealing with multi-layered target networks that cut across political, economic, social, technological, and military issues...
Hydraulic Modeling: Pipe Network Analysis
Datwyler, Trevor T.
2012-01-01
Water modeling is becoming an increasingly important part of hydraulic engineering. One application of hydraulic modeling is pipe network analysis. Using programmed algorithms to repeatedly solve continuity and energy equations, computer software can greatly reduce the amount of time required to analyze a closed conduit system. Such hydraulic models can become a valuable tool for cities to maintain their water systems and plan for future growth. The Utah Division of Drinking Water regulations...
Spatial Models for Virtual Networks
Janssen, Jeannette
This paper discusses the use of spatial graph models for the analysis of networks that do not have a direct spatial reality, such as web graphs, on-line social networks, or citation graphs. In a spatial graph model, nodes are embedded in a metric space, and link formation depends on the relative position of nodes in the space. It is argued that spatial models form a good basis for link mining: assuming a spatial model, the link information can be used to infer the spatial position of the nodes, and this information can then be used for clustering and recognition of node similarity. This paper gives a survey of spatial graph models, and discusses their suitability for link mining.
Ising model for distribution networks
Hooyberghs, H; Giuraniuc, C; Van Schaeybroeck, B; Indekeu, J O
2012-01-01
An elementary Ising spin model is proposed for demonstrating cascading failures (break-downs, blackouts, collapses, avalanches, ...) that can occur in realistic networks for distribution and delivery by suppliers to consumers. A ferromagnetic Hamiltonian with quenched random fields results from policies that maximize the gap between demand and delivery. Such policies can arise in a competitive market where firms artificially create new demand, or in a solidary environment where too high a demand cannot reasonably be met. Network failure in the context of a policy of solidarity is possible when an initially active state becomes metastable and decays to a stable inactive state. We explore the characteristics of the demand and delivery, as well as the topological properties, which make the distribution network susceptible of failure. An effective temperature is defined, which governs the strength of the activity fluctuations which can induce a collapse. Numerical results, obtained by Monte Carlo simulations of t...
Boolean representations of simplicial complexes and matroids
Rhodes, John
2015-01-01
This self-contained monograph explores a new theory centered around boolean representations of simplicial complexes leading to a new class of complexes featuring matroids as central to the theory. The book illustrates these new tools to study the classical theory of matroids as well as their important geometric connections. Moreover, many geometric and topological features of the theory of matroids find their counterparts in this extended context. Graduate students and researchers working in the areas of combinatorics, geometry, topology, algebra and lattice theory will find this monograph appealing due to the wide range of new problems raised by the theory. Combinatorialists will find this extension of the theory of matroids useful as it opens new lines of research within and beyond matroids. The geometric features and geometric/topological applications will appeal to geometers. Topologists who desire to perform algebraic topology computations will appreciate the algorithmic potential of boolean represent...
Fast Vertical Mining Using Boolean Algebra
Hosny M. Ibrahim
2015-01-01
Full Text Available The vertical association rules mining algorithm is an efficient mining method, which makes use of support sets of frequent itemsets to calculate the support of candidate itemsets. It overcomes the disadvantage of scanning database many times like Apriori algorithm. In vertical mining, frequent itemsets can be represented as a set of bit vectors in memory, which enables for fast computation. The sizes of bit vectors for itemsets are the main space expense of the algorithm that restricts its expansibility. Therefore, in this paper, a proposed algorithm that compresses the bit vectors of frequent itemsets will be presented. The new bit vector schema presented here depends on Boolean algebra rules to compute the intersection of two compressed bit vectors without making any costly decompression operation. The experimental results show that the proposed algorithm, Vertical Boolean Mining (VBM algorithm is better than both Apriori algorithm and the classical vertical association rule mining algorithm in the mining time and the memory usage.
Meghabghab, George
2001-01-01
Discusses the evaluation of search engines and uses neural networks in stochastic simulation of the number of rejected Web pages per search query. Topics include the iterative radial basis functions (RBF) neural network; precision; response time; coverage; Boolean logic; regression models; crawling algorithms; and implications for search engine…
Efficient Analog Circuits for Boolean Satisfiability
Yin, Xunzhao; Sedighi, Behnam; Varga, Melinda; Ercsey-Ravasz, Maria; Toroczkai, Zoltan; Hu, Xiaobo Sharon
2016-01-01
Efficient solutions to NP-complete problems would significantly benefit both science and industry. However, such problems are intractable on digital computers based on the von Neumann architecture, thus creating the need for alternative solutions to tackle such problems. Recently, a deterministic, continuous-time dynamical system (CTDS) was proposed (Nature Physics, 7(12), 966 (2011)) to solve a representative NP-complete problem, Boolean Satisfiability (SAT). This solver shows polynomial ana...
Using Genetic Algorithms for Boolean Queries Optimization
Húsek, Dušan; Snášel, Václav; Owais, S.S.J.; Krömer, P.
Calgary: ACTA Press, 2005 - (Hamza, M.), s. 178-184 ISBN 0-88986-510-8. [IASTED International Conference on Internet and Multimedia Systems and Applications /9./. Honolulu (US), 15.08.2005-17.08.2005] R&D Projects: GA AV ČR 1ET100300419 Institutional research plan: CEZ:AV0Z10300504 Keywords : genetic algorithms * information retrieval * Boolean query * genetic programming Subject RIV: BA - General Mathematics
On the Implementation of Boolean Matrix Factorization
Snášel, V.; Krömer, P.; Platoš, J.; Húsek, Dušan
Los Alamitos: IEEE, 2008, s. 554-558. ISBN 978-0-7695-3299-8. [ETID '08. International Workshop on Evolutionary Techniques /2./, in collocation with DEXA 2008 International Conference /19./. Turin (IT), 01.09.2008-05.09.2008] Institutional research plan: CEZ:AV0Z10300504 Keywords : data mining * genetic algorithms * Boolean factorization * binary data * machine learning * feature extraction Subject RIV: IN - Informatics, Computer Science
Nonparametric Bayesian Modeling of Complex Networks
Schmidt, Mikkel Nørgaard; Mørup, Morten
2013-01-01
Modeling structure in complex networks using Bayesian nonparametrics makes it possible to specify flexible model structures and infer the adequate model complexity from the observed data. This article provides a gentle introduction to nonparametric Bayesian modeling of complex networks: Using...... for complex networks can be derived and point out relevant literature....
Research on the model of home networking
Yun, Xiang; Feng, Xiancheng
2007-11-01
It is the research hotspot of current broadband network to combine voice service, data service and broadband audio-video service by IP protocol to transport various real time and mutual services to terminal users (home). Home Networking is a new kind of network and application technology which can provide various services. Home networking is called as Digital Home Network. It means that PC, home entertainment equipment, home appliances, Home wirings, security, illumination system were communicated with each other by some composing network technology, constitute a networking internal home, and connect with WAN by home gateway. It is a new network technology and application technology, and can provide many kinds of services inside home or between homes. Currently, home networking can be divided into three kinds: Information equipment, Home appliances, Communication equipment. Equipment inside home networking can exchange information with outer networking by home gateway, this information communication is bidirectional, user can get information and service which provided by public networking by using home networking internal equipment through home gateway connecting public network, meantime, also can get information and resource to control the internal equipment which provided by home networking internal equipment. Based on the general network model of home networking, there are four functional entities inside home networking: HA, HB, HC, and HD. (1) HA (Home Access) - home networking connects function entity; (2) HB (Home Bridge) Home networking bridge connects function entity; (3) HC (Home Client) - Home networking client function entity; (4) HD (Home Device) - decoder function entity. There are many physical ways to implement four function entities. Based on theses four functional entities, there are reference model of physical layer, reference model of link layer, reference model of IP layer and application reference model of high layer. In the future home network
Mathematical Modelling Plant Signalling Networks
Muraro, D.
2013-01-01
During the last two decades, molecular genetic studies and the completion of the sequencing of the Arabidopsis thaliana genome have increased knowledge of hormonal regulation in plants. These signal transduction pathways act in concert through gene regulatory and signalling networks whose main components have begun to be elucidated. Our understanding of the resulting cellular processes is hindered by the complex, and sometimes counter-intuitive, dynamics of the networks, which may be interconnected through feedback controls and cross-regulation. Mathematical modelling provides a valuable tool to investigate such dynamics and to perform in silico experiments that may not be easily carried out in a laboratory. In this article, we firstly review general methods for modelling gene and signalling networks and their application in plants. We then describe specific models of hormonal perception and cross-talk in plants. This mathematical analysis of sub-cellular molecular mechanisms paves the way for more comprehensive modelling studies of hormonal transport and signalling in a multi-scale setting. © EDP Sciences, 2013.