WorldWideScience

Sample records for boolean algebra

  1. Algebraic partial Boolean algebras

    Energy Technology Data Exchange (ETDEWEB)

    Smith, Derek [Math Department, Lafayette College, Easton, PA 18042 (United States)

    2003-04-04

    Partial Boolean algebras, first studied by Kochen and Specker in the 1960s, provide the structure for Bell-Kochen-Specker theorems which deny the existence of non-contextual hidden variable theories. In this paper, we study partial Boolean algebras which are 'algebraic' in the sense that their elements have coordinates in an algebraic number field. Several of these algebras have been discussed recently in a debate on the validity of Bell-Kochen-Specker theorems in the context of finite precision measurements. The main result of this paper is that every algebraic finitely-generated partial Boolean algebra B(T) is finite when the underlying space H is three-dimensional, answering a question of Kochen and showing that Conway and Kochen's infinite algebraic partial Boolean algebra has minimum dimension. This result contrasts the existence of an infinite (non-algebraic) B(T) generated by eight elements in an abstract orthomodular lattice of height 3. We then initiate a study of higher-dimensional algebraic partial Boolean algebras. First, we describe a restriction on the determinants of the elements of B(T) that are generated by a given set T. We then show that when the generating set T consists of the rays spanning the minimal vectors in a real irreducible root lattice, B(T) is infinite just if that root lattice has an A{sub 5} sublattice. Finally, we characterize the rays of B(T) when T consists of the rays spanning the minimal vectors of the root lattice E{sub 8}.

  2. Symmetric Boolean Algebras

    OpenAIRE

    DÍaz, R.; Rivas, M.

    2010-01-01

    In order to study Boolean algebras in the category of vector spaces we introduce a prop whose algebras in set are Boolean algebras. A probabilistic logical interpretation for linear Boolean algebras is provided. An advantage of defining Boolean algebras in the linear category is that we are able to study its symmetric powers. We give explicit formulae for products in symmetric and cyclic Boolean algebras of various dimensions and formulate symmetric forms of the inclusion-exclusion principle.

  3. Boolean algebra essentials

    CERN Document Server

    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

  4. Nearly projective Boolean algebras

    CERN Document Server

    Heindorf, Lutz; Shapiro, Leonid B

    1994-01-01

    The book is a fairly complete and up-to-date survey of projectivity and its generalizations in the class of Boolean algebras. Although algebra adds its own methods and questions, many of the results presented were first proved by topologists in the more general setting of (not necessarily zero-dimensional) compact spaces. An appendix demonstrates the application of advanced set-theoretic methods to the field. The intended readers are Boolean and universal algebraists. The book will also be useful for general topologists wanting to learn about kappa-metrizable spaces and related classes. The text is practically self-contained but assumes experience with the basic concepts and techniques of Boolean algebras.

  5. Summing Boolean Algebras

    Institute of Scientific and Technical Information of China (English)

    Antonio AIZPURU; Antonio GUTI(E)RREZ-D(A)VILA

    2004-01-01

    In this paper we will study some families and subalgebras ( ) of ( )(N) that let us characterize the unconditional convergence of series through the weak convergence of subseries ∑i∈A xi, A ∈ ( ).As a consequence, we obtain a new version of the Orlicz-Pettis theorem, for Banach spaces. We also study some relationships between algebraic properties of Boolean algebras and topological properties of the corresponding Stone spaces.

  6. Boolean Algebra of C-Algebras

    Directory of Open Access Journals (Sweden)

    G.C. Rao

    2012-11-01

    Full Text Available A C- algebra is the algebraic form of the 3-valued conditional logic, which was introduced by F. Guzman and C. C. Squier in 1990. In this paper, some equivalent conditions for a C- algebra to become a boolean algebra in terms of congruences are given. It is proved that the set of all central elements B(A is isomorphic to the Boolean algebra of all C-algebras Sa, where a B(A. It is also proved that B(A is isomorphic to the Boolean algebra of all C-algebras Aa, where a B(A.

  7. Cardinal invariants on Boolean algebras

    CERN Document Server

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

  8. Boolean metric spaces and Boolean algebraic varieties

    OpenAIRE

    Avilés, Antonio

    2009-01-01

    The concepts of Boolean metric space and convex combination are used to characterize polynomial maps in a class of commutative Von Neumann regular rings including Boolean rings and p-rings, that we have called CFG-rings. In those rings, the study of the category of algebraic varieties (i.e. sets of solutions to a finite number of polynomial equations with polynomial maps as morphisms) is equivalent to the study of a class of Boolean metric spaces, that we call here CFG-spaces.

  9. Constructive version of Boolean algebra

    CERN Document Server

    Ciraulo, Francesco; Toto, Paola

    2012-01-01

    The notion of overlap algebra introduced by G. Sambin provides a constructive version of complete Boolean algebra. Here we first show some properties concerning overlap algebras: we prove that the notion of overlap morphism corresponds classically to that of map preserving arbitrary joins; we provide a description of atomic set-based overlap algebras in the language of formal topology, thus giving a predicative characterization of discrete locales; we show that the power-collection of a set is the free overlap algebra join-generated from the set. Then, we generalize the concept of overlap algebra and overlap morphism in various ways to provide constructive versions of the category of Boolean algebras with maps preserving arbitrary existing joins.

  10. The Boolean algebra and central Galois algebras

    Directory of Open Access Journals (Sweden)

    George Szeto

    2001-01-01

    Full Text Available Let B be a Galois algebra with Galois group G, Jg={b∈B∣bx=g(xb   for all   x∈B} for g∈G, and BJg=Beg for a central idempotent eg. Then a relation is given between the set of elements in the Boolean algebra (Ba,≤ generated by {0,eg∣g∈G} and a set of subgroups of G, and a central Galois algebra Be with a Galois subgroup of G is characterized for an e∈Ba.

  11. Single axioms for Boolean algebra.

    Energy Technology Data Exchange (ETDEWEB)

    McCune, W.

    2000-06-30

    Explicit single axioms are presented for Boolean algebra in terms of (1) the Sheffer stroke; (2) disjunction and negation; (3) disjunction, conjunction, and negation; and (4) disjunction, conjunction, negation, 0, and 1. It was previously known that single axioms exist for these systems, but the procedures to generate them are exponential, producing huge equations. Automated deduction techniques were applied to find axioms of lengths 105, 131, 111, and 127, respectively, each with six variables.

  12. Adjunctions between Boolean spaces and skew Boolean algebras

    CERN Document Server

    Kudryavtseva, Ganna

    2011-01-01

    We apply the representation theory of left-handed skew Boolean algebras by sections of their dual \\'{e}tale spaces, given in \\cite{K}, to construct a series of dual adjunctions between the categories of locally compact Boolean spaces and left-handed skew Boolean algebras by means of extensions of certain enriched $\\Hom$-set functors induced by objects sitting in two categories. The constructed adjunctions are "deformations" of Stone duality obtained by the replacement in the latter of the category of Boolean algebras by the category of left-handed skew Boolean algebras. The constructions provide natural settings for the $\\omega$-functor constructed in \\cite{LS} and its left adjoint functor.

  13. Duality theories for Boolean algebras with operators

    CERN Document Server

    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.

  14. Boolean-Lie algebras and the Leibniz rule

    Energy Technology Data Exchange (ETDEWEB)

    Bazso, Fueloep [KFKI Research Institute for Particle and Nuclear Physics of the Hungarian Academy of Sciences, PO Box 49, H-1525 Budapest (Hungary); Labos, Elemer [Neurobiology Research Group, United Research Organization of the Hungarian Academy of Sciences and Semmelweis University, H-1450 Budapest, PO Box 95 (Hungary)

    2006-06-02

    Using internal negations acting on Boolean functions, the notion of Boolean-Lie algebra is introduced. The underlying Lie product is the Boolean analogue of the Poisson bracket. The structure of a Boolean-Lie algebra is determined; it turns out to be solvable, but not nilpotent. We prove that the adjoint representation of an element of the Boolean-Lie algebra acts as a derivative operator on the space of Boolean functions. The adjoint representation is related to the previously known concept of the sensitivity function. Using the notion of adjoint representation we give the definition of a temporal derivative applicable to iterative dynamics of Boolean mappings.

  15. Spectra of Tukey types of ultrafilters on Boolean algebras

    OpenAIRE

    Brown, Jennifer A.; Dobrinen, Natasha

    2014-01-01

    Extending recent investigations on the structure of Tukey types of ultrafilters on $\\mathcal{P}(\\omega)$ to Boolean algebras in general, we classify the spectra of Tukey types of ultrafilters for several classes of Boolean algebras, including interval algebras, tree algebras, and pseudo-tree algebras.

  16. Soft Boolean algebra%软布尔代数

    Institute of Scientific and Technical Information of China (English)

    刘卫锋

    2013-01-01

    将软集理论应用到布尔代数中,提出了软布尔代数、软布尔子代数、软布尔代数的软理想、软理想布尔代数等概念,研究了它们的相关性质,并初步讨论了软布尔代数与几类布尔代数的模糊子代数的关系。%The soft set theory is applied to the Boolean algebra.The concepts of soft Boolean algebra, soft Boolean sub-algebra, soft ideal of soft Boolean algebra and idealistic soft Boolean algebra are presented and some related algebraic properties are discussed.The relations between soft Boolean algebra and several kinds of fuzzy subalgebras of Boolean algebra are preliminarily investigated.

  17. Short single axioms for boolean algebra.

    Energy Technology Data Exchange (ETDEWEB)

    McCune, W.; Veroff, R.; Fitelson, B.; Harris, K.; Feist, A.; Wos, L.; Mathematics and Computer Science; Univ. of New Mexico; Univ. of Wisconsin at Madison; Duke Univ.

    2002-01-01

    We present short single equational axioms for Boolean algebra in terms of disjunction and negation and in terms of the Sheffer stroke. Previously known single axioms for these theories are much longer than the ones we present. We show that there is no shorter axiom in terms of the Sheffer stroke. Automated deduction techniques were used in several parts of the work.

  18. A Short Sheffer axiom for Boolean algebra.

    Energy Technology Data Exchange (ETDEWEB)

    Veroff, R.; McCune, W.

    2000-06-30

    A short Sheffer stroke identity is shown to be a single axiom for Boolean algebra. The axiom has length 15 and 3 variables. The proof shows that it is equivalent to Sheffer's original 3-basis for the theory. Automated deduction techniques were used to find the proof. The shortest single axiom previously known to us has length 105 and 6 variables.

  19. GCD, LCM, and Boolean Algebra?

    Science.gov (United States)

    Cohen, Martin P.; Juraschek, William A.

    1976-01-01

    This article investigates the algebraic structure formed when the process of finding the greatest common divisor and the least common multiple are considered as binary operations on selected subsets of positive integers. (DT)

  20. Fast Vertical Mining Using Boolean Algebra

    Directory of Open Access Journals (Sweden)

    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.

  1. Robbins algebra : conditions that make a near-Boolean algebra Boolean.

    Energy Technology Data Exchange (ETDEWEB)

    Winker, S.; Mathematics and Computer Science

    1990-01-01

    Some problems posed years ago remain challenging today. In particular, the Robbins problem, which is still open and which is the focus of attention in this paper, offers interesting challenges for attack with the assistance of an automated reasoning program; for the study presented here, we used the program OTTER. For example, when one submits this problem, which asks for a proof that every Robbins algebra is a Boolean algebra, a large number of deduced clauses results. One must, therefore, consider the possibility that there exists a Robbins algebra that is not Boolean; such an algebra would have to be infinite. One can instead search for properties that, if adjoined to those of a Robbins algebra, guarantee that the algebra is Boolean. Here we present a number of such properties, and we show how an automated reasoning program was used to obtain the corresponding proofs. Additional properties have been identified, and we include here examples of using such a program to check that the corresponding hand-proofs are correct. We present the appropriate input for many of the examples and also include the resulting proofs in clause notation.

  2. Noise as a Boolean algebra of sigma-fields

    CERN Document Server

    Tsirelson, Boris

    2011-01-01

    The black noise of two-dimensional percolation, disclosed recently by O. Schramm, S. Smirnov and C. Garban, exceeds the limits of the existing framework based on one-dimensional intervals. A remake of the theory of noises, provided here, treats them as Boolean algebras of sigma-fields. Completeness of the Boolean algebra implies classicality, which answers an old question of J. Feldman.

  3. Construction and enumeration of Boolean functions with maximum algebraic immunity

    Institute of Scientific and Technical Information of China (English)

    ZHANG WenYing; WU ChuanKun; LIU XiangZhong

    2009-01-01

    Algebraic immunity is a new cryptographic criterion proposed against algebraic attacks. In order to resist algebraic attacks, Boolean functions used in many stream ciphers should possess high algebraic immunity. This paper presents two main results to find balanced Boolean functions with maximum algebraic immunity. Through swapping the values of two bits, and then generalizing the result to swap some pairs of bits of the symmetric Boolean function constructed by Dalai, a new class of Boolean functions with maximum algebraic immunity are constructed. Enumeration of such functions is also given. For a given function p(x) with deg(p(x)) < [n/2], we give a method to construct functions in the form p(x)+q(x) which achieve the maximum algebraic immunity, where every term with nonzero coefficient in the ANF of q(x) has degree no less than [n/2].

  4. Boolean algebraic analysis of fire protection

    Energy Technology Data Exchange (ETDEWEB)

    Hulme, B.L.; Shiver, A.W.; Slater, P.J.

    1982-01-01

    This paper describes a computational procedure which can be used to find minimum cost ways to protect the critical combinations of equipment from a single-source fire by protecting certain areas and strengthening certain barriers against fire. The procedure yields a complete set of optimum solutions by iteratively computing upper and lower bounds on the minimum cost. The fire protection sets evolve from Boolean algebraic computations which obtain minimum cost blocking sets associated with the lower bounds while the upper bounds are producd by maxflow-mincut calculations in a network.

  5. Boolean Algebra. Geometry Module for Use in a Mathematics Laboratory Setting.

    Science.gov (United States)

    Brotherton, Sheila; And Others

    This module is recommended as an honors unit to follow a unit on logic. There are four basic parts: (1) What is a Boolean Algebra; (2) Using Boolean Algebra to Prove Theorems; (3) Using Boolean Algebra to Simplify Logical Statements; and (4) Circuit Problems with Logic and Boolean Algebra. Of these, sections 1, 2, and 3 are primarily written…

  6. 布尔代数的软商布尔代数%Soft quotient Boolean algebra of Boolean algebra

    Institute of Scientific and Technical Information of China (English)

    刘卫锋

    2015-01-01

    The concepts of soft congruence relation,soft quotient algebra and soft quotient Boolean algebra of Boolean algebra are defined,and it is proved that soft congruence relation and soft ideal of Boolean algebra can be determined by each other.Then soft quotient Boolean algebra of Boolean algebra is obtained from soft proper ideal of Boolean algebra. Finally,the nature of preserving soft congruence relation of soft homomorphism of Boolean algebras is proved.%定义了布尔代数的软合同关系、软商代数和软商布尔代数等概念,证明了布尔代数的软合同关系与软理想相互确定,进而由布尔代数的软真理想得到布尔代数的软商布尔代数。最后,证明了布尔代数的软同态具有保软合同性。

  7. Noise as a Boolean algebra of sigma-fields. II. Classicality, blackness, spectrum

    CERN Document Server

    Tsirelson, Boris

    2011-01-01

    Similarly to noises, Boolean algebras of sigma-fields can be black. A noise may be treated as a homomorphism from a Boolean algebra of regular open sets to a Boolean algebra of sigma-fields. Spectral sets are useful also in this framework.

  8. On designated-weight Boolean functions with highest algebraic immunity

    Institute of Scientific and Technical Information of China (English)

    2010-01-01

    Algebraic immunity has been considered as one of cryptographically significant properties for Boolean functions. In this paper, we study ∑d-1 i=0 (ni)-weight Boolean functions with algebraic immunity achiev-ing the minimum of d and n - d + 1, which is highest for the functions. We present a simpler sufficient and necessary condition for these functions to achieve highest algebraic immunity. In addition, we prove that their algebraic degrees are not less than the maximum of d and n - d + 1, and for d = n1 +2 their nonlinearities equalthe minimum of ∑d-1 i=0 (ni) and ∑ d-1 i=0 (ni). Lastly, we identify two classes of such functions, one having algebraic degree of n or n-1.

  9. Formalization of Human Categorization Process Using Interpolative Boolean Algebra

    Directory of Open Access Journals (Sweden)

    Vladimir Dobrić

    2015-01-01

    Full Text Available Since the ancient times, it has been assumed that categorization has the basic form of classical sets. This implies that the categorization process rests on the Boolean laws. In the second half of the twentieth century, the classical theory has been challenged in cognitive science. According to the prototype theory, objects belong to categories with intensities, while humans categorize objects by comparing them to prototypes of relevant categories. Such categorization process is governed by the principles of perceived world structure and cognitive economy. Approaching the prototype theory by using truth-functional fuzzy logic has been harshly criticized due to not satisfying the complementation laws. In this paper, the prototype theory is approached by using structure-functional fuzzy logic, the interpolative Boolean algebra. The proposed formalism is within the Boolean frame. Categories are represented as fuzzy sets of objects, while comparisons between objects and prototypes are formalized by using Boolean consistent fuzzy relations. Such relations are directly constructed from a Boolean consistent fuzzy partial order relation, which is treated by Boolean implication. The introduced formalism secures the principles of categorization showing that Boolean laws are fundamental in the categorization process. For illustration purposes, the artificial cognitive system which mimics human categorization activity is proposed.

  10. Superatomic Boolean algebras constructed from strongly unbounded functions

    CERN Document Server

    Martinez, Juan Carlos

    2010-01-01

    Using Koszmider's strongly unbounded functions, we show the following consistency result: Suppose that $\\kappa,\\lambda$ are infinite cardinals such that $\\kappa^{+++} \\leq \\lambda$, $\\kappa^{_{{\\omega}_1}\\concatenation \\$ and $\\_{{\\omega}_2}\\concatenation \\$ can be cardinal sequences of superatomic Boolean algebras.

  11. On the 2m-variable symmetric Boolean functions with maximum algebraic immunity

    Institute of Scientific and Technical Information of China (English)

    QU LongJiang; LI Chao

    2008-01-01

    The properties of the 2m-variable symmetric Boolean functions with maximum al-gebraic immunity are studied in this paper. Their value vectors, algebraic normal forms, and algebraic degrees and weights are all obtained. At last, some necessary conditions for a symmetric Boolean function on even number variables to have maximum algebraic immunity are introduced.

  12. Discrete interference modeling via boolean algebra.

    Science.gov (United States)

    Beckhoff, Gerhard

    2011-01-01

    Two types of boolean functions are considered, the locus function of n variables, and the interval function of ν = n - 1 variables. A 1-1 mapping is given that takes elements (cells) of the interval function to antidual pairs of elements in the locus function, and vice versa. A set of ν binary codewords representing the intervals are defined and used to generate the codewords of all genomic regions. Next a diallelic three-point system is reviewed in the light of boolean functions, which leads to redefining complete interference by a logic function. Together with the upper bound of noninterference already defined by a boolean function, it confines the region of interference. Extensions of these two functions to any finite number of ν are straightforward, but have been also made in terms of variables taken from the inclusion-exclusion principle (expressing "at least" and "exactly equal to" a decimal integer). Two coefficients of coincidence for systems with more than three loci are defined and discussed, one using the average of several individual coefficients and the other taking as coefficient a real number between zero and one. Finally, by way of a malfunction of the mod-2 addition, it is shown that a four-point system may produce two different functions, one of which exhibiting loss of a class of odd recombinants.

  13. A complexity theory based on Boolean algebra

    DEFF Research Database (Denmark)

    Skyum, Sven; Valiant, Leslie

    1985-01-01

    relevance in Turing-machine-based complexity theory can be replicated easily and naturally in this elementary framework. Finer distinctions about the computational relationships among natural problems can be made than in previous formulations and some negative results are proved.......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...

  14. Detecting Emergent Behaviors with Semi-Boolean Algebra

    Energy Technology Data Exchange (ETDEWEB)

    Haglich, Peter [Lockheed Martin Corporation; Rouff, Christopher [Lockheed Martin Corporation; Pullum, Laura L [ORNL

    2010-01-01

    As systems continue to be interconnected, their collective behavior becomes increasingly difficult to predict. The emergent properties of systems of systems make them powerful, but at the same time make them more difficult to design, assure proper behaviors emerge, operate correctly, and have no new security holes. Learning and adaptation cause additional concerns because emergent behavior patterns simply cannot be fully predicted through the use of traditional system development methods, such as testing and model checking. In addition, self-organization can occur as the individual systems optimize to address inefficiencies in the larger system. Designing for and detecting emergent behavior is something that has not been addressed in current systems development methodologies. This paper gives background on approaches for modeling and verifying emergent behavior and then discusses the use of semi-Boolean algebra as a means for detecting emergence in combined behaviors. Semi-Boolean algebra is a generalization of the Boolean algebra concept obtained by weakening the requirement that any two elements have a common upper bound. An example is given and several ways are described that allow emergent behavior to be detected with this technique.

  15. Interval soft Boolean algebras%区间软布尔代数

    Institute of Scientific and Technical Information of China (English)

    刘卫锋; 杜迎雪; 许宏伟

    2014-01-01

    将区间软集应用于布尔代数之中,定义了区间软布尔代数、区间软布尔子代数、区间理想软布尔代数和区间软布尔代数的区间软同态等概念,并研究了它们的相关性质。推广了软布尔代数及其相关结论。%The interval soft set is applied to the Boolean algebras.The concepts of interval soft Boolean algebras, inter-val soft Boolean subalgebras, interval idealistic soft Boolean algebras and interval soft homomorphism between interval soft Boolean algebras are defined and some related properties are discussed.Soft Boolean algebras and related results are generalized.

  16. On Boolean algebras which have the Vitali-Hahn-Saks property

    Directory of Open Access Journals (Sweden)

    Dimitru Popa

    1997-05-01

    Full Text Available Given a boolean algebra A, we say when A verifies the Drewnowski condition.  In thepaper we prove that if a boolean algebra verifies the Drewnowski condition then A has the Vitali-Hahn-Saks property. Also other related questions are investigated.

  17. Boolean functions of an odd number of variables with maximum algebraic immunity

    Institute of Scientific and Technical Information of China (English)

    LI Na; QI WenFeng

    2007-01-01

    In this paper, we study Boolean functions of an odd number of variables with maximum algebraic immunity, We identify three classes of such functions, and give some necessary conditions of such functions, which help to examine whether a Boolean function of an odd number of variables has the maximum algebraic immunity. Further, some necessary conditions for such functions to have also higher nonlinearity are proposed, and a class of these functions are also obtained. Finally,we present a sufficient and necessary condition for Boolean functions of an odd number of variables to achieve maximum algebraic immunity and to be also 1-resilient.

  18. Boolean Algebra Application in Analysis of Flight Accidents

    Directory of Open Access Journals (Sweden)

    Casandra Venera BALAN

    2015-12-01

    Full Text Available Fault tree analysis is a deductive approach for resolving an undesired event into its causes, identifying the causes of a failure and providing a framework for a qualitative and quantitative evaluation of the top event. An alternative approach to fault tree analysis methods calculus goes to logical expressions and it is based on a graphical representation of the data structure for a logic - based binary decision diagram representation. In this analysis, such sites will be reduced to a minimal size and arranged in the sense that the variables appear in the same order in each path. An event can be defined as a statement that can be true or false. Therefore, Boolean algebra rules allow restructuring of a Fault Tree into one equivalent to it, but simpler.

  19. On $2k$-Variable Symmetric Boolean Functions with Maximum Algebraic Immunity $k$

    CERN Document Server

    Wang, Hui; Li, Yuan; Kan, Haibin

    2011-01-01

    Given a positive even integer $n$, it is found that the weight distribution of any $n$-variable symmetric Boolean function with maximum algebraic immunity $\\frac{n}{2}$ is determined by the binary expansion of $n$. Based on that, all $n$-variable symmetric Boolean functions with maximum algebraic immunity are constructed. The amount is $(2\\wt(n)+1)2^{\\lfloor \\log_2 n \\rfloor}$.

  20. The algebraic immunity and the optimal algebraic immunity functions of a class of correlation immune H Boolean functions

    Directory of Open Access Journals (Sweden)

    Huang Jinglian

    2016-01-01

    Full Text Available We put forward an efficient method to study the algebraic immunity of H Boolean functions with Hamming weight of 2n-1 + 2n-2, getting the existence of the higher-order algebraic immunity functions with correlation immunity. We also prove the existing problem of the above 2-order algebraic immunity functions and the optimal algebraic immunity functions. Meanwhile, we solve the compatibility of algebraic immunity and correlation immunity. What is more, the main theoretical results are verified through the examples and are revealed to be correct. Such researches are important in cryptographic primitive designs, and have significance and role in the theory and application range of cryptosystems.

  1. Constructing and Counting Even-Variable Symmetric Boolean Functions with Algebraic Immunity not Less Than $d$

    CERN Document Server

    Li, Yuan; Kan, Haibin

    2011-01-01

    In this paper, we explicitly construct a large class of symmetric Boolean functions on $2k$ variables with algebraic immunity not less than $d$, where integer $k$ is given arbitrarily and $d$ is a given suffix of $k$ in binary representation. If let $d = k$, our constructed functions achieve the maximum algebraic immunity. Remarkably, $2^{\\lfloor \\log_2{k} \\rfloor + 2}$ symmetric Boolean functions on $2k$ variables with maximum algebraic immunity are constructed, which is much more than the previous constructions. Based on our construction, a lower bound of symmetric Boolean functions with algebraic immunity not less than $d$ is derived, which is $2^{\\lfloor \\log_2{d} \\rfloor + 2(k-d+1)}$. As far as we know, this is the first lower bound of this kind.

  2. 从布尔代数到布尔微积分%From Boolean algebra to Boolean calculus

    Institute of Scientific and Technical Information of China (English)

    程代展; 赵寅; 徐相如

    2011-01-01

    布尔函数作为最简单的有限值函数具有特殊的重要性.它在包括信息、控制等许多领域有着广泛的应用.本文综合介绍有关布尔函数的理论基础.包括从布尔代数到布尔微积分的主要理论结果,它们在信息与控制中的一些重要应用,以及其前沿动态与新进展.介绍的一个重点是矩阵半张量积在这些领域的应用.%Boolean functions are of special importance, though they are the simplest class of finite-valued functions. It is widely applied to many fields, including information, control and so on. The theoretical foundation of Boolean functions is introduced in this paper, involving some main results from Boolean algebra to Boolean Calculus, applications in information and control and some recent frontiers and developments. The semi-tensor product approach to these fields is introduced emohaticallv.

  3. Fuzzy Boolean Algebras Based on Implication Operator%基于蕴涵算子上的模糊布尔代数

    Institute of Scientific and Technical Information of China (English)

    陈华新

    2011-01-01

    文中给出R-模糊布尔代数的定义,讨论了其与模糊布尔代数的关系,证明在一定的条件下,有限个R-模糊布尔代数的交(并)还是R-模糊布尔代数,R-模糊布尔代数的同态像(原像)仍是R-模糊布尔代数.%In this paper ,we introduce the definition of fuzzy Boolean algebra. Based on that, the differences and connection between R-fuzzy Boolean algebra and fuzzy Boolean algebra are discussed. Furhtermore, it is proved that the finite intersection (union) of R-fuzzy Boolean algebra is still R-fuzzy Boolean algebra , and the homomorphic image (preimage) of R-fuzzy Boolean algebra is still R-fuzzy Boolean algebra.

  4. Calculation Method for Reliability of Agricultural Distribution Power Networks while Applying Functions of Boolean Algebra

    Directory of Open Access Journals (Sweden)

    V. Rusan

    2012-01-01

    Full Text Available The paper considers calculation methods for reliability of  agricultural distribution power networks while using Boolean algebra functions and analytical method. Reliability of 10 kV overhead line circuits with automatic sectionalization points and automatic standby activation has been investigated in the paper.

  5. Extension of Boolean algebra by a Bayesian operator: application to the definition of a Deterministic Bayesian Logic

    CERN Document Server

    Dambreville, Frederic

    2011-01-01

    This work contributes to the domains of Boolean algebra and of Bayesian probability, by proposing an algebraic extension of Boolean algebras, which implements an operator for the Bayesian conditional inference and is closed under this operator. It is known since the work of Lewis (Lewis' triviality) that it is not possible to construct such conditional operator within the space of events. Nevertheless, this work proposes an answer which complements Lewis' triviality, by the construction of a conditional operator outside the space of events, thus resulting in an algebraic extension. In particular, it is proved that any probability defined on a Boolean algebra may be extended to its algebraic extension in compliance with the multiplicative definition of the conditional probability. In the last part of this paper, a new \\emph{bivalent} logic is introduced on the basis of this algebraic extension, and basic properties are derived.

  6. On (2m + 1)-variable symmetric Boolean functions with submaximum algebraic immunity 2m-1

    Institute of Scientific and Technical Information of China (English)

    2009-01-01

    All (2m +1)-variable symmetric Boolean functions with submaximal algebraic immunity 2m-1 are described and constructed. The total number of such Boolean functions is 32 ·22m-3 +3m-2 · 24 - 2 for m≥2.

  7. A Note on "On the Construction of Boolean Functions with Optimal Algebraic Immunity"

    CERN Document Server

    Li, Yuan; Kokichi, Futatsugi

    2011-01-01

    In this note, we go further on the "basis exchange" idea presented in \\cite{LiNa1} by using Mobious inversion. We show that the matrix $S_1(f)S_0(f)^{-1}$ has a nice form when $f$ is chosen to be the majority function, where $S_1(f)$ is the matrix with row vectors $\\upsilon_k(\\alpha)$ for all $\\alpha \\in 1_f$ and $S_0(f)=S_1(f\\oplus1)$. And an exact counting for Boolean functions with maximum algebraic immunity by exchanging one point in on-set with one point in off-set of the majority function is given. Furthermore, we present a necessary condition according to weight distribution for Boolean functions to achieve algebraic immunity not less than a given number.

  8. Mathematical-logical modeling of regulations on mining safety. [Boolean algebra analysis

    Energy Technology Data Exchange (ETDEWEB)

    Fajkos, A.; Suchan, L.

    1979-09-01

    Complexity of the logical structure of mine safety regulations results from the complexity of mining problems. This complexity sometimes makes it difficult to precisely formulate mining safety regulations and to monitor their observance by the miners. It is suggested that mathematical- logical modeling can be an efficient tool in analyzing mine safety regulations. A short description of the method based on Boolean algebra, and three examples of its use in the field of mine safety regulations are presented. (2 refs.) (In Czech)

  9. Noise as a Boolean algebra of sigma-fields. III. An old question of Jacob Feldman

    CERN Document Server

    Tsirelson, Boris

    2011-01-01

    The noise-type completion C of a noise-type Boolean algebra B is generally not the same as the closure of B. As shown in Part I (Introduction, Theorem 2), C consists of all complemented elements of the closure. It appears that C is the whole closure if and only if B is classical (as defined in Part II, Sect. 1a), which is the main result of this Part III.

  10. Completely positive matrices over Boolean algebras and their CP-rank

    Directory of Open Access Journals (Sweden)

    Mohindru Preeti

    2015-04-01

    Full Text Available Drew, Johnson and Loewy conjectured that for n ≥ 4, the CP-rank of every n × n completely positive real matrix is at most [n2/4]. In this paper, we prove this conjecture for n × n completely positive matrices over Boolean algebras (finite or infinite. In addition,we formulate various CP-rank inequalities of completely positive matrices over special semirings using semiring homomorphisms.

  11. Steady state analysis of Boolean molecular network models via model reduction and computational algebra

    Science.gov (United States)

    2014-01-01

    Background A key problem in the analysis of mathematical models of molecular networks is the determination of their steady states. The present paper addresses this problem for Boolean network models, an increasingly popular modeling paradigm for networks lacking detailed kinetic information. For small models, the problem can be solved by exhaustive enumeration of all state transitions. But for larger models this is not feasible, since the size of the phase space grows exponentially with the dimension of the network. The dimension of published models is growing to over 100, so that efficient methods for steady state determination are essential. Several methods have been proposed for large networks, some of them heuristic. While these methods represent a substantial improvement in scalability over exhaustive enumeration, the problem for large networks is still unsolved in general. Results This paper presents an algorithm that consists of two main parts. The first is a graph theoretic reduction of the wiring diagram of the network, while preserving all information about steady states. The second part formulates the determination of all steady states of a Boolean network as a problem of finding all solutions to a system of polynomial equations over the finite number system with two elements. This problem can be solved with existing computer algebra software. This algorithm compares favorably with several existing algorithms for steady state determination. One advantage is that it is not heuristic or reliant on sampling, but rather determines algorithmically and exactly all steady states of a Boolean network. The code for the algorithm, as well as the test suite of benchmark networks, is available upon request from the corresponding author. Conclusions The algorithm presented in this paper reliably determines all steady states of sparse Boolean networks with up to 1000 nodes. The algorithm is effective at analyzing virtually all published models even those of moderate

  12. Principal and Boolean congruences on \\theta-valued Lukasiewicz-Moisil algebras

    CERN Document Server

    Figallo, A V

    2012-01-01

    The first system of many-valued logic was introduced by J. Lukasiewicz, his motivation was of philosophical nature as he was looking for an interpretation of the concepts of possibility and necessity. Since then, plenty of research has been developed in this area. In 1968, when Gr.C. Moisil came across Zadeh's fuzzy set theory he found the motivation he had been looking for in order to legitimate the introduction and study of infinitely-valued Lukasiewicz algebras, so he defined \\theta-valued Lukasiewicz algebras (or LM\\theta-algebras, for short) (without negation), where \\theta is the order type of a chain. In this article, our main interest is to investigate the principal and Boolean congruences and \\theta-congruences on LM\\theta-algebras. In order to do this we take into account a topological duality for these algebras obtained in (A.V. Figallo, I. Pascual, A. Ziliani, A Duality for \\theta-Valued Lukasiewicz-Moisil Algebras and Aplicattions. J. LMult- Valued Logic & Soft Computing. Vol. 16, pp 303-322....

  13. Security analysis of boolean algebra based on Zhang-Wang digital signature scheme

    Science.gov (United States)

    Zheng, Jinbin

    2014-10-01

    In 2005, Zhang and Wang proposed an improvement signature scheme without using one-way hash function and message redundancy. In this paper, we show that this scheme exits potential safety concerns through the analysis of boolean algebra, such as bitwise exclusive-or, and point out that mapping is not one to one between assembly instructions and machine code actually by means of the analysis of the result of the assembly program segment, and which possibly causes safety problems unknown to the software.

  14. Security analysis of boolean algebra based on Zhang-Wang digital signature scheme

    Energy Technology Data Exchange (ETDEWEB)

    Zheng, Jinbin, E-mail: jbzheng518@163.com [School of Mathematics and Computer Science, Long Yan University, Longyan 364012 (China)

    2014-10-06

    In 2005, Zhang and Wang proposed an improvement signature scheme without using one-way hash function and message redundancy. In this paper, we show that this scheme exits potential safety concerns through the analysis of boolean algebra, such as bitwise exclusive-or, and point out that mapping is not one to one between assembly instructions and machine code actually by means of the analysis of the result of the assembly program segment, and which possibly causes safety problems unknown to the software.

  15. The (\\lambda, \\kappa)-Freese-Nation property for boolean algebras and compacta

    CERN Document Server

    Milovich, David

    2012-01-01

    We study a two-parameter generalization of the Freese-Nation Property of boolean algebras and its order-theoretic and topological consequences. For every regular infinite \\kappa, the (\\kappa,\\kappa)-FN, the (\\kappa^+,\\kappa)-FN, and the \\kappa-FN are known to be equivalent; we show that the family of properties (\\lambda,\\mu)-FN for \\lambda>\\mu form a true two-dimensional hierarchy that is robust with respect to coproducts, retracts, and the exponential operation. The (\\kappa,\\aleph_0)-FN in particular has strong consequences for base properties of compacta (stronger still for homogeneous compacta), and these consequences have natural duals in terms of special subsets of boolean algebras. We show that the (\\kappa,\\aleph_0)-FN also leads to a generalization of the equality of weight and \\pi-character in dyadic compacta. Elementary subalgebras and their duals, elementary quotient spaces, were originally used to define the (\\lambda, \\kappa)-FN and its topological dual, which naturally generalized from Stone space...

  16. Automatd generation of models and counterexamples and its application to open questions in Ternary Boolean algebra

    Energy Technology Data Exchange (ETDEWEB)

    Winker, S.; Wos, L.

    1978-01-01

    The purposes of this paper are to answer certain previously unanswered questions in the field of Ternary Boolean algebra; to describe the method, by use of an automated theorem-proving program as an invaluable aid, by which these answers were obtained; and to give informally the characteristics of those problems to which the method can be successfully applied. The approach under study begins with known facts in the form of axioms and lemmas of the field being investigated, finds by means of certain specified inference rules new facts, and continues to reason from the expanding set of facts until the problem at hand is solved or the procedure is interrupted. The solution often takes the form of a finite model or of a counter-example to the underlying conjecture. The model and/or counterexample is generated with the aid of an already existing automated theorem-proving procedure and without any recourse to any additional programing.

  17. Ones and zeros understanding Boolean algebra digital circuits and the logic of sets

    CERN Document Server

    Gregg, John

    1998-01-01

    "Ones and Zeros explains, in lay terms, Boolean algebra, the suprisingly simple system of mathematical logic used in digital computer circuitry. Ones and Zeros follows the development of this logic system from its origins in Victorian England to its rediscovery in this century as the foundation of all modern computing machinery. Readers will learn about the interesting history of the development of symbolic logic in particular, and the often misunderstood process of mathematical invention and scientific discovery, in general. Ones and Zeros also features practical exercises with answers, real-world examples of digital circuit design, and a reading list." "Ones and Zeros will be of particular interest to software engineers who want to gain a comprehensive understanding of computer hardware." "Outstanding features include: a history of mathematical logic, an explanation of the logic of digital circuits, and hands-on exercises and examples."--Jacket.

  18. Boolean process

    Institute of Scientific and Technical Information of China (English)

    闵应骅; 李忠诚; 赵著行

    1997-01-01

    Boolean algebra successfully describes the logical behavior of a digital circuit, and has been widely used in electronic circuit design and test With the development of high speed VLSIs it is a drawback for Boolean algebra to be unable to describe circuit timing behavior. Therefore a Boolean process is defined as a family of Boolean van ables relevant to the time parameter t. A real-valued sample of a Boolean process is a waveform. Waveform functions can be manipulated formally by using mathematical tools. The distance, difference and limit of a waveform polynomial are defined, and a sufficient and necessary condition of the limit existence is presented. Based on this, the concept of sensitization is redefined precisely to demonstrate the potential and wide application possibility The new definition is very different from the traditional one, and has an impact on determining the sensitizable paths with maximum or minimum length, and false paths, and then designing and testing high performance circuits

  19. Boolean universes above Boolean models

    OpenAIRE

    Wehrung, Friedrich

    1993-01-01

    We establish several first- or second-order properties of models of first-order theories by considering their elements as atoms of a new universe of set theory, and by extending naturally any structure of Boolean model on the atoms to the whole universe. For example, complete f-rings are ``boundedly algebraically compact" in the language $( + , - , . , \\wedge , \\vee , \\leq )$, and the positive cone of a complete l-group with infinity adjoined is algebraically compact in the language $( + , \\v...

  20. Boolean reasoning the logic of boolean equations

    CERN Document Server

    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.

  1. Characterization of Boolean Algebras in Terms of Certain States of Jauch-Piron Type

    Science.gov (United States)

    Matoušek, Milan; Pták, Pavel

    2015-12-01

    Suppose that L is an orthomodular lattice (a quantum logic). We show that L is Boolean exactly if L possesses a strongly unital set of weakly Jauch-Piron states, or if L possesses a unital set of weakly positive states. We also discuss some general properties of Jauch-Piron-like states.

  2. Construction of 1-Resilient Boolean Functions with Optimal Algebraic Immunity and Good Nonlinearity

    Institute of Scientific and Technical Information of China (English)

    Sen-Shan Pan; Xiao-Tong Fu; Wei-Guo Zhangx

    2011-01-01

    This paper presents a construction for a class of 1-resilient functions with optimal algebraic immunity on an even number of variables. The construction is based on the concatenation of two balanced functions in associative classes. For some n, a part of 1-resilient functions with maximum algebraic immunity constructed in the paper can achieve almost optimal nonlinearity. Apart from their high nonlinearity, the functions reach Siegenthaler's upper bound of algebraic degree. Also a class of 1-resilient functions on any number n > 2 of variables with at least sub-optimal algebraic immunity is provided.

  3. Research on Algebraic Immunity of Vectorial Boolean Functions%向量布尔函数代数免疫性质研究

    Institute of Scientific and Technical Information of China (English)

    王永娟; 孙宇

    2013-01-01

    By discussing the algebraic degree of the annihilators of vectorial Boolean functions, it is found that the algebraic immunity of vectorial Boolean functions remains invariant after affine transformation of the input variables. And after permutation of the output variables, the algebraic immunity also remains invariant. The relations between the Hamming weight of Component functions, the algebraic immunity, Walsh spectrum and the nonlinearity of vectorial Boolean functions were also investigated.%通过讨论向量布尔函数零化子的代数次数,对向量布尔函数的代数免疫性质进行研究,得出其置换不变性,即在输入变量作仿射变换和输出变量作置换之后仍然保持不变,并得出向量布尔函数代数免疫与线性组合函数重量、Walsh谱以及非线性度之间的关系.

  4. Computing the Algebraic Immunity of Boolean Functions on the SRC-6 Reconfigurable Computer

    Science.gov (United States)

    2012-03-01

    between the truth table form of the function and its algebraic normal form. The first known Verilog implementation of a reduced transeunt triangle was... Verilog , Algebraic Attack 15. NUMBER OF PAGES 172 16. PRICE CODE 17. SECURITY CLASSIFICATION OF REPORT Unclassified 18. SECURITY...The first known Verilog implementation of a reduced transeunt triangle was developed for this conversion. This reduced form requires many fewer

  5. Boolean Operator Fuzzy Logic

    Institute of Scientific and Technical Information of China (English)

    刘叙华; 邓安生

    1994-01-01

    A new approach of operator fuzzy logic, Boolean operator fuzzy logic (BOFL) based on Boolean algebra, is presented. The resolution principle is also introduced into BOFL. BOFL is a natural generalization of classical logic and can be applied to the qualitative description of fuzzy knowledge.

  6. Dynamic Boolean Mathematics

    Science.gov (United States)

    Bossé, Michael J.; Adu-Gyamfi, Kwaku; Chandler, Kayla; Lynch-Davis, Kathleen

    2016-01-01

    Dynamic mathematical environments allow users to reify mathematical concepts through multiple representations, transform mathematical relations and organically explore mathematical properties, investigate integrated mathematics, and develop conceptual understanding. Herein, we integrate Boolean algebra, the functionalities of a dynamic…

  7. Boolean differential equations

    CERN Document Server

    Steinbach, Bernd

    2013-01-01

    The Boolean Differential Calculus (BDC) is a very powerful theory that extends the structure of a Boolean Algebra significantly. Based on a small number of definitions, many theorems have been proven. The available operations have been efficiently implemented in several software packages. There is a very wide field of applications. While a Boolean Algebra is focused on values of logic functions, the BDC allows the evaluation of changes of function values. Such changes can be explored for pairs of function values as well as for whole subspaces. Due to the same basic data structures, the BDC can

  8. Clustering Boolean Tensors

    OpenAIRE

    Metzler, S; Miettinen, P

    2015-01-01

    Tensor factorizations are computationally hard problems, and in particular, are often significantly harder than their matrix counterparts. In case of Boolean tensor factorizations -- where the input tensor and all the factors are required to be binary and we use Boolean algebra -- much of that hardness comes from the possibility of overlapping components. Yet, in many applications we are perfectly happy to partition at least one of the modes. In this paper we investigate what consequences doe...

  9. Combinatorial optimization with Boolean constraints

    Energy Technology Data Exchange (ETDEWEB)

    Hulme, B.L.; Worrell, R.B.

    1983-02-01

    This report shows how Boolean algebraic formula manipulation can be used to solve certain kinds of optimization problems. If the problem can be formulated in terms of 0 to 1 variables and if the feasible solutions can be described by a Boolean equation, then the method of this report can be used. The method generates feasible solutions algebraically as terms of a disjunctive normal form of a Boolean function. Many small sample problems are solved to illustrate the method and the practical situations in which these optimization problems arise.

  10. Nonmonotonic logics and algebras

    Institute of Scientific and Technical Information of China (English)

    CHAKRABORTY Mihir Kr; GHOSH Sujata

    2008-01-01

    Several nonmonotonie logic systems together with their algebraic semantics are discussed. NM-algebra is defined.An elegant construction of an NM-algebra starting from a Boolean algebra is described which gives rise to a few interesting algebraic issues.

  11. Boolean networks with multiexpressions and parameters.

    Science.gov (United States)

    Zou, Yi Ming

    2013-01-01

    To model biological systems using networks, it is desirable to allow more than two levels of expression for the nodes and to allow the introduction of parameters. Various modeling and simulation methods addressing these needs using Boolean models, both synchronous and asynchronous, have been proposed in the literature. However, analytical study of these more general Boolean networks models is lagging. This paper aims to develop a concise theory for these different Boolean logic-based modeling methods. Boolean models for networks where each node can have more than two levels of expression and Boolean models with parameters are defined algebraically with examples provided. Certain classes of random asynchronous Boolean networks and deterministic moduli asynchronous Boolean networks are investigated in detail using the setting introduced in this paper. The derived theorems provide a clear picture for the attractor structures of these asynchronous Boolean networks.

  12. Partial stability and stabilisation of Boolean networks

    Science.gov (United States)

    Chen, Hong-Wei; Sun, Liang-Jie; Liu, Yang

    2016-07-01

    In this paper, we investigate the stability of Boolean networks and the stabilisation of Boolean control networks with respect to part of the system's states. First, an algebraic expression of the Boolean (control) network is derived by the semi-tensor product of matrices. Then, some necessary and sufficient conditions for partial stability of Boolean networks are given. Finally, the stabilisation of Boolean control networks by a free control sequence and a state-feedback control is investigated and the respective necessary and sufficient conditions are obtained. Examples are provided to illustrate the efficiency of the obtained results.

  13. Ockham Algebras Arising from Monoids

    Institute of Scientific and Technical Information of China (English)

    T.S. Blyth; H.J. Silva; J.C. Varlet

    2001-01-01

    An Ockham algebra (L; f) is of boolean shape if its lattice reduct L is boolean and f is not the complementation. We investigate a natural construction of Ockham algebras of boolean shape from any given monoid. Of particular interest is the question of when such algebras are subdirectly irreducible. In settling this, we obtain what is probably the first example of a subdirectly irreducible Ockham algebra that does not belong to the generalized variety Kω. We also prove that every semigroup can be embedded in the monoid of endomorphisms of an Ockham algebra of boolean shape.

  14. Boolean complexes and boolean numbers

    OpenAIRE

    Tenner, Bridget Eileen

    2017-01-01

    International audience; The Bruhat order gives a poset structure to any Coxeter group. The ideal of elements in this poset having boolean principal order ideals forms a simplicial poset. This simplicial poset defines the boolean complex for the group. In a Coxeter system of rank n, we show that the boolean complex is homotopy equivalent to a wedge of (n-1)-dimensional spheres. The number of these spheres is the boolean number, which can be computed inductively from the unlabeled Coxeter syste...

  15. Boolean logic in artificial intelligence and Turing degrees of Boolean-valued sets

    Energy Technology Data Exchange (ETDEWEB)

    Cai, Maohua.

    1989-01-01

    Over the years a number of generalizations of recursion theory have been introduced and studied. In this dissertation the author presents yet another such generalization. Based on the concept of a weakly recursively presented Boolean algebra, he defines Boolean-valued sets, Boolean-valued recursive sets, and Boolean-valued recursively enumerable sets and discuss the basic relationships between a Boolean-valued set, its principal part, and its support. Then he generalizes many elementary concepts and results about recursive and recursively enumerable sets such as the s-m-n theorem, the recursion theorem, and the projection theorem, etc. to Boolean valued sets. By using finite and infinite injury arguments, he generalizes the Friedberg-Muchnik theorem, the theorem about nonrecursive low r.e. sets, the minimal pair theorem, and other results. Finally, he discusses the possible application of Boolean-valued logic in artificial intelligence, and gives an implementation of a parser for the four-valued Boolean logic.

  16. A Note on Boolean Stochastic Processes

    Science.gov (United States)

    Fidaleo, Francesco

    2015-03-01

    For the quantum stochastic processes generated by the Boolean commutation relations, we prove the following version of De Finetti Theorem: each of such Boolean processes is exchangeable if and only if it is independent and identically distributed with respect to the tail algebra.

  17. Delay synchronization of temporal Boolean networks

    Science.gov (United States)

    Wei, Qiang; Xie, Cheng-jun; Liang, Yi; Niu, Yu-jun; Lin, Da

    2016-01-01

    This paper investigates the delay synchronization between two temporal Boolean networks base on semi-tensor product method, which improve complete synchronization. Necessary and sufficient conditions for delay synchronization are drawn base on algebraic expression of temporal Boolean networks. A example is presented to show the effectiveness of theoretical analysis.

  18. Kazhdan-Lusztig polynomials of boolean elements

    CERN Document Server

    Mongelli, Pietro

    2011-01-01

    We give closed combinatorial product formulas for Kazhdan-Lusztig poynomials and their parabolic analogue of type q in the case of boolean elements, introduced in [M. Marietti, Boolean elements in Kazhdan-Lusztig theory, J. Algebra 295 (2006)], in Coxeter groups whose Coxeter graph is a tree.

  19. Boolean Inner product Spaces and Boolean Matrices

    OpenAIRE

    Gudder, Stan; Latremoliere, Frederic

    2009-01-01

    This article discusses the concept of Boolean spaces endowed with a Boolean valued inner product and their matrices. A natural inner product structure for the space of Boolean n-tuples is introduced. Stochastic boolean vectors and stochastic and unitary Boolean matrices are studied. A dimension theorem for orthonormal bases of a Boolean space is proven. We characterize the invariant stochastic Boolean vectors for a Boolean stochastic matrix and show that they can be used to reduce a unitary m...

  20. The Boolean Algebra of Cubical Areas as a Tensor Product in the Category of Semilattices with Zero

    Directory of Open Access Journals (Sweden)

    Nicolas Ninin

    2014-10-01

    Full Text Available In this paper we describe a model of concurrency together with an algebraic structure reflecting the parallel composition. For the sake of simplicity we restrict to linear concurrent programs i.e. the ones with no loops nor branching. Such programs are given a semantics using cubical areas. Such a semantics is said to be geometric. The collection of all these cubical areas enjoys a structure of tensor product in the category of semi-lattice with zero. These results naturally extend to fully fledged concurrent programs up to some technical tricks.

  1. Boolean computation of optimum hitting sets

    Energy Technology Data Exchange (ETDEWEB)

    Hulme, B.L.; Baca, L.S.; Shiver, A.W.; Worrell, R.B.

    1984-04-01

    This report presents the results of computational experience in solving weighted hitting set problems by Boolean algebraic methods. The feasible solutions are obtained by Boolean formula manipulations, and the optimum solutions are obtained by comparing the weight sums of the feasible solutions. Both the algebra and the optimization can be accomplished using the SETS language. One application is to physical protection problems. 8 references, 2 tables.

  2. THE INVERSE PROBLEM FOR BOOLEAN EQUATIONS

    Directory of Open Access Journals (Sweden)

    Hussain Mobarak Albarakati

    2012-01-01

    Full Text Available The Forward Problem (FB of Boolean equations consists of finding solutions of a system of Boolean equations, or equivalently, a single Boolean equation of the form f(X = 0 where f(X: Bn → B and B is an arbitrary Boolean algebra. By contrast, the Inverse Problem (IB of Boolean equations aims to reconstruct the equation f (X = 0 given the set of solutions and hence to verify the correctness of this set. This study derives methods that handle this inverse problem for the main types of solutions of Boolean equations. These include: (a Subsumptive general solutions, in which each of the variables is expressed as an interval by deriving successive conjunctive or disjunctive eliminants of the original function, (b Parametric general solutions, in which each of the variables is expressed via arbitrary parameters which are freely chosen elements of the underlying Boolean algebra and (c Particular solutions, each of which is an assignment from the underlying Boolean algebra to every pertinent variable that makes the Boolean equation an identity. The reconstructed function f(X in every case is set in a canonical form, such as the complete-sum form, to facilitate proving its equivalence to the original function. The methods presented herein are demonstrated with carefully-chosen illustrative examples over big Boolean algebras of various sizes. Among the methods utilized in handling the inverse problem for Boolean equations, the ones utilizing the variable-entered Karnaugh map offered pictorial insight and exhibited an efficient divide-and-conquer strategy.

  3. Algebra

    CERN Document Server

    Tabak, John

    2004-01-01

    Looking closely at algebra, its historical development, and its many useful applications, Algebra examines in detail the question of why this type of math is so important that it arose in different cultures at different times. The book also discusses the relationship between algebra and geometry, shows the progress of thought throughout the centuries, and offers biographical data on the key figures. Concise and comprehensive text accompanied by many illustrations presents the ideas and historical development of algebra, showcasing the relevance and evolution of this branch of mathematics.

  4. Algebra

    Institute of Scientific and Technical Information of China (English)

    2004-01-01

    Through most of Greek history, mathematicians concentrated on geometry, although Euclid considered the theory of numbers. The Greek mathematician Diophantus (3rd century),however, presented problems that had to be solved by what we would today call algebra. His book is thus the first algebra text.

  5. Algebra

    CERN Document Server

    Flanders, Harley

    1975-01-01

    Algebra presents the essentials of algebra with some applications. The emphasis is on practical skills, problem solving, and computational techniques. Topics covered range from equations and inequalities to functions and graphs, polynomial and rational functions, and exponentials and logarithms. Trigonometric functions and complex numbers are also considered, together with exponentials and logarithms.Comprised of eight chapters, this book begins with a discussion on the fundamentals of algebra, each topic explained, illustrated, and accompanied by an ample set of exercises. The proper use of a

  6. Boolean Chaos

    OpenAIRE

    Zhang, Rui; Cavalcante, Hugo L. D. de S.; Gao, Zheng; Gauthier, Daniel J.; Socolar, Joshua E. S.; Adams, Matthew M.; Lathrop, Daniel P.

    2009-01-01

    We observe deterministic chaos in a simple network of electronic logic gates that are not regulated by a clocking signal. The resulting power spectrum is ultra-wide-band, extending from dc to beyond 2 GHz. The observed behavior is reproduced qualitatively using an autonomously updating Boolean model with signal propagation times that depend on the recent history of the gates and filtering of pulses of short duration, whose presence is confirmed experimentally. Electronic Boolean chaos may fin...

  7. Boolean Factor Congruences and Property (*)

    CERN Document Server

    Terraf, Pedro Sánchez

    2008-01-01

    A variety V has Boolean factor congruences (BFC) if the set of factor congruences of every algebra in V is a distributive sublattice of its congruence lattice; this property holds in rings with unit and in every variety which has a semilattice operation. BFC has a prominent role in the study of uniqueness of direct product representations of algebras, since it is a strengthening of the refinement property. We provide an explicit Mal'cev condition for BFC. With the aid of this condition, it is shown that BFC is equivalent to a variant of the definability property (*), an open problem in R. Willard's work ("Varieties Having Boolean Factor Congruences," J. Algebra, 132 (1990)).

  8. Boolean Networks with Multi-Expressions and Parameters.

    Science.gov (United States)

    Zou, Yi Ming

    2013-07-01

    To model biological systems using networks, it is desirable to allow more than two levels of expression for the nodes and to allow the introduction of parameters. Various modeling and simulation methods addressing these needs using Boolean models, both synchronous and asynchronous, have been proposed in the literature. However, analytical study of these more general Boolean networks models is lagging. This paper aims to develop a concise theory for these different Boolean logic based modeling methods. Boolean models for networks where each node can have more than two levels of expression and Boolean models with parameters are defined algebraically with examples provided. Certain classes of random asynchronous Boolean networks and deterministic moduli asynchronous Boolean networks are investigated in detail using the setting introduced in this paper. The derived theorems provide a clear picture for the attractor structures of these asynchronous Boolean networks.

  9. Non-Boolean probabilities and quantum measurement

    Energy Technology Data Exchange (ETDEWEB)

    Niestegge, Gerd

    2001-08-03

    A non-Boolean extension of the classical probability model is proposed. The non-Boolean probabilities reproduce typical quantum phenomena. The proposed model is more general and more abstract, but easier to interpret, than the quantum mechanical Hilbert space formalism and exhibits a particular phenomenon (state-independent conditional probabilities) which may provide new opportunities for an understanding of the quantum measurement process. Examples of the proposed model are provided, using Jordan operator algebras. (author)

  10. Boolean approach to zero-one linear programming

    Energy Technology Data Exchange (ETDEWEB)

    Hulme, B.L.; Baca, L.S.

    1984-07-01

    Problems of minimizing or maximizing a linear objective function in zero-one variables subject to linear constraints can be solved by Boolean algebraic methods. This report gives both a general procedure for stating such problems in Boolean form and a solution procedure that has been implemented by a SETS user program. The program uses the Boolean algebraic formula manipulation techniques of the SETS language. Sample problems illustrate how to make optimum choices in the contexts of physical protection, packing knapsacks, designing manufacturing processes and making assignments.

  11. Stratification and enumeration of Boolean functions by canalizing depth

    CERN Document Server

    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.

  12. Stratification and enumeration of Boolean functions by canalizing depth

    Science.gov (United States)

    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.

  13. An Algebraic Approach to Empirical Science and Quantum Logic.

    Science.gov (United States)

    1982-01-01

    little ingenuity, one could extend this limit. The alphanumeric representation is imediately converted to a 36 digit binary representation, and in this...34 Studia Logica , XXXV, 2 (1976). 31bid., "Semi-Boolean Algebras," Matematickl Vesnick, 4:177-198 (1967). * 4D. J. Foulis and C. H. Randall, "What are...1970. • "Ortho-implication Algebras," Studia Logica , XXXV, 2 (1976). _ Rings with Boolean Difference. Pre-print. _’"Semi-Boolean Algebras

  14. Free Boolean Topological Groups

    Directory of Open Access Journals (Sweden)

    Ol’ga Sipacheva

    2015-11-01

    Full Text Available Known and new results on free Boolean topological groups are collected. An account of the properties that these groups share with free or free Abelian topological groups and properties specific to free Boolean groups is given. Special emphasis is placed on the application of set-theoretic methods to the study of Boolean topological groups.

  15. On Boolean Stable Laws

    CERN Document Server

    Arizmendi, Octavio

    2012-01-01

    We determine which Boolean stable law is freely infinitely divisible and which is not. Some positive Boolean stable laws and a mixture of them have completely monotonic densities and they are both freely and classically infinitely divisible. Freely infinitely divisible Boolean stable laws and the corresponding free stable laws are non trivial examples whose free divisibility indicators are infinity.

  16. Algebraic and stochastic coding theory

    CERN Document Server

    Kythe, Dave K

    2012-01-01

    Using a simple yet rigorous approach, Algebraic and Stochastic Coding Theory makes the subject of coding theory easy to understand for readers with a thorough knowledge of digital arithmetic, Boolean and modern algebra, and probability theory. It explains the underlying principles of coding theory and offers a clear, detailed description of each code. More advanced readers will appreciate its coverage of recent developments in coding theory and stochastic processes. After a brief review of coding history and Boolean algebra, the book introduces linear codes, including Hamming and Golay codes.

  17. Synchronization in an array of coupled Boolean networks

    Energy Technology Data Exchange (ETDEWEB)

    Li, Rui, E-mail: rui.li@pku.edu.cn [State Key Laboratory for Turbulence and Complex Systems, College of Engineering, Peking University, Beijing 100871 (China); Chu, Tianguang, E-mail: chutg@pku.edu.cn [State Key Laboratory for Turbulence and Complex Systems, College of Engineering, Peking University, Beijing 100871 (China)

    2012-10-01

    This Letter presents an analytical study of synchronization in an array of coupled deterministic Boolean networks. A necessary and sufficient criterion for synchronization is established based on algebraic representations of logical dynamics in terms of the semi-tensor product of matrices. Some basic properties of a synchronized array of Boolean networks are then derived for the existence of transient states and the upper bound of the number of fixed points. Particularly, an interesting consequence indicates that a “large” mismatch between two coupled Boolean networks in the array may result in loss of synchrony in the entire system. Examples, including the Boolean model of coupled oscillations in the cell cycle, are given to illustrate the present results. -- Highlights: ► We analytically study synchronization in an array of coupled Boolean networks. ► The study is based on the algebraic representations of logical dynamics. ► A necessary and sufficient algebraic criterion for synchronization is established. ► It reveals some basic properties of a synchronized array of Boolean networks. ► A large mismatch between two coupled networks may result in the loss of synchrony.

  18. Boolean representations of simplicial complexes and matroids

    CERN Document Server

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

  19. Boolean methods of optimization over independence systems

    Energy Technology Data Exchange (ETDEWEB)

    Hulme, B.L.

    1983-01-01

    This paper presents both a direct and an iterative method of solving the combinatorial optimization problem associated with any independence system. The methods use Boolean algebraic computations to produce solutions. In addition, the iterative method employs a version of the greedy algorithm both to compute upper bounds on the optimum value and to produce the additional circuits needed at every stage. The methods are extensions of those used to solve a problem of fire protection at nuclear reactor power plants.

  20. On Validating Boolean Optimizers

    CERN Document Server

    Morgado, Antonio

    2011-01-01

    Boolean optimization finds a wide range of application domains, that motivated a number of different organizations of Boolean optimizers since the mid 90s. Some of the most successful approaches are based on iterative calls to an NP oracle, using either linear search, binary search or the identification of unsatisfiable sub-formulas. The increasing use of Boolean optimizers in practical settings raises the question of confidence in computed results. For example, the issue of confidence is paramount in safety critical settings. One way of increasing the confidence of the results computed by Boolean optimizers is to develop techniques for validating the results. Recent work studied the validation of Boolean optimizers based on branch-and-bound search. This paper complements existing work, and develops methods for validating Boolean optimizers that are based on iterative calls to an NP oracle. This entails implementing solutions for validating both satisfiable and unsatisfiable answers from the NP oracle. The wo...

  1. Boolean integral calculus

    Science.gov (United States)

    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.

  2. Monotone Boolean functions

    Energy Technology Data Exchange (ETDEWEB)

    Korshunov, A D [S.L. Sobolev Institute for Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk (Russian Federation)

    2003-10-31

    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.

  3. Random Boolean expressions

    OpenAIRE

    Gardy, Danièle

    2005-01-01

    International audience; We examine how we can define several probability distributions on the set of Boolean functions on a fixed number of variables, starting from a representation of Boolean expressions by trees. Analytic tools give us a systematic way to prove the existence of probability distributions, the main challenge being the actual computation of the distributions. We finally consider the relations between the probability of a Boolean function and its complexity.

  4. Boolean Expression Diagrams

    DEFF Research Database (Denmark)

    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...... a BED into a reduced ordered BDD. One is a generalized version of the BDD apply-operator while the other can exploit the structural information of the Boolean expression. This ability is demonstrated by verifying that two different circuit implementations of a 16-bit multiplier implement the same...... Boolean function. Using BEDs, this verification problem is solved efficiently, while using standard BDD techniques this problem is infeasible. Generally, BEDs are useful in applications, for example tautology checking, where the end-result as a reduced ordered BDD is small. Moreover, using operators...

  5. Boolean Expression Diagrams

    DEFF Research Database (Denmark)

    Andersen, Henrik Reif; Hulgaard, Henrik

    1997-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 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 redundant and non-redundant versions of the ISCAS 85 benchmark circuits are identical. In particular, it is verified that the two 16-bit multiplication circuits (c6288 and c6288nr) implement the same Boolean functions. Using BEDs, this verification problem is solved in less than a second, while using...

  6. 广义Boolean-like环%Generalized Boolean-like Rings

    Institute of Scientific and Technical Information of China (English)

    秦蕊

    2013-01-01

    广义Boolean-like环是Boolean-like环的一个推广,文章主要介绍了广义Boolean-like环的构建,从而列举了若干广义Boolean-like环的相关例子及基本性质.并且,考虑了广义Boolean-like环的部分扩张,如上三角矩阵环.

  7. Synchronization in output-coupled temporal Boolean networks

    Science.gov (United States)

    Lu, Jianquan; Zhong, Jie; Tang, Yang; Huang, Tingwen; Cao, Jinde; Kurths, Jürgen

    2014-09-01

    This paper presents an analytical study of synchronization in an array of output-coupled temporal Boolean networks. A temporal Boolean network (TBN) is a logical dynamic system developed to model Boolean networks with regulatory delays. Both state delay and output delay are considered, and these two delays are assumed to be different. By referring to the algebraic representations of logical dynamics and using the semi-tensor product of matrices, the output-coupled TBNs are firstly converted into a discrete-time algebraic evolution system, and then the relationship between the states of coupled TBNs and the initial state sequence is obtained. Then, some necessary and sufficient conditions are derived for the synchronization of an array of TBNs with an arbitrary given initial state sequence. Two numerical examples including one epigenetic model are finally given to illustrate the obtained results.

  8. Boolean Ring and Its Spectrum%布尔环及其素谱

    Institute of Scientific and Technical Information of China (English)

    曲伟

    2012-01-01

    利用交换代数、拓扑等相关知识,讨论了布尔代数、布尔格、布尔环三者之间的对应关系,给出了布尔环及其素谱的一些性质并证明了由布尔环诱导出的布尔格与布尔环上素谱的既开又闲的子集构成的格同构.%In this paper,we show that Boolean rings,Boolean lattices and Boolean algebra are essentially the same. Moreover, every Boolean lattice induced by Boolean ring is isomorphic to the lattice of open and closed subsets of the Boolean ring's spectrum.

  9. Feedback Controller Design for the Synchronization of Boolean Control Networks.

    Science.gov (United States)

    Liu, Yang; Sun, Liangjie; Lu, Jianquan; Liang, Jinling

    2016-09-01

    This brief investigates the partial and complete synchronization of two Boolean control networks (BCNs). Necessary and sufficient conditions for partial and complete synchronization are established by the algebraic representations of logical dynamics. An algorithm is obtained to construct the feedback controller that guarantees the synchronization of master and slave BCNs. Two biological examples are provided to illustrate the effectiveness of the obtained results.

  10. On pseudo-Boolean polynomials

    Science.gov (United States)

    Leont'ev, V. K.

    2015-11-01

    A pseudo-Boolean function is an arbitrary mapping of the set of binary n-tuples to the real line. Such functions are a natural generalization of classical Boolean functions and find numerous applications in various applied studies. Specifically, the Fourier transform of a Boolean function is a pseudo-Boolean function. A number of facts associated with pseudo-Boolean polynomials are presented, and their applications to well-known discrete optimization problems are described.

  11. Monotone Boolean approximation

    Energy Technology Data Exchange (ETDEWEB)

    Hulme, B.L.

    1982-12-01

    This report presents a theory of approximation of arbitrary Boolean functions by simpler, monotone functions. Monotone increasing functions can be expressed without the use of complements. Nonconstant monotone increasing functions are important in their own right since they model a special class of systems known as coherent systems. It is shown here that when Boolean expressions for noncoherent systems become too large to treat exactly, then monotone approximations are easily defined. The algorithms proposed here not only provide simpler formulas but also produce best possible upper and lower monotone bounds for any Boolean function. This theory has practical application for the analysis of noncoherent fault trees and event tree sequences.

  12. Cylindric-like algebras and algebraic logic

    CERN Document Server

    Ferenczi, Miklós; Németi, István

    2013-01-01

    Algebraic logic is a subject in the interface between logic, algebra and geometry, it has strong connections with category theory and combinatorics. Tarski’s quest for finding structure in logic leads to cylindric-like algebras as studied in this book, they are among the main players in Tarskian algebraic logic. Cylindric algebra theory can be viewed in many ways:  as an algebraic form of definability theory, as a study of higher-dimensional relations, as an enrichment of Boolean Algebra theory, or, as logic in geometric form (“cylindric” in the name refers to geometric aspects). Cylindric-like algebras have a wide range of applications, in, e.g., natural language theory, data-base theory, stochastics, and even in relativity theory. The present volume, consisting of 18 survey papers, intends to give an overview of the main achievements and new research directions in the past 30 years, since the publication of the Henkin-Monk-Tarski monographs. It is dedicated to the memory of Leon Henkin.

  13. Congruence Kernels of Orthoimplication Algebras

    Directory of Open Access Journals (Sweden)

    I. Chajda

    2007-10-01

    Full Text Available Abstracting from certain properties of the implication operation in Boolean algebras leads to so-called orthoimplication algebras. These are in a natural one-to-one correspondence with families of compatible orthomodular lattices. It is proved that congruence kernels of orthoimplication algebras are in a natural one-to-one correspondence with families of compatible p-filters on the corresponding orthomodular lattices. Finally, it is proved that the lattice of all congruence kernels of an orthoimplication algebra is relatively pseudocomplemented and a simple description of the relative pseudocomplement is given.

  14. Modern Algebra, Mathematics: 5293.36.

    Science.gov (United States)

    Edwards, Raymond J.

    This guidebook covers Boolean algebra, matrices, linear transformations of the plane, characteristic values, vectors, and algebraic structures. Overall course goals and performance objectives for each unit are specified; sequencing of units and various time schedules are suggested. A sample pretest and posttest are given, and an annotated list of…

  15. Modeling digital switching circuits with linear algebra

    CERN Document Server

    Thornton, Mitchell A

    2014-01-01

    Modeling Digital Switching Circuits with Linear Algebra describes an approach for modeling digital information and circuitry that is an alternative to Boolean algebra. While the Boolean algebraic model has been wildly successful and is responsible for many advances in modern information technology, the approach described in this book offers new insight and different ways of solving problems. Modeling the bit as a vector instead of a scalar value in the set {0, 1} allows digital circuits to be characterized with transfer functions in the form of a linear transformation matrix. The use of transf

  16. Symmetric Boolean functions

    OpenAIRE

    Canteaut, Anne; Videau, Marion

    2005-01-01

    http://www.ieee.org/; We present an extensive study of symmetric Boolean functions, especially of their cryptographic properties. Our main result establishes the link between the periodicity of the simplified value vector of a symmetric Boolean function and its degree. Besides the reduction of the amount of memory required for representing a symmetric function, this property has some consequences from a cryptographic point of view. For instance, it leads to a new general bound on the order of...

  17. A Subclass of Ockham Algebras

    Institute of Scientific and Technical Information of China (English)

    Jie FANG; Zhong Ju SUN

    2012-01-01

    Here we introduce a subclass of the class of Ockham algebras (L; f) for which L satisfies the property that for every x ∈ L,there exists n ≥ 0 such that fn(x) and fn+1(x) are complementary.We characterize the structure of the lattice of congruences on such an algebra (L; f).We show that the lattice of compact congruences on L is a dual Stone lattice,and in particular,that the lattice Con L of congruences on L is boolean if and only if L is finite boolean.We also show that L is congruence coherent if and only if it is boolean.Finally,we give a sufficient and necessary condition to have the subdirectly irreducible chains.

  18. Towards boolean operations with thermal photons

    CERN Document Server

    Ben-Abdallah, Philippe

    2016-01-01

    The Boolean algebra is the natural theoretical framework for a classical information treatment. The basic logical operations are usually performed using logic gates. In this Letter we demonstrate that NOT, OR and AND gates can be realized exploiting the near-field radiative interaction in N-body systems with phase change materials. With the recent development of a photon thermal transistor and thermal memory, this result paves the way for a full information treatment and smart solutions for active thermal management at nanoscale with photons.

  19. Towards Boolean operations with thermal photons

    Science.gov (United States)

    Ben-Abdallah, Philippe; Biehs, Svend-Age

    2016-12-01

    The Boolean algebra is the natural theoretical framework for a classical information treatment. The basic logical operations are usually performed using logic gates. In this Rapid Communication we demonstrate that not, or, and and gates can be realized exploiting the near-field radiative interaction in N -body systems with phase change materials. With the recent development of a photon thermal transistor and thermal memory, this result paves the way for a full information treatment and smart solutions for active thermal management at nanoscale with photons.

  20. Partial Synchronization of Interconnected Boolean Networks.

    Science.gov (United States)

    Chen, Hongwei; Liang, Jinling; Lu, Jianquan

    2017-01-01

    This paper addresses the partial synchronization problem for the interconnected Boolean networks (BNs) via the semi-tensor product (STP) of matrices. First, based on an algebraic state space representation of BNs, a necessary and sufficient criterion is presented to ensure the partial synchronization of the interconnected BNs. Second, by defining an induced digraph of the partial synchronized states set, an equivalent graphical description for the partial synchronization of the interconnected BNs is established. Consequently, the second partial synchronization criterion is derived in terms of adjacency matrix of the induced digraph. Finally, two examples (including an epigenetic model) are provided to illustrate the efficiency of the obtained results.

  1. The Boolean Isomorphism problem

    Energy Technology Data Exchange (ETDEWEB)

    Agrawal, M. [Indian Institute of Technology, Kanpur (India); Thierauf, T. [Universitaet Ulm (Germany)

    1996-12-31

    We investigate the computational complexity of the Boolean Isomorphism problem (BI): on input of two Boolean formulas F and G decide whether there exists a permutation of the variables of G such that F and G become equivalent. Our main result is a one-round interactive proof for BI, where the verifier has access to an NP oracle. To obtain this, we use a recent result from learning theory by Bshouty et.al. that Boolean formulas can be learned probabilistically with equivalence queries and access to an NP oracle. As a consequence, BI cannot be {sigma}{sup p}{sub 2} complete unless the Polynomial Hierarchy collapses. This solves an open problem posed in [BRS95]. Further properties of BI are shown: BI has And- and Or-functions, the counting version, No. BI, can be computed in polynomial time relative to BI, and BI is self-reducible.

  2. Synchronization of Arbitrarily Switched Boolean Networks.

    Science.gov (United States)

    Chen, Hongwei; Liang, Jinling; Huang, Tingwen; Cao, Jinde

    2017-03-01

    This paper investigates the complete synchronization problem for the drive-response switched Boolean networks (SBNs) under arbitrary switching signals, where the switching signals of the response SBN follow those generated by the drive SBN at each time instant. First, the definition of complete synchronization is introduced for the drive-response SBNs under arbitrary switching signals. Second, the concept of switching reachable set starting from a given initial state set is put forward. Based on it, a necessary and sufficient condition is derived for the complete synchronization of the drive-response SBNs. Last, we give a simple algebraic expression for the switching reachable set in a given number of time steps, and two computable algebraic criteria are obtained for the complete synchronization of the SBNs. A biological example is given to demonstrate the effectiveness of the obtained main results.

  3. Dynamic Boolean models

    OpenAIRE

    Berg, van den, Aad; Meester, R.; White, Damien

    1997-01-01

    Consider an ordinary Boolean model, that is, a homogeneous Poisson point process in Rd, where the points are all centres of random balls with i.i.d. radii. Now let these points move around according to i.i.d. stochastic processes. It is not hard to show that at each xed time t we again have a Boolean model with the original distribution. Hence if the original model is supercritical then, for any t, the probability of having an unbounded occupied component at time t equals 1. We show that unde...

  4. Vectorial Resilient PC(l) of Order k Boolean Functions from AG-Codes

    Institute of Scientific and Technical Information of China (English)

    Hao CHEN; Liang MA; Jianhua LI

    2011-01-01

    Propagation criteria and resiliency of vectorial Boolean functions are important for cryptographic purpose (see [1- 4, 7, 8, 10, 11, 16]). Kurosawa, Stoh [8] and Carlet [1]gave a construction of Boolean functions satisfying PC(l) of order k from binary linear or nonlinear codes. In this paper, the algebraic-geometric codes over GF(2m) are used to modify the Carlet and Kurosawa-Satoh's construction for giving vectorial resilient Boolean functions satisfying PC(l) of order k criterion. This new construction is compared with previously known results.

  5. Quantum Boolean image denoising

    Science.gov (United States)

    Mastriani, Mario

    2015-05-01

    A quantum Boolean image processing methodology is presented in this work, with special emphasis in image denoising. A new approach for internal image representation is outlined together with two new interfaces: classical to quantum and quantum to classical. The new quantum Boolean image denoising called quantum Boolean mean filter works with computational basis states (CBS), exclusively. To achieve this, we first decompose the image into its three color components, i.e., red, green and blue. Then, we get the bitplanes for each color, e.g., 8 bits per pixel, i.e., 8 bitplanes per color. From now on, we will work with the bitplane corresponding to the most significant bit (MSB) of each color, exclusive manner. After a classical-to-quantum interface (which includes a classical inverter), we have a quantum Boolean version of the image within the quantum machine. This methodology allows us to avoid the problem of quantum measurement, which alters the results of the measured except in the case of CBS. Said so far is extended to quantum algorithms outside image processing too. After filtering of the inverted version of MSB (inside quantum machine), the result passes through a quantum-classical interface (which involves another classical inverter) and then proceeds to reassemble each color component and finally the ending filtered image. Finally, we discuss the more appropriate metrics for image denoising in a set of experimental results.

  6. Algebraic totality, towards completeness

    CERN Document Server

    Tasson, Christine

    2009-01-01

    Finiteness spaces constitute a categorical model of Linear Logic (LL) whose objects can be seen as linearly topologised spaces, (a class of topological vector spaces introduced by Lefschetz in 1942) and morphisms as continuous linear maps. First, we recall definitions of finiteness spaces and describe their basic properties deduced from the general theory of linearly topologised spaces. Then we give an interpretation of LL based on linear algebra. Second, thanks to separation properties, we can introduce an algebraic notion of totality candidate in the framework of linearly topologised spaces: a totality candidate is a closed affine subspace which does not contain 0. We show that finiteness spaces with totality candidates constitute a model of classical LL. Finally, we give a barycentric simply typed lambda-calculus, with booleans ${\\mathcal{B}}$ and a conditional operator, which can be interpreted in this model. We prove completeness at type ${\\mathcal{B}}^n\\to{\\mathcal{B}}$ for every n by an algebraic metho...

  7. Computational complexity of Boolean functions

    Energy Technology Data Exchange (ETDEWEB)

    Korshunov, Aleksei D [Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk (Russian Federation)

    2012-02-28

    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.

  8. Fault Tolerant Boolean Satisfiability

    CERN Document Server

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

  9. The algebra of logic: what Boole really started

    OpenAIRE

    Green, Judy

    1994-01-01

    Although the concept of a Boolean algebra has its roots in the algebra of logic, an algebra of logic of the nineteenth century was a scheme for symbolizing logical relationships as algebraic ones in such a way that logical deductions could be accomplished by algebraic manipulations. Boole wrote three works on logic, but it is in the first of these, the 1847 The Mathematical Analysis of Logic, Being an Essay Towards a Calculus of Deductive Logic, that one finds the most careful algebraic devel...

  10. J-Boolean like环%J-Boolean Like Ring

    Institute of Scientific and Technical Information of China (English)

    秦蕊

    2013-01-01

    本文首先引进了Boolean-like环的一类新的扩张J-Boolean like环,即对任意环R中元素a,b都有(a-a2)(b-b2)∈J(R),这里J(R)为环R的Jacobson根,则环R称为J-Boolean like环.证明了两个定理分别为(1)设D是一个环,C是D的一个子环,R[D,C]是一个J-Boolean like环(=)(a)C,D是J-Boolean like环,(b)J2(C)(∈)J(D).(2)如果B/J(B)是Boolean环,并且B[i]={a+bi| i2=ui+η,a,b,u,η∈B},那么B[i]是J-Booleanlike环当且仅当uη∈J(B).

  11. Approximate Reasoning with Fuzzy Booleans

    NARCIS (Netherlands)

    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

  12. Independence-friendly cylindric set algebras

    CERN Document Server

    Mann, Allen L

    2007-01-01

    Independence-friendly logic is a conservative extension of first-order logic that has the same expressive power as existential second-order logic. In her Ph.D. thesis, Dechesne introduces a variant of independence-friendly logic called IFG logic. We attempt to algebraize IFG logic in the same way that Boolean algebra is the algebra of propositional logic and cylindric algebra is the algebra of first-order logic. We define independence-friendly cylindric set algebras and prove two main results. First, every independence-friendly cylindric set algebra over a structure has an underlying Kleene algebra. Moreover, the class of such underlying Kleene algebras generates the variety of all Kleene algebras. Hence the equational theory of the class of Kleene algebras that underly an independence-friendly cylindric set algebra is finitely axiomatizable. Second, every one-dimensional independence-friendly cylindric set algebra over a structure has an underlying monadic Kleene algebra. However, the class of such underlyin...

  13. Cryptographic Boolean functions and applications

    CERN Document Server

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

  14. Polynomial threshold functions and Boolean threshold circuits

    DEFF Research Database (Denmark)

    Hansen, Kristoffer Arnsfelt; Podolskii, Vladimir V.

    2013-01-01

    of secondary interest. We show that PTFs on general Boolean domains are tightly connected to depth two threshold circuits. Our main results in regard to this connection are: PTFs of polynomial length and polynomial degree compute exactly the functions computed by THRMAJ circuits. An exponential length lower...... bound for PTFs that holds regardless of degree, thereby extending known lower bounds for THRMAJ circuits. We generalize two-party unbounded error communication complexity to the multi-party number-on-the-forehead setting, and show that communication lower bounds for 3-player protocols would yield size...... lower bounds for THRTHR circuits. We obtain several other results about PTFs. These include relationships between weight and degree of PTFs, and a degree lower bound for PTFs of constant length. We also consider a variant of PTFs over the max-plus algebra. We show that they are connected to PTFs over...

  15. CONSTRUCTION OF GENERAL SUBSUMPTIVE SOLUTIONS OF BOOLEAN EQUATIONS VIA COMPLETE-SUM DERIVATION

    Directory of Open Access Journals (Sweden)

    Ali Muhammad Ali Rushdi

    2014-01-01

    Full Text Available Boolean-equation solving permeates many diverse areas of modern science. To solve a system of Boolean equations, one usually combines them into an equivalent single Boolean equation whose set of solutions is exactly the same as that of the original system of equations. One of the general classes of solutions for Boolean equations is the subsumptive general solution, in which each variable is expressed as an interval decided by a double inequality in terms of the succeeding variables. The solution validity depends on the satisfaction of a required consistency condition. In this study, we introduce a novel method (henceforth called the CS method for producing subsumptive Boolean-equation solutions based on deriving the complete sum of the pertinent Boolean function . The complete sum is a disjunction of all prime implicants of and nothing else. It explicitly shows all information about in the most compact form. We demonstrate the proposed CS solutions in terms of four examples, covering Boolean algebras of different sizes and using two prominent methods for deriving . Occasionally, the consistency condition results in a collapse of the underlying Boolean algebra into a smaller subalgebra. We also illustrate how an expansion tree (typically reduced to an acyclic graph can be used to deduce a complete list of all particular solutions from the subsumptive solution. The present CS method yields correct solutions, since it fits into the frame of the most general subsumptive solution. Among competing subsumptive methods, the CS method strikes a reasonable tradeoff between the conflicting requirements of less computational cost and more compact form for the solution obtained. In fact, it is the second best known method from both criteria of efficiency and compactness of solution.

  16. Algebra V homological algebra

    CERN Document Server

    Shafarevich, I

    1994-01-01

    This book, the first printing of which was published as volume 38 of the Encyclopaedia of Mathematical Sciences, presents a modern approach to homological algebra, based on the systematic use of the terminology and ideas of derived categories and derived functors. The book contains applications of homological algebra to the theory of sheaves on topological spaces, to Hodge theory, and to the theory of modules over rings of algebraic differential operators (algebraic D-modules). The authors Gelfand and Manin explain all the main ideas of the theory of derived categories. Both authors are well-known researchers and the second, Manin, is famous for his work in algebraic geometry and mathematical physics. The book is an excellent reference for graduate students and researchers in mathematics and also for physicists who use methods from algebraic geometry and algebraic topology.

  17. Quantum algorithms for testing Boolean functions

    OpenAIRE

    Erika Andersson; Floess, Dominik F.; Mark Hillery

    2010-01-01

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

  18. Bounded Algebra and Current-Mode Digital Circuits

    Institute of Scientific and Technical Information of China (English)

    WU Xunwei; Massoud Pedram

    1999-01-01

    This paper proposes two boundedarithmetic operations, which are easily realized with current signals.Based on these two operations, a bounded algebra system suitable fordescribing current-mode digital circuits is developed and itsrelationship with the Boolean algebra, which is suitable for representingvoltage-mode digital circuits, is investigated. Design procedure forcurrent-mode circuits using the proposed algebra system is demonstratedon a number of common circuit elements which are used to realizearithmetic operations, such as adders and multipliers.

  19. ON (∈, ∈∨q)-FUZZY FILTERS OF BL-ALGEBRAS

    Institute of Scientific and Technical Information of China (English)

    Xueling MA; Jianming ZHAN

    2008-01-01

    The authors introduce the notions of (∈, ∈∨q)-fuzzy Boolean (implicative, positive implica-tive, and fantastic) filters in BL-algebras, present some characterizations on these generalized fuzzy filters, and describe the relations among these generalized fuzzy filters. It is proved that an (∈, ∈∨q)-fuzzy filter in a BL-algebra is Boolean (implicative) if and only if it is both positive implicative and fantastic.

  20. Ultra LI-ideals in lattice implication algebras and MTL-algebras

    CERN Document Server

    Zhang, Xiaohong; Dudek, Wieslaw A

    2007-01-01

    A mistake concerning the ultra \\textit{LI}-ideal of a lattice implication algebra is pointed out, and some new sufficient and necessary conditions for an \\textit{LI}-ideal to be an ultra \\textit{LI}-ideal are given. Moreover, the notion of an \\textit{LI}-ideal is extended to MTL-algebras, the notions of a (prime, ultra, obstinate, Boolean) \\textit{LI}-ideal and an \\textit{ILI}-ideal of an MTL-algebra are introduced, some important examples are given, and the following notions are proved to be equivalent in MTL-algebra: (1) prime proper \\textit{LI}-ideal and Boolean \\textit{LI}-ideal, (2) prime proper \\textit{LI}-ideal and \\textit{ILI}-ideal, (3) proper obstinate \\textit{LI}-ideal, (4) ultra \\textit{LI}-ideal.

  1. Left Artinian Algebraic Algebras

    Institute of Scientific and Technical Information of China (English)

    S. Akbari; M. Arian-Nejad

    2001-01-01

    Let R be a left artinian central F-algebra, T(R) = J(R) + [R, R],and U(R) the group of units of R. As one of our results, we show that, if R is algebraic and char F = 0, then the number of simple components of -R = R/J(R)is greater than or equal to dimF R/T(R). We show that, when char F = 0 or F is uncountable, R is algebraic over F if and only if [R, R] is algebraic over F. As another approach, we prove that R is algebraic over F if and only if the derived subgroup of U(R) is algebraic over F. Also, we present an elementary proof for a special case of an old question due to Jacobson.

  2. Computing preimages of Boolean networks

    Science.gov (United States)

    2013-01-01

    In this paper we present an algorithm based on the sum-product algorithm that finds elements in the preimage of a feed-forward Boolean networks given an output of the network. Our probabilistic method runs in linear time with respect to the number of nodes in the network. We evaluate our algorithm for randomly constructed Boolean networks and a regulatory network of Escherichia coli and found that it gives a valid solution in most cases. PMID:24267277

  3. Maiorana-McFarland class: Degree optimization and algebraic properties

    DEFF Research Database (Denmark)

    Pasalic, Enes

    2006-01-01

    degree of functions in the extended Maiorana-McFarland (MM) class (nonlinear resilient functions F : GF (2)(n) -> GF (2)(m) derived from linear codes). We also show that in the Boolean case, the same subclass seems not to have an optimized algebraic immunity, hence not providing a maximum resistance......In this paper, we consider a subclass of the Maiorana-McFarland class used in the design of resilient nonlinear Boolean functions. We show that these functions allow a simple modification so that resilient Boolean functions of maximum algebraic degree may be generated instead of suboptimized degree...... in the original class. Preserving a high-nonlinearity value immanent to the original construction method, together with the degree optimization gives in many cases functions with cryptographic properties superior to all previously known construction methods. This approach is then used to increase the algebraic...

  4. Synchronization Analysis of Master-Slave Probabilistic Boolean Networks

    Science.gov (United States)

    Lu, Jianquan; Zhong, Jie; Li, Lulu; Ho, Daniel W. C.; Cao, Jinde

    2015-01-01

    In this paper, we analyze the synchronization problem of master-slave probabilistic Boolean networks (PBNs). The master Boolean network (BN) is a deterministic BN, while the slave BN is determined by a series of possible logical functions with certain probability at each discrete time point. In this paper, we firstly define the synchronization of master-slave PBNs with probability one, and then we investigate synchronization with probability one. By resorting to new approach called semi-tensor product (STP), the master-slave PBNs are expressed in equivalent algebraic forms. Based on the algebraic form, some necessary and sufficient criteria are derived to guarantee synchronization with probability one. Further, we study the synchronization of master-slave PBNs in probability. Synchronization in probability implies that for any initial states, the master BN can be synchronized by the slave BN with certain probability, while synchronization with probability one implies that master BN can be synchronized by the slave BN with probability one. Based on the equivalent algebraic form, some efficient conditions are derived to guarantee synchronization in probability. Finally, several numerical examples are presented to show the effectiveness of the main results. PMID:26315380

  5. Synchronization Analysis of Master-Slave Probabilistic Boolean Networks.

    Science.gov (United States)

    Lu, Jianquan; Zhong, Jie; Li, Lulu; Ho, Daniel W C; Cao, Jinde

    2015-01-01

    In this paper, we analyze the synchronization problem of master-slave probabilistic Boolean networks (PBNs). The master Boolean network (BN) is a deterministic BN, while the slave BN is determined by a series of possible logical functions with certain probability at each discrete time point. In this paper, we firstly define the synchronization of master-slave PBNs with probability one, and then we investigate synchronization with probability one. By resorting to new approach called semi-tensor product (STP), the master-slave PBNs are expressed in equivalent algebraic forms. Based on the algebraic form, some necessary and sufficient criteria are derived to guarantee synchronization with probability one. Further, we study the synchronization of master-slave PBNs in probability. Synchronization in probability implies that for any initial states, the master BN can be synchronized by the slave BN with certain probability, while synchronization with probability one implies that master BN can be synchronized by the slave BN with probability one. Based on the equivalent algebraic form, some efficient conditions are derived to guarantee synchronization in probability. Finally, several numerical examples are presented to show the effectiveness of the main results.

  6. Algebraic Statistics

    OpenAIRE

    Norén, Patrik

    2013-01-01

    Algebraic statistics brings together ideas from algebraic geometry, commutative algebra, and combinatorics to address problems in statistics and its applications. Computer algebra provides powerful tools for the study of algorithms and software. However, these tools are rarely prepared to address statistical challenges and therefore new algebraic results need often be developed. This way of interplay between algebra and statistics fertilizes both disciplines. Algebraic statistics is a relativ...

  7. Boolean Searches--A Life Skill.

    Science.gov (United States)

    Ala, Judy; Cerabona, Kathy

    1992-01-01

    Discusses the importance of Boolean searching as a skill that students will need in the future. Methods for teaching Boolean searching are described, and the value of truncation as an online searching aid is considered. (MES)

  8. Algebraic geometry

    CERN Document Server

    Lefschetz, Solomon

    2005-01-01

    An introduction to algebraic geometry and a bridge between its analytical-topological and algebraical aspects, this text for advanced undergraduate students is particularly relevant to those more familiar with analysis than algebra. 1953 edition.

  9. Generalized periodic and generalized Boolean rings

    Directory of Open Access Journals (Sweden)

    Howard E. Bell

    2001-01-01

    Full Text Available We prove that a generalized periodic, as well as a generalized Boolean, ring is either commutative or periodic. We also prove that a generalized Boolean ring with central idempotents must be nil or commutative. We further consider conditions which imply the commutativity of a generalized periodic, or a generalized Boolean, ring.

  10. Synchronization for the Realization-Dependent Probabilistic Boolean Networks.

    Science.gov (United States)

    Chen, Hongwei; Liang, Jinling; Lu, Jianquan; Qiu, Jianlong

    2017-01-24

    This paper investigates the synchronization problem for the realization-dependent probabilistic Boolean networks (PBNs) coupled unidirectionally in the drive-response configuration. The realization of the response PBN is assumed to be uniquely determined by the realization signal generated by the drive PBN at each discrete time instant. First, the drive-response PBNs are expressed in their algebraic forms based on the semitensor product method, and then, a necessary and sufficient condition is presented for the synchronization of the PBNs. Second, by resorting to a newly defined matrix operator, the reachable set from any initial state is expressed by a column vector. Consequently, an easily computable algebraic criterion is derived assuring the synchronization of the drive-response PBNs. Finally, three illustrative examples are employed to demonstrate the applicability and usefulness of the developed theoretical results.

  11. Synchronization of Asynchronous Switched Boolean Network.

    Science.gov (United States)

    Zhang, Hao; Wang, Xingyuan; Lin, Xiaohui

    2015-01-01

    In this paper, the complete synchronizations for asynchronous switched Boolean network with free Boolean sequence controllers and close-loop controllers are studied. First, the basic asynchronous switched Boolean network model is provided. With the method of semi-tensor product, the Boolean dynamics is translated into linear representation. Second, necessary and sufficient conditions for ASBN synchronization with free Boolean sequence control and close-loop control are derived, respectively. Third, some illustrative examples are provided to show the efficiency of the proposed methods.

  12. Geometric Operators on Boolean Functions

    DEFF Research Database (Denmark)

    Frisvad, Jeppe Revall; Falster, Peter

    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 propositional reasoning. In other words, we can capture all kinds of inference in propositional logic by means...... independent of representation such that we no longer need to be much concerned with the form of the Boolean functions. Knowing that the operators can easily be implemented (as they have been in array-based logic), shows the advantage they give with respect to automated reasoning....

  13. Boolean Operations on Conic Polygons

    Institute of Scientific and Technical Information of China (English)

    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.

  14. Sublogarithmic uniform Boolean proof nets

    CERN Document Server

    Aubert, Clément

    2012-01-01

    Using a proofs-as-programs correspondence, Terui was able to compare two models of parallel computation: Boolean circuits and proof nets for multiplicative linear logic. Mogbil et. al. gave a logspace translation allowing us to compare their computational power as uniform complexity classes. This paper presents a novel translation in AC0 and focuses on a simpler restricted notion of uniform Boolean proof nets. We can then encode constant-depth circuits and compare complexity classes below logspace, which were out of reach with the previous translations.

  15. Algebra for cryptologists

    CERN Document Server

    Meijer, Alko R

    2016-01-01

    This textbook provides an introduction to the mathematics on which modern cryptology is based. It covers not only public key cryptography, the glamorous component of modern cryptology, but also pays considerable attention to secret key cryptography, its workhorse in practice. Modern cryptology has been described as the science of the integrity of information, covering all aspects like confidentiality, authenticity and non-repudiation and also including the protocols required for achieving these aims. In both theory and practice it requires notions and constructions from three major disciplines: computer science, electronic engineering and mathematics. Within mathematics, group theory, the theory of finite fields, and elementary number theory as well as some topics not normally covered in courses in algebra, such as the theory of Boolean functions and Shannon theory, are involved. Although essentially self-contained, a degree of mathematical maturity on the part of the reader is assumed, corresponding to his o...

  16. Modular Decomposition of Boolean Functions

    NARCIS (Netherlands)

    J.C. Bioch (Cor)

    2002-01-01

    textabstractModular decomposition is a thoroughly investigated topic in many areas such as switching theory, reliability theory, game theory and graph theory. Most appli- cations can be formulated in the framework of Boolean functions. In this paper we give a uni_ed treatment of modular decompositio

  17. Evolutionary Design of Boolean Functions

    Institute of Scientific and Technical Information of China (English)

    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.

  18. Mental Models of Boolean Concepts

    Science.gov (United States)

    Goodwin, Geoffrey P.; Johnson-Laird, P. N.

    2011-01-01

    Negation, conjunction, and disjunction are major building blocks in the formation of concepts. This article presents a new model-based theory of these Boolean components. It predicts that individuals simplify the models of instances of concepts. Evidence corroborates the theory and challenges alternative accounts, such as those based on minimal…

  19. Construction of optimized Boolean functions

    Institute of Scientific and Technical Information of China (English)

    CHEN Wei; YANG Yi-xian; NIU Xin-xin

    2006-01-01

    Considering connections of characteristics,this paper is aimed at the construction of optimized Boolean functions.A new method based on the Bent function,discrete Walsh spectrum and characteristics matrices are presented by concatenating,breaking,and revising output sequences conditionally.This new construction can be used to construct different kinds of functions satisfying different design criteria.

  20. Synchronization of Boolean Networks with Different Update Schemes.

    Science.gov (United States)

    Zhang, Hao; Wang, Xingyuan; Lin, Xiaohui

    2014-01-01

    In this paper, the synchronizations of Boolean networks with different update schemes (synchronized Boolean networks and asynchronous Boolean networks) are investigated. All nodes in Boolean network are represented in terms of semi-tensor product. First, we give the concept of inner synchronization and observe that all nodes in a Boolean network are synchronized with each other. Second, we investigate the outer synchronization between a driving Boolean network and a corresponding response Boolean network. We provide not only the concept of traditional complete synchronization, but also the anti-synchronization and get the anti-synchronization in simulation. Third, we extend the outer synchronization to asynchronous Boolean network and get the complete synchronization between an asynchronous Boolean network and a response Boolean network. Consequently, theorems for synchronization of Boolean networks and asynchronous Boolean networks are derived. Examples are provided to show the correctness of our theorems.

  1. A Boolean action of C(M,U(1)) without a spatial model

    CERN Document Server

    Moore, Justin Tatch

    2012-01-01

    We will demonstrate that if M is an uncountable compact metric space, then there is an action of the Polish group of all continuous functions from M to U(1) on a separable probability algebra which preserves the measure and yet does not admit a point realization (in a standard probability space) in the sense of Mackey. This contrasts Mackey's point realization theorem for locally compact, second countable groups which asserts that any measure preserving Boolean action of a locally compact, second countable group on a separable probability algebra can be realized as an action on the points of a standard probability space.

  2. Quantum algorithms for testing Boolean functions

    Directory of Open Access Journals (Sweden)

    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.

  3. Computer Algebra.

    Science.gov (United States)

    Pavelle, Richard; And Others

    1981-01-01

    Describes the nature and use of computer algebra and its applications to various physical sciences. Includes diagrams illustrating, among others, a computer algebra system and flow chart of operation of the Euclidean algorithm. (SK)

  4. Algebraic Topology

    OpenAIRE

    2013-01-01

    The chapter provides an introduction to the basic concepts of Algebraic Topology with an emphasis on motivation from applications in the physical sciences. It finishes with a brief review of computational work in algebraic topology, including persistent homology.

  5. Polynomial threshold functions and Boolean threshold circuits

    DEFF Research Database (Denmark)

    Hansen, Kristoffer Arnsfelt; Podolskii, Vladimir V.

    2013-01-01

    We study the complexity of computing Boolean functions on general Boolean domains by polynomial threshold functions (PTFs). A typical example of a general Boolean domain is 12n . We are mainly interested in the length (the number of monomials) of PTFs, with their degree and weight being...... of secondary interest. We show that PTFs on general Boolean domains are tightly connected to depth two threshold circuits. Our main results in regard to this connection are: PTFs of polynomial length and polynomial degree compute exactly the functions computed by THRMAJ circuits. An exponential length lower...

  6. Rational Verification in Iterated Electric Boolean Games

    Directory of Open Access Journals (Sweden)

    Youssouf Oualhadj

    2016-07-01

    Full Text Available Electric boolean games are compact representations of games where the players have qualitative objectives described by LTL formulae and have limited resources. We study the complexity of several decision problems related to the analysis of rationality in electric boolean games with LTL objectives. In particular, we report that the problem of deciding whether a profile is a Nash equilibrium in an iterated electric boolean game is no harder than in iterated boolean games without resource bounds. We show that it is a PSPACE-complete problem. As a corollary, we obtain that both rational elimination and rational construction of Nash equilibria by a supervising authority are PSPACE-complete problems.

  7. Progress in Applications of Boolean Functions

    CERN Document Server

    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.

  8. Generalizing Boolean Satisfiability III: Implementation

    CERN Document Server

    Dixon, H E; Hofer, D; Luks, E M; Parkes, A J; 10.1613/jair.1656

    2011-01-01

    This is the third of three 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 has been to define a representation in which this structure is apparent and can be exploited to improve computational performance. The first paper surveyed existing work that (knowingly or not) exploited problem structure to improve the performance of satisfiability engines, and the second paper showed that this structure could be understood in terms of groups of permutations acting on individual clauses in any particular Boolean theory. We conclude the series by discussing the techniques needed to implement our ideas, and by reporting on their performance on a variety of problem instances.

  9. Reconstructing Boolean Models of Signaling

    Science.gov (United States)

    Karp, Richard M.

    2013-01-01

    Abstract Since the first emergence of protein–protein interaction networks more than a decade ago, they have been viewed as static scaffolds of the signaling–regulatory events taking place in cells, and their analysis has been mainly confined to topological aspects. Recently, functional models of these networks have been suggested, ranging from Boolean to constraint-based methods. However, learning such models from large-scale data remains a formidable task, and most modeling approaches rely on extensive human curation. Here we provide a generic approach to learning Boolean models automatically from data. We apply our approach to growth and inflammatory signaling systems in humans and show how the learning phase can improve the fit of the model to experimental data, remove spurious interactions, and lead to better understanding of the system at hand. PMID:23286509

  10. Boolean networks with veto functions

    Science.gov (United States)

    Ebadi, Haleh; Klemm, Konstantin

    2014-08-01

    Boolean networks are discrete dynamical systems for modeling regulation and signaling in living cells. We investigate a particular class of Boolean functions with inhibiting inputs exerting a veto (forced zero) on the output. We give analytical expressions for the sensitivity of these functions and provide evidence for their role in natural systems. In an intracellular signal transduction network [Helikar et al., Proc. Natl. Acad. Sci. USA 105, 1913 (2008), 10.1073/pnas.0705088105], the functions with veto are over-represented by a factor exceeding the over-representation of threshold functions and canalyzing functions in the same system. In Boolean networks for control of the yeast cell cycle [Li et al., Proc. Natl. Acad. Sci. USA 101, 4781 (2004), 10.1073/pnas.0305937101; Davidich et al., PLoS ONE 3, e1672 (2008), 10.1371/journal.pone.0001672], no or minimal changes to the wiring diagrams are necessary to formulate their dynamics in terms of the veto functions introduced here.

  11. A Multiple—Valued Algebra for Modeling MOS VLSI Circuits at Switch—Level

    Institute of Scientific and Technical Information of China (English)

    胡谋

    1992-01-01

    A multiple-valued algebra for modeling MOS VLSI circuits at switch-level is proposed in this paper,Its structure and properties are studied.This algebra can be used to transform a MOS digital circuit to a swith-level algebraic expression so as to generate the truth table for the circuit and to derive a Boolean expression for it.In the paper,methods to construct a switch-level algebraic expression for a circuit and methods to simplify expressions are given.This algebra provides a new tool for MOS VLSI circuit design and analysis.

  12. Semi-Boolean Algebras Empirical Logic and Rings.

    Science.gov (United States)

    1982-01-01

    Thesis, University of Massachusetts. 13j 141LI.G. Bughes, "Quantum Logic," Scientific American, 202-213 (Oct. 1981). 15J.3. Fraleigh , A First Course ...Workshop on Quaatum Logic. Erice, Sicily: Ettore Majorana Centre for Scientific Culture, 2-9 Dec 1970. Flaleigh, J. B. A First Course in Abstract Alebra...be shown that o is a lower bound and that if z is any other lower bound for S then z < o. First , since ox - o it follows that o < x for all x in S

  13. Algebraic circuits

    CERN Document Server

    Lloris Ruiz, Antonio; Parrilla Roure, Luis; García Ríos, Antonio

    2014-01-01

    This book presents a complete and accurate study of algebraic circuits, digital circuits whose performance can be associated with any algebraic structure. The authors distinguish between basic algebraic circuits, such as Linear Feedback Shift Registers (LFSRs) and cellular automata, and algebraic circuits, such as finite fields or Galois fields. The book includes a comprehensive review of representation systems, of arithmetic circuits implementing basic and more complex operations, and of the residue number systems (RNS). It presents a study of basic algebraic circuits such as LFSRs and cellular automata as well as a study of circuits related to Galois fields, including two real cryptographic applications of Galois fields.

  14. Version Spaces and Generalized Monotone Boolean Functions

    NARCIS (Netherlands)

    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

  15. Boolean Search: Current State and Perspectives.

    Science.gov (United States)

    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…

  16. Boolean analysis of addition and multiplication

    Energy Technology Data Exchange (ETDEWEB)

    Faltin, F. (Cornell Univ., Ithaca, NY); Metropolis, N.; Ross, B.; Rota, G.-C.

    1977-01-01

    The notions of binary string and binary symmetric function are introduced, and basic results presented. Boolean algorithms are given for binary addition and multiplication. An analysis of the redundancies involved is straightforward. The examination of carry propagation which arises in the Boolean analysis of functions may lead to a new interpretation of the notion of computational complexity.

  17. Boolean integral calculus for digital systems

    Science.gov (United States)

    Tucker, J. H.; Tapia, M. A.; Bennett, A. W.

    1985-01-01

    The concept of Boolean integration is introduced and developed. When the changes in a desired function are specified in terms of changes in its arguments, then ways of 'integrating' (i.e., realizing) the function, if it exists, are presented. Boolean integral calculus has applications in design of logic circuits.

  18. On a Boolean-valued Model of the Strict Implication System(Continuous)

    Institute of Scientific and Technical Information of China (English)

    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 .

  19. Boolean networks as modelling framework

    Directory of Open Access Journals (Sweden)

    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.

  20. Hom-Akivis algebras

    CERN Document Server

    Issa, A Nourou

    2010-01-01

    Non-Hom-associative algebras and Hom-Akivis algebras are introduced. The commutator-Hom-associator algebra of a non-Hom-associative algebra is a Hom-Akivis algebra. It is shown that non-Hom-associative algebras can be obtained from nonassociative algebras by twisting along algebra automorphisms while Hom-Akivis algebras can be obtained from Akivis algebras by twisting along algebra endomorphisms.

  1. On the Complexity of the Evaluation of Transient Extensions of Boolean Functions

    Directory of Open Access Journals (Sweden)

    Janusz Brzozowski

    2010-08-01

    Full Text Available Transient algebra is a multi-valued algebra for hazard detection in gate circuits. Sequences of alternating 0's and 1's, called transients, represent signal values, and gates are modeled by extensions of boolean functions to transients. Formulas for computing the output transient of a gate from the input transients are known for NOT, AND, OR} and XOR gates and their complements, but, in general, even the problem of deciding whether the length of the output transient exceeds a given bound is NP-complete. We propose a method of evaluating extensions of general boolean functions. We introduce and study a class of functions with the following property: Instead of evaluating an extension of a boolean function on a given set of transients, it is possible to get the same value by using transients derived from the given ones, but having length at most 3. We prove that all functions of three variables, as well as certain other functions, have this property, and can be efficiently evaluated.

  2. Elliptic algebras

    Energy Technology Data Exchange (ETDEWEB)

    Odesskii, A V [L.D. Landau Institute for Theoretical Physics, Russian Academy of Sciences, Moscow (Russian Federation)

    2002-12-31

    This survey is devoted to associative Z{sub {>=}}{sub 0}-graded algebras presented by n generators and n(n-1)/2 quadratic relations and satisfying the so-called Poincare-Birkhoff-Witt condition (PBW-algebras). Examples are considered of such algebras, depending on two continuous parameters (namely, on an elliptic curve and a point on it), that are flat deformations of the polynomial ring in n variables. Diverse properties of these algebras are described, together with their relations to integrable systems, deformation quantization, moduli spaces, and other directions of modern investigations.

  3. Model Checking of Boolean Process Models

    CERN Document Server

    Schneider, Christoph

    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 model explicitly states with a subsequent skipping of activations and arbitrary logical rules of type AND, XOR, OR etc. to model the split and join of the control flow. We apply model checking as a verification method for the safeness and liveness of Boolean systems. Model checking of Boolean systems uses the elementary theory of propositional logic, no modal operators are needed. Our verification builds on a finite complete prefix of a certain T-system attached to the Boolean system. It splits the processes of the Boolean sy...

  4. Mining TCGA data using Boolean implications.

    Science.gov (United States)

    Sinha, Subarna; Tsang, Emily K; Zeng, Haoyang; Meister, Michela; Dill, David L

    2014-01-01

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

  5. Mining TCGA Data Using Boolean Implications

    Science.gov (United States)

    Sinha, Subarna; Tsang, Emily K.; Zeng, Haoyang; Meister, Michela; Dill, David L.

    2014-01-01

    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/. PMID:25054200

  6. Mining TCGA data using Boolean implications.

    Directory of Open Access Journals (Sweden)

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

  7. Boolean gates on actin filaments

    Science.gov (United States)

    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.

  8. Evolving sensitivity balances Boolean Networks.

    Directory of Open Access Journals (Sweden)

    Jamie X Luo

    Full Text Available We investigate the sensitivity of Boolean Networks (BNs to mutations. We are interested in Boolean Networks as a model of Gene Regulatory Networks (GRNs. We adopt Ribeiro and Kauffman's Ergodic Set and use it to study the long term dynamics of a BN. We define the sensitivity of a BN to be the mean change in its Ergodic Set structure under all possible loss of interaction mutations. In silico experiments were used to selectively evolve BNs for sensitivity to losing interactions. We find that maximum sensitivity was often achievable and resulted in the BNs becoming topologically balanced, i.e. they evolve towards network structures in which they have a similar number of inhibitory and excitatory interactions. In terms of the dynamics, the dominant sensitivity strategy that evolved was to build BNs with Ergodic Sets dominated by a single long limit cycle which is easily destabilised by mutations. We discuss the relevance of our findings in the context of Stem Cell Differentiation and propose a relationship between pluripotent stem cells and our evolved sensitive networks.

  9. Linear Algebra and Smarandache Linear Algebra

    OpenAIRE

    Vasantha, Kandasamy

    2003-01-01

    The present book, on Smarandache linear algebra, not only studies the Smarandache analogues of linear algebra and its applications, it also aims to bridge the need for new research topics pertaining to linear algebra, purely in the algebraic sense. We have introduced Smarandache semilinear algebra, Smarandache bilinear algebra and Smarandache anti-linear algebra and their fuzzy equivalents. Moreover, in this book, we have brought out the study of linear algebra and ve...

  10. A Representation of Quantum Measurement in Nonassociative Algebras

    CERN Document Server

    Niestegge, Gerd

    2010-01-01

    Starting from an abstract setting for the Lueders - von Neumann quantum measurement process and its interpretation as a probability conditionalization rule in a non-Boolean event structure, the author derived a certain generalization of operator algebras in a preceding paper. This is an order-unit space with some specific properties. It becomes a Jordan operator algebra under a certain set of additional conditions, but does not own a multiplication operation in the most general case. A major objective of the present paper is the search for such examples of the structure mentioned above that do not stem from Jordan operator algebras; first natural candidates are matrix algebras over the octonions and other nonassociative rings. Therefore, the case when a nonassociative commutative multiplication exists is studied without assuming that it satisfies the Jordan condition. The characteristics of the resulting algebra are analyzed. This includes the uniqueness of the spectral resolution as well as a criterion for i...

  11. Robust Reachability of Boolean Control Networks.

    Science.gov (United States)

    Li, Fangfei; Tang, Yang

    2016-04-20

    Boolean networks serve a powerful tool in analysis of genetic regulatory networks since it emphasizes the fundamental principles and establishes a nature framework for capturing the dynamics of regulation of cellular states. In this paper, the robust reachability of Boolean control networks is investigated by means of semi-tensor product. Necessary and sufficient conditions for the robust reachability of Boolean control networks are provided, in which control inputs relying on disturbances or not are considered, respectively. Besides, the corresponding control algorithms are developed for these two cases. A reduced model of the lac operon in the Escherichia coli is presented to show the effectiveness of the presented results.

  12. Flexible method for Boolean information retrieval

    Energy Technology Data Exchange (ETDEWEB)

    Salton, G.; Wu, H.

    1983-01-01

    A new flexible retrieval system is described which makes it possible to relax the strict conditions of Boolean query logic thereby retrieving useful items that are rejected in a conventional retrieval situation. The query structure inherent in the Boolean system is preserved, while at the same time weighted terms may be incorporated into both queries and stored documents; the retrieved output can also be ranked in strict similarity order with the user queries. A conventional retrieval system can be modified to make use of the flexible metric system. Laboratory tests indicate that the extended system produces better retrieval output than either the Boolean or the vector processing systems. 11 references.

  13. Kiddie Algebra

    Science.gov (United States)

    Cavanagh, Sean

    2009-01-01

    As educators and policymakers search for ways to prepare students for the rigors of algebra, teachers in the Helena, Montana, school system are starting early by attempting to nurture students' algebraic-reasoning ability, as well as their basic number skills, in early elementary school, rather than waiting until middle or early high school.…

  14. Algebra-Geometry of Piecewise Algebraic Varieties

    Institute of Scientific and Technical Information of China (English)

    Chun Gang ZHU; Ren Hong WANG

    2012-01-01

    Algebraic variety is the most important subject in classical algebraic geometry.As the zero set of multivariate splines,the piecewise algebraic variety is a kind generalization of the classical algebraic variety.This paper studies the correspondence between spline ideals and piecewise algebraic varieties based on the knowledge of algebraic geometry and multivariate splines.

  15. Adiabatic quantum gates and Boolean functions

    Energy Technology Data Exchange (ETDEWEB)

    Andrecut, M; Ali, M K [Department of Physics, University of Lethbridge, Lethbridge, AB, T1K 3M4 (Canada)

    2004-06-25

    We discuss the logical implementation of quantum gates and Boolean functions in the framework of quantum adiabatic method, which uses the language of ground states, spectral gaps and Hamiltonians instead of the standard unitary transformation language. (letter to the editor)

  16. Boolean networks with reliable dynamics

    CERN Document Server

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

  17. Stability of Boolean Multiplex Networks

    CERN Document Server

    Cozzo, Emanuele; Moreno, Yamir

    2012-01-01

    We extend the formalism of Random Boolean Networks with canalizing rules to multilevel complex networks. The formalism allows to model genetic networks in which each gene might take part in more than one signaling pathway. We use a semi-annealed approach to study the stability of this class of models when coupled in a multiplex network and show that the analytical results are in good agreement with numerical simulations. Our main finding is that the multiplex structure provides a mechanism for the stabilization of the system and of chaotic regimes of individual layers. Our results help understanding why some genetic networks that are theoretically expected to operate in the chaotic regime can actually display dynamical stability.

  18. Generalizing Boolean Satisfiability II: Theory

    CERN Document Server

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

  19. Local Correction of Boolean Functions

    CERN Document Server

    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.

  20. Geometric Algebra

    CERN Document Server

    Chisolm, Eric

    2012-01-01

    This is an introduction to geometric algebra, an alternative to traditional vector algebra that expands on it in two ways: 1. In addition to scalars and vectors, it defines new objects representing subspaces of any dimension. 2. It defines a product that's strongly motivated by geometry and can be taken between any two objects. For example, the product of two vectors taken in a certain way represents their common plane. This system was invented by William Clifford and is more commonly known as Clifford algebra. It's actually older than the vector algebra that we use today (due to Gibbs) and includes it as a subset. Over the years, various parts of Clifford algebra have been reinvented independently by many people who found they needed it, often not realizing that all those parts belonged in one system. This suggests that Clifford had the right idea, and that geometric algebra, not the reduced version we use today, deserves to be the standard "vector algebra." My goal in these notes is to describe geometric al...

  1. On Boolean matrices with full factor rank

    Energy Technology Data Exchange (ETDEWEB)

    Shitov, Ya [National Research University " Higher School of Economics" , Moscow (Russian Federation)

    2013-11-30

    It is demonstrated that every (0,1)-matrix of size n×m having Boolean rank n contains a column with at least √n/2−1 zero entries. This bound is shown to be asymptotically optimal. As a corollary, it is established that the size of a full-rank Boolean matrix is bounded from above by a function of its tropical and determinantal ranks. Bibliography: 16 titles.

  2. Stochastic coupling of two random Boolean networks

    Energy Technology Data Exchange (ETDEWEB)

    Ho, M.-C. [Department of Physics, National Kaohsiung Normal University, Kaohsiung, Taiwan (China)]. E-mail: t1603@nknucc.nknu.edu.tw; Hung, Y.-C. [Department of Physics, National Sun Yat-sen University, Kaohsiung, Taiwan (China)]. E-mail: d9123801@student.nsysu.edu.tw; Jiang, I-M. [Department of Physics, National Sun Yat-sen University, Kaohsiung, Taiwan (China)

    2005-08-29

    We study the dynamics of two coupled random Boolean networks. Based on the Boolean model studied by Andrecut and Ali [Int. J. Mod. Phys. B 15 (2001) 17] and the stochastic coupling techniques, the density evolution of networks is precisely described by two deterministic coupled polynomial maps. The iteration results of the model match the real networks well. By using MSE and the maximal Lyapunov exponents, the synchronization phenomena of coupled networks is also under our discussion.

  3. Symmetry in critical random Boolean network dynamics

    Science.gov (United States)

    Hossein, Shabnam; Reichl, Matthew D.; Bassler, Kevin E.

    2014-04-01

    Using Boolean networks as prototypical examples, the role of symmetry in the dynamics of heterogeneous complex systems is explored. We show that symmetry of the dynamics, especially in critical states, is a controlling feature that can be used both to greatly simplify analysis and to characterize different types of dynamics. Symmetry in Boolean networks is found by determining the frequency at which the various Boolean output functions occur. There are classes of functions that consist of Boolean functions that behave similarly. These classes are orbits of the controlling symmetry group. We find that the symmetry that controls the critical random Boolean networks is expressed through the frequency by which output functions are utilized by nodes that remain active on dynamical attractors. This symmetry preserves canalization, a form of network robustness. We compare it to a different symmetry known to control the dynamics of an evolutionary process that allows Boolean networks to organize into a critical state. Our results demonstrate the usefulness and power of using the symmetry of the behavior of the nodes to characterize complex network dynamics, and introduce an alternative approach to the analysis of heterogeneous complex systems.

  4. Testing Booleanity and the Uncertainty Principle

    CERN Document Server

    Gur, Tom

    2012-01-01

    Let f:{-1,1}^n -> R be a real function on the hypercube, given by its discrete Fourier expansion, or, equivalently, represented as a multilinear polynomial. We say that it is Boolean if its image is in {-1,1}. We show that every function on the hypercube with a sparse Fourier expansion must either be Boolean or far from Boolean. In particular, we show that a multilinear polynomial with at most k terms must either be Boolean, or output values different than -1 or 1 for a fraction of at least 2/(k+2)^2 of its domain. It follows that given black box access to f, together with the guarantee that its representation as a multilinear polynomial has at most k terms, one can test Booleanity using O(k^2) queries. We show an Omega(k) queries lower bound for this problem. We also consider the problem of deciding if a function is Boolean, given its explicit representation as a k term multilinear polynomial. The naive approach of evaluating it at every input has O(kn2^n) time complexity. For large k (i.e, exponential) we p...

  5. Symmetry in critical random Boolean network dynamics.

    Science.gov (United States)

    Hossein, Shabnam; Reichl, Matthew D; Bassler, Kevin E

    2014-04-01

    Using Boolean networks as prototypical examples, the role of symmetry in the dynamics of heterogeneous complex systems is explored. We show that symmetry of the dynamics, especially in critical states, is a controlling feature that can be used both to greatly simplify analysis and to characterize different types of dynamics. Symmetry in Boolean networks is found by determining the frequency at which the various Boolean output functions occur. There are classes of functions that consist of Boolean functions that behave similarly. These classes are orbits of the controlling symmetry group. We find that the symmetry that controls the critical random Boolean networks is expressed through the frequency by which output functions are utilized by nodes that remain active on dynamical attractors. This symmetry preserves canalization, a form of network robustness. We compare it to a different symmetry known to control the dynamics of an evolutionary process that allows Boolean networks to organize into a critical state. Our results demonstrate the usefulness and power of using the symmetry of the behavior of the nodes to characterize complex network dynamics, and introduce an alternative approach to the analysis of heterogeneous complex systems.

  6. College algebra

    CERN Document Server

    Kolman, Bernard

    1985-01-01

    College Algebra, Second Edition is a comprehensive presentation of the fundamental concepts and techniques of algebra. The book incorporates some improvements from the previous edition to provide a better learning experience. It provides sufficient materials for use in the study of college algebra. It contains chapters that are devoted to various mathematical concepts, such as the real number system, the theory of polynomial equations, exponential and logarithmic functions, and the geometric definition of each conic section. Progress checks, warnings, and features are inserted. Every chapter c

  7. Abstract algebra

    CERN Document Server

    Garrett, Paul B

    2007-01-01

    Designed for an advanced undergraduate- or graduate-level course, Abstract Algebra provides an example-oriented, less heavily symbolic approach to abstract algebra. The text emphasizes specifics such as basic number theory, polynomials, finite fields, as well as linear and multilinear algebra. This classroom-tested, how-to manual takes a more narrative approach than the stiff formalism of many other textbooks, presenting coherent storylines to convey crucial ideas in a student-friendly, accessible manner. An unusual feature of the text is the systematic characterization of objects by universal

  8. Sensitivity analysis of biological Boolean networks using information fusion based on nonadditive set functions

    Science.gov (United States)

    2014-01-01

    Background An algebraic method for information fusion based on nonadditive set functions is used to assess the joint contribution of Boolean network attributes to the sensitivity of the network to individual node mutations. The node attributes or characteristics under consideration are: in-degree, out-degree, minimum and average path lengths, bias, average sensitivity of Boolean functions, and canalizing degrees. The impact of node mutations is assessed using as target measure the average Hamming distance between a non-mutated/wild-type network and a mutated network. Results We find that for a biochemical signal transduction network consisting of several main signaling pathways whose nodes represent signaling molecules (mainly proteins), the algebraic method provides a robust classification of attribute contributions. This method indicates that for the biochemical network, the most significant impact is generated mainly by the combined effects of two attributes: out-degree, and average sensitivity of nodes. Conclusions The results support the idea that both topological and dynamical properties of the nodes need to be under consideration. The algebraic method is robust against the choice of initial conditions and partition of data sets in training and testing sets for estimation of the nonadditive set functions of the information fusion procedure. PMID:25189194

  9. 高阶布尔网络的结构%Structure of higher order Boolean networks*

    Institute of Scientific and Technical Information of China (English)

    李志强; 赵寅; 程代展

    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代数形式的关系.

  10. Elementary algebra

    CERN Document Server

    McKeague, Charles P

    1981-01-01

    Elementary Algebra 2e, Second Edition focuses on the basic principles, operations, and approaches involved in elementary algebra. The book first tackles the basics, linear equations and inequalities, and graphing and linear systems. Discussions focus on the substitution method, solving linear systems by graphing, solutions to linear equations in two variables, multiplication property of equality, word problems, addition property of equality, and subtraction, addition, multiplication, and division of real numbers. The manuscript then examines exponents and polynomials, factoring, and rational e

  11. Elementary algebra

    CERN Document Server

    McKeague, Charles P

    1986-01-01

    Elementary Algebra, Third Edition focuses on the basic principles, operations, and approaches involved in elementary algebra. The book first ponders on the basics, linear equations and inequalities, and graphing and linear systems. Discussions focus on the elimination method, solving linear systems by graphing, word problems, addition property of equality, solving linear equations, linear inequalities, addition and subtraction of real numbers, and properties of real numbers. The text then takes a look at exponents and polynomials, factoring, and rational expressions. Topics include reducing ra

  12. On the average sensitivity of laced Boolean functions

    CERN Document Server

    jiyou, Li

    2011-01-01

    In this paper we obtain the average sensitivity of the laced Boolean functions. This confirms a conjecture of Shparlinski. We also compute the weights of the laced Boolean functions and show that they are almost balanced.

  13. Linear algebra and probability for computer science applications

    CERN Document Server

    Davis, Ernest

    2012-01-01

    MATLABDesk calculator operations Booleans Nonstandard numbers Loops and conditionals Script file Functions Variable scope and parameter passingI: Linear Algebra Vectors Definition of vectors Applications of vectorsBasic operations on vectorsDot productVectors in MATLAB: Basic operationsPlotting vectors in MATLABVectors in other programming languagesMatrices Definition of matrices Applications of matrices Simple operations on matrices Multiplying a matrix times a vector Linear transformation Systems of linear equations Matrix multiplication Vectors as matrices Algebraic properties of matrix mul

  14. Why Do the Quantum Observables Form a Jordan Operator Algebra?

    CERN Document Server

    Niestegge, Gerd

    2010-01-01

    The Jordan algebra structure of the bounded real quantum observables was recognized already in the early days of quantum mechanics. While there are plausible reasons for most parts of this structure, the existence of the distributive nonassociative multiplication operation is hard to justify from a physical or statistical point of view. Considering the non-Boolean extension of classical probabilities, presented in a recent paper, it is shown in this paper that such a multiplication operation can be derived from certain properties of the conditional probabilities and the observables, i.e., from postulates with a clear statistical interpretation. The well-known close relation between Jordan operator algebras and C*-algebras then provides the connection to the quantum-mechanical Hilbert space formalism, thus resulting in a novel axiomatic approach to general quantum mechanics that includes the types II and III von Neumann algebras.

  15. Symmetry in Critical Random Boolean Networks Dynamics

    Science.gov (United States)

    Bassler, Kevin E.; Hossein, Shabnam

    2014-03-01

    Using Boolean networks as prototypical examples, the role of symmetry in the dynamics of heterogeneous complex systems is explored. We show that symmetry of the dynamics, especially in critical states, is a controlling feature that can be used to both greatly simplify analysis and to characterize different types of dynamics. Symmetry in Boolean networks is found by determining the frequency at which the various Boolean output functions occur. Classes of functions occur at the same frequency. These classes are orbits of the controlling symmetry group. We find the nature of the symmetry that controls the dynamics of critical random Boolean networks by determining the frequency of output functions utilized by nodes that remain active on dynamical attractors. This symmetry preserves canalization, a form of network robustness. We compare it to a different symmetry known to control the dynamics of an evolutionary process that allows Boolean networks to organize into a critical state. Our results demonstrate the usefulness and power of using symmetry to characterize complex network dynamics, and introduce a novel approach to the analysis of heterogeneous complex systems. This work was supported by the NSF through grants DMR-0908286 and DMR-1206839, and by the AFSOR and DARPA through grant FA9550-12-1-0405.

  16. Simulating Boolean circuits on a DNA computer

    Energy Technology Data Exchange (ETDEWEB)

    Ogihara, Mitsunori; Ray, A. [Univ. of Rochester, NY (United States)

    1997-12-01

    We demonstrate that DNA computers can simulate Boolean circuits with a small overhead. Boolean circuits embody the notion of massively parallel signal processing and are frequently encountered in many parallel algorithms. Many important problems such as sorting, integer arithmetic, and matrix multiplication are known to be computable by small size Boolean circuits much faster than by ordinary sequential digital computers. This paper shows that DNA chemistry allows one to simulate large semi-unbounded fan-in Boolean circuits with a logarithmic slowdown in computation time. Also, for the class NC{sup 1}, the slowdown can be reduced to a constant. In this algorithm we have encoded the inputs, the Boolean AND gates, and the OR gates to DNA oligonucleotide sequences. We operate on the gates and the inputs by standard molecular techniques of sequence-specific annealing, ligation, separation by size, amplification, sequence-specific cleavage, and detection by size. Additional steps of amplification are not necessary for NC{sup 1} circuits. Preliminary biochemical experiments on a small test circuit have produced encouraging results. Further confirmatory experiments are in progress. 19 refs., 3 figs., 1 tab.

  17. A Simple Blueprint for Automatic Boolean Query Processing.

    Science.gov (United States)

    Salton, G.

    1988-01-01

    Describes a new Boolean retrieval environment in which an extended soft Boolean logic is used to automatically construct queries from original natural language formulations provided by users. Experimental results that compare the retrieval effectiveness of this method to conventional Boolean and vector processing are discussed. (27 references)…

  18. Synchronization of coupled large-scale Boolean networks

    Energy Technology Data Exchange (ETDEWEB)

    Li, Fangfei, E-mail: li-fangfei@163.com [Department of Mathematics, East China University of Science and Technology, No. 130, Meilong Road, Shanghai, Shanghai 200237 (China)

    2014-03-15

    This paper investigates the complete synchronization and partial synchronization of two large-scale Boolean networks. First, the aggregation algorithm towards large-scale Boolean network is reviewed. Second, the aggregation algorithm is applied to study the complete synchronization and partial synchronization of large-scale Boolean networks. Finally, an illustrative example is presented to show the efficiency of the proposed results.

  19. Synchronization of coupled large-scale Boolean networks

    Science.gov (United States)

    Li, Fangfei

    2014-03-01

    This paper investigates the complete synchronization and partial synchronization of two large-scale Boolean networks. First, the aggregation algorithm towards large-scale Boolean network is reviewed. Second, the aggregation algorithm is applied to study the complete synchronization and partial synchronization of large-scale Boolean networks. Finally, an illustrative example is presented to show the efficiency of the proposed results.

  20. Color Algebras

    Science.gov (United States)

    Mulligan, Jeffrey B.

    2017-01-01

    A color algebra refers to a system for computing sums and products of colors, analogous to additive and subtractive color mixtures. We would like it to match the well-defined algebra of spectral functions describing lights and surface reflectances, but an exact correspondence is impossible after the spectra have been projected to a three-dimensional color space, because of metamerism physically different spectra can produce the same color sensation. Metameric spectra are interchangeable for the purposes of addition, but not multiplication, so any color algebra is necessarily an approximation to physical reality. Nevertheless, because the majority of naturally-occurring spectra are well-behaved (e.g., continuous and slowly-varying), color algebras can be formulated that are largely accurate and agree well with human intuition. Here we explore the family of algebras that result from associating each color with a member of a three-dimensional manifold of spectra. This association can be used to construct a color product, defined as the color of the spectrum of the wavelength-wise product of the spectra associated with the two input colors. The choice of the spectral manifold determines the behavior of the resulting system, and certain special subspaces allow computational efficiencies. The resulting systems can be used to improve computer graphic rendering techniques, and to model various perceptual phenomena such as color constancy.

  1. Piecewise algebraic varieties

    Institute of Scientific and Technical Information of China (English)

    WANG Renhong; ZHU Chungang

    2004-01-01

    The piecewise algebraic variety is a generalization of the classical algebraic variety. This paper discusses some properties of piecewise algebraic varieties and their coordinate rings based on the knowledge of algebraic geometry.

  2. Generalized exterior algebras

    OpenAIRE

    Marchuk, Nikolay

    2011-01-01

    Exterior algebras and differential forms are widely used in many fields of modern mathematics and theoretical physics. In this paper we define a notion of $N$-metric exterior algebra, which depends on $N$ matrices of structure constants. The usual exterior algebra (Grassmann algebra) can be considered as 0-metric exterior algebra. Clifford algebra can be considered as 1-metric exterior algebra. $N$-metric exterior algebras for $N\\geq2$ can be considered as generalizations of the Grassmann alg...

  3. 关于模态公理系统P1-P5的布尔值%On Boolean Value of the Modal Axiomic System from P1 to P5

    Institute of Scientific and Technical Information of China (English)

    李娜; 路征

    2001-01-01

    证明与模态命题系统S2-S4等价的系统P2-P4的布尔值为1,而分别与S1和S5等价的系统P1和P5的布尔值不能确定. 由此,证明了VB是P2-P4的布尔值模型.%The paper proves that the modal propositional system from P2to P4 of the Boolean value is 1. But,the Boolean value of the system P1 and P5 is undecidable. Therefore, VB (B is a complete Boolean algebra) is the Boolean valued model of the system from P2 to P4.

  4. Linear algebra

    CERN Document Server

    Edwards, Harold M

    1995-01-01

    In his new undergraduate textbook, Harold M Edwards proposes a radically new and thoroughly algorithmic approach to linear algebra Originally inspired by the constructive philosophy of mathematics championed in the 19th century by Leopold Kronecker, the approach is well suited to students in the computer-dominated late 20th century Each proof is an algorithm described in English that can be translated into the computer language the class is using and put to work solving problems and generating new examples, making the study of linear algebra a truly interactive experience Designed for a one-semester course, this text adopts an algorithmic approach to linear algebra giving the student many examples to work through and copious exercises to test their skills and extend their knowledge of the subject Students at all levels will find much interactive instruction in this text while teachers will find stimulating examples and methods of approach to the subject

  5. Algebraic Groups

    DEFF Research Database (Denmark)

    2007-01-01

    of algebraic groups (in a broad sense) has seen important developments in several directions, also related to representation theory and algebraic geometry. The workshop aimed at presenting some of these developments in order to make them accessible to a "general audience" of algebraic group......-theorists, and to stimulate contacts between participants. Each of the first four days was dedicated to one area of research that has recently seen decisive progress: \\begin{itemize} \\item structure and classification of wonderful varieties, \\item finite reductive groups and character sheaves, \\item quantum cohomology...... of homogeneous varieties, \\item representation categories and their connections to orbits and flag varieties. \\end{itemize} The first three days started with survey talks that will help to make the subject accessible to the next generation. The talks on the last day introduced to several recent advances...

  6. Linear algebra

    CERN Document Server

    Liesen, Jörg

    2015-01-01

    This self-contained textbook takes a matrix-oriented approach to linear algebra and presents a complete theory, including all details and proofs, culminating in the Jordan canonical form and its proof. Throughout the development, the applicability of the results is highlighted. Additionally, the book presents special topics from applied linear algebra including matrix functions, the singular value decomposition, the Kronecker product and linear matrix equations. The matrix-oriented approach to linear algebra leads to a better intuition and a deeper understanding of the abstract concepts, and therefore simplifies their use in real world applications. Some of these applications are presented in detailed examples. In several ‘MATLAB-Minutes’ students can comprehend the concepts and results using computational experiments. Necessary basics for the use of MATLAB are presented in a short introduction. Students can also actively work with the material and practice their mathematical skills in more than 300 exerc...

  7. Boolean nested canalizing functions: a comprehensive analysis

    CERN Document Server

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

  8. Forced synchronization of autonomous dynamical Boolean networks.

    Science.gov (United States)

    Rivera-Durón, R R; Campos-Cantón, E; Campos-Cantón, I; Gauthier, Daniel J

    2015-08-01

    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.

  9. Forced synchronization of autonomous dynamical Boolean networks

    Energy Technology Data Exchange (ETDEWEB)

    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.

  10. Linear algebra

    CERN Document Server

    Allenby, Reg

    1995-01-01

    As the basis of equations (and therefore problem-solving), linear algebra is the most widely taught sub-division of pure mathematics. Dr Allenby has used his experience of teaching linear algebra to write a lively book on the subject that includes historical information about the founders of the subject as well as giving a basic introduction to the mathematics undergraduate. The whole text has been written in a connected way with ideas introduced as they occur naturally. As with the other books in the series, there are many worked examples.Solutions to the exercises are available onlin

  11. Basic algebra

    CERN Document Server

    Jacobson, Nathan

    2009-01-01

    A classic text and standard reference for a generation, this volume and its companion are the work of an expert algebraist who taught at Yale for two decades. Nathan Jacobson's books possess a conceptual and theoretical orientation, and in addition to their value as classroom texts, they serve as valuable references.Volume I explores all of the topics typically covered in undergraduate courses, including the rudiments of set theory, group theory, rings, modules, Galois theory, polynomials, linear algebra, and associative algebra. Its comprehensive treatment extends to such rigorous topics as L

  12. Lie algebras

    CERN Document Server

    Jacobson, Nathan

    1979-01-01

    Lie group theory, developed by M. Sophus Lie in the 19th century, ranks among the more important developments in modern mathematics. Lie algebras comprise a significant part of Lie group theory and are being actively studied today. This book, by Professor Nathan Jacobson of Yale, is the definitive treatment of the subject and can be used as a textbook for graduate courses.Chapter I introduces basic concepts that are necessary for an understanding of structure theory, while the following three chapters present the theory itself: solvable and nilpotent Lie algebras, Carlan's criterion and its

  13. Linear algebra

    CERN Document Server

    Stoll, R R

    1968-01-01

    Linear Algebra is intended to be used as a text for a one-semester course in linear algebra at the undergraduate level. The treatment of the subject will be both useful to students of mathematics and those interested primarily in applications of the theory. The major prerequisite for mastering the material is the readiness of the student to reason abstractly. Specifically, this calls for an understanding of the fact that axioms are assumptions and that theorems are logical consequences of one or more axioms. Familiarity with calculus and linear differential equations is required for understand

  14. Dynamics of Random Boolean Networks under Fully Asynchronous Stochastic Update Based on Linear Representation

    Science.gov (United States)

    Luo, Chao; Wang, Xingyuan

    2013-01-01

    A novel algebraic approach is proposed to study dynamics of asynchronous random Boolean networks where a random number of nodes can be updated at each time step (ARBNs). In this article, the logical equations of ARBNs are converted into the discrete-time linear representation and dynamical behaviors of systems are investigated. We provide a general formula of network transition matrices of ARBNs as well as a necessary and sufficient algebraic criterion to determine whether a group of given states compose an attractor of length in ARBNs. Consequently, algorithms are achieved to find all of the attractors and basins in ARBNs. Examples are showed to demonstrate the feasibility of the proposed scheme. PMID:23785502

  15. Boolean differentiation and integration using Karnaugh maps

    Science.gov (United States)

    Tucker, J. H.; Tapia, M. A.; Bennett, A. W.

    1977-01-01

    Algorithms are presented for differentiation and integration of Boolean functions by means of Karnaugh maps. The algorithms are considered simple when the number of variables is six or less; in this case Boolean differentiation and integration is said to be as easy as the Karnaugh map method of simplifying switching functions. It is suggested that the algorithms would be useful in the analysis of faults in combinational systems and in the synthesis of asynchronous sequential systems which utilize edge-sensitive flip-flops.

  16. Coherent spaces, Boolean rings and quantum gates

    Science.gov (United States)

    Vourdas, A.

    2016-10-01

    Coherent spaces spanned by a finite number of coherent states, are introduced. Their coherence properties are studied, using the Dirac contour representation. It is shown that the corresponding projectors resolve the identity, and that they transform into projectors of the same type, under displacement transformations, and also under time evolution. The set of these spaces, with the logical OR and AND operations is a distributive lattice, and with the logical XOR and AND operations is a Boolean ring (Stone's formalism). Applications of this Boolean ring into classical CNOT gates with n-ary variables, and also quantum CNOT gates with coherent states, are discussed.

  17. Inferring Boolean network states from partial information

    Science.gov (United States)

    2013-01-01

    Networks of molecular interactions regulate key processes in living cells. Therefore, understanding their functionality is a high priority in advancing biological knowledge. Boolean networks are often used to describe cellular networks mathematically and are fitted to experimental datasets. The fitting often results in ambiguities since the interpretation of the measurements is not straightforward and since the data contain noise. In order to facilitate a more reliable mapping between datasets and Boolean networks, we develop an algorithm that infers network trajectories from a dataset distorted by noise. We analyze our algorithm theoretically and demonstrate its accuracy using simulation and microarray expression data. PMID:24006954

  18. EXACT SIMULATION OF A BOOLEAN MODEL

    Directory of Open Access Journals (Sweden)

    Christian Lantuéjoul

    2013-06-01

    Full Text Available A Boolean model is a union of independent objects (compact random subsets located at Poisson points. Two algorithms are proposed for simulating a Boolean model in a bounded domain. The first one applies only to stationary models. It generates the objects prior to their Poisson locations. Two examples illustrate its applicability. The second algorithm applies to stationary and non-stationary models. It generates the Poisson points prior to the objects. Its practical difficulties of implementation are discussed. Both algorithms are based on importance sampling techniques, and the generated objects are weighted.

  19. Information encryption systems based on Boolean functions

    Directory of Open Access Journals (Sweden)

    Aureliu Zgureanu

    2011-02-01

    Full Text Available An information encryption system based on Boolean functions is proposed. Information processing is done using multidimensional matrices, performing logical operations with these matrices. At the basis of ensuring high level security of the system the complexity of solving the problem of building systems of Boolean functions that depend on many variables (tens and hundreds is set. Such systems represent the private key. It varies both during the encryption and decryption of information, and during the transition from one message to another.

  20. Analysis of affinely equivalent Boolean functions

    Institute of Scientific and Technical Information of China (English)

    MENG QingShu; ZHANG HuanGuo; YANG Min; WANG ZhangYi

    2007-01-01

    By some basic transforms and invariant theory, we give two results: 1) an algorithm,which can be used to judge if two Boolean functions are affinely equivalent and to obtain the equivalence relationship if they are equivalent. This is useful in studying Boolean functions and in engineering. For example, we classify all 8-variable homogeneous bent functions of degree 3 into two classes; 2) Reed-Muller codes R(4,6)/R(1,6), R(3,7)/R(1,7) are classified efficiently.

  1. Algebraic Stacks

    Indian Academy of Sciences (India)

    Tomás L Gómez

    2001-02-01

    This is an expository article on the theory of algebraic stacks. After introducing the general theory, we concentrate in the example of the moduli stack of vector bundles, giving a detailed comparison with the moduli scheme obtained via geometric invariant theory.

  2. Algebraic Topology

    CERN Document Server

    Oliver, Bob; Pawałowski, Krzystof

    1991-01-01

    As part of the scientific activity in connection with the 70th birthday of the Adam Mickiewicz University in Poznan, an international conference on algebraic topology was held. In the resulting proceedings volume, the emphasis is on substantial survey papers, some presented at the conference, some written subsequently.

  3. Central simple Poisson algebras

    Institute of Scientific and Technical Information of China (English)

    SU Yucai; XU Xiaoping

    2004-01-01

    Poisson algebras are fundamental algebraic structures in physics and symplectic geometry. However, the structure theory of Poisson algebras has not been well developed. In this paper, we determine the structure of the central simple Poisson algebras related to locally finite derivations, over an algebraically closed field of characteristic zero.The Lie algebra structures of these Poisson algebras are in general not finitely-graded.

  4. Competitive learning of monotone Boolean functions

    OpenAIRE

    2014-01-01

    We apply competitive analysis onto the problem of minimizing the number of queries to an oracle to completely reconstruct a given monotone Boolean function. Besides lower and upper bounds on the competitivity we determine optimal deterministic online algorithms for the smallest problem instances.

  5. Demonstrating Boolean Logic Using Simple Electrical Circuits

    Science.gov (United States)

    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.

  6. A Boolean Map Theory of Visual Attention

    Science.gov (United States)

    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…

  7. On Fuzzy Ideals of BL-Algebras

    Directory of Open Access Journals (Sweden)

    Biao Long Meng

    2014-01-01

    Full Text Available In this paper we investigate further properties of fuzzy ideals of a BL-algebra. The notions of fuzzy prime ideals, fuzzy irreducible ideals, and fuzzy Gödel ideals of a BL-algebra are introduced and their several properties are investigated. We give a procedure to generate a fuzzy ideal by a fuzzy set. We prove that every fuzzy irreducible ideal is a fuzzy prime ideal but a fuzzy prime ideal may not be a fuzzy irreducible ideal and prove that a fuzzy prime ideal ω is a fuzzy irreducible ideal if and only if ω0=1 and |Im⁡(ω|=2. We give the Krull-Stone representation theorem of fuzzy ideals in BL-algebras. Furthermore, we prove that the lattice of all fuzzy ideals of a BL-algebra is a complete distributive lattice. Finally, it is proved that every fuzzy Boolean ideal is a fuzzy Gödel ideal, but the converse implication is not true.

  8. On annihilators in BL-algebras

    Directory of Open Access Journals (Sweden)

    Zou Yu Xi

    2016-01-01

    Full Text Available In the paper, we introduce the notion of annihilators in BL-algebras and investigate some related properties of them. We get that the ideal lattice (I(L, ⊆ is pseudo-complemented, and for any ideal I, its pseudo-complement is the annihilator I⊥ of I. Also, we define the An (L to be the set of all annihilators of L, then we have that (An(L; ⋂,∧An(L,⊥,{0}, L is a Boolean algebra. In addition, we introduce the annihilators of a nonempty subset X of L with respect to an ideal I and study some properties of them. As an application, we show that if I and J are ideals in a BL-algebra L, then JI⊥$J_I^ \\bot $ is the relative pseudo-complement of J with respect to I in the ideal lattice (I(L, ⊆. Moreover, we get some properties of the homomorphism image of annihilators, and also give the necessary and sufficient condition of the homomorphism image and the homomorphism pre-image of an annihilator to be an annihilator. Finally, we introduce the notion of α-ideal and give a notation E(I . We show that (E(I(L, ∧E, ∨E, E(0, E(L is a pseudo-complemented lattice, a complete Brouwerian lattice and an algebraic lattice, when L is a BL-chain or a finite product of BL-chains.

  9. Algebraic theory of molecules

    CERN Document Server

    Iachello, F

    1995-01-01

    1. The Wave Mechanics of Diatomic Molecules. 2. Summary of Elements of Algebraic Theory. 3. Mechanics of Molecules. 4. Three-Body Algebraic Theory. 5. Four-Body Algebraic Theory. 6. Classical Limit and Coordinate Representation. 8. Prologue to the Future. Appendices. Properties of Lie Algebras; Coupling of Algebras; Hamiltonian Parameters

  10. Effect of memory in non-Markovian Boolean networks

    CERN Document Server

    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.

  11. Real Algebraic Geometry

    CERN Document Server

    Mahé, Louis; Roy, Marie-Françoise

    1992-01-01

    Ten years after the first Rennes international meeting on real algebraic geometry, the second one looked at the developments in the subject during the intervening decade - see the 6 survey papers listed below. Further contributions from the participants on recent research covered real algebra and geometry, topology of real algebraic varieties and 16thHilbert problem, classical algebraic geometry, techniques in real algebraic geometry, algorithms in real algebraic geometry, semialgebraic geometry, real analytic geometry. CONTENTS: Survey papers: M. Knebusch: Semialgebraic topology in the last ten years.- R. Parimala: Algebraic and topological invariants of real algebraic varieties.- Polotovskii, G.M.: On the classification of decomposing plane algebraic curves.- Scheiderer, C.: Real algebra and its applications to geometry in the last ten years: some major developments and results.- Shustin, E.L.: Topology of real plane algebraic curves.- Silhol, R.: Moduli problems in real algebraic geometry. Further contribu...

  12. Exact and heuristic methods for solving Boolean games

    OpenAIRE

    DE CLERCQ, Sofie; Bauters, Kim; Schockaert, Steven; Mihaylov, Mihail; Nowé, Ann; De Cock, Martine

    2015-01-01

    Boolean games are a framework for reasoning about the rational behavior of agents whose goals are formalized using propositional formulas. Compared to normal form games, a well-studied and related game framework, Boolean games allow for an intuitive and more compact representation of the agents’ goals. So far, Boolean games have been mainly studied in the literature from the Knowledge Representation perspective, and less attention has been paid on the algorithmic issues underlying the computa...

  13. Solvable quadratic Lie algebras

    Institute of Scientific and Technical Information of China (English)

    ZHU; Linsheng

    2006-01-01

    A Lie algebra endowed with a nondegenerate, symmetric, invariant bilinear form is called a quadratic Lie algebra. In this paper, the author investigates the structure of solvable quadratic Lie algebras, in particular, the solvable quadratic Lie algebras whose Cartan subalgebras consist of semi-simple elements, the author presents a procedure to construct a class of quadratic Lie algebras from the point of view of cohomology and shows that all solvable quadratic Lie algebras can be obtained in this way.

  14. Piecewise-Koszul algebras

    Institute of Scientific and Technical Information of China (English)

    2007-01-01

    It is a small step toward the Koszul-type algebras. The piecewise-Koszul algebras are,in general, a new class of quadratic algebras but not the classical Koszul ones, simultaneously they agree with both the classical Koszul and higher Koszul algebras in special cases. We give a criteria theorem for a graded algebra A to be piecewise-Koszul in terms of its Yoneda-Ext algebra E(A), and show an A∞-structure on E(A). Relations between Koszul algebras and piecewise-Koszul algebras are discussed. In particular, our results are related to the third question of Green-Marcos.

  15. A Generalization of J-Boolean Like Rings%J-Boolean like 环的扩张

    Institute of Scientific and Technical Information of China (English)

    秦蕊

    2014-01-01

    对 J-Boolean like环进行了扩张,并且将 J-Boolean like环与广义矩阵环和Morita Context环联系起来,进而探索了部分环为 J-Boolean like环时应具备的条件,且给出若干相关例子。%The paper mainly explored the generalization of J-Boolean like rings ,and connected J-Boolean like rings with generalized matrix rings and Morita Context rings ,then studied the conditions when a part of other rings became J-Boolean like rings ,and listed some examples .

  16. Random Boolean network models and the yeast transcriptional network

    Science.gov (United States)

    Kauffman, Stuart; Peterson, Carsten; Samuelsson, Björn; Troein, Carl

    2003-12-01

    The recently measured yeast transcriptional network is analyzed in terms of simplified Boolean network models, with the aim of determining feasible rule structures, given the requirement of stable solutions of the generated Boolean networks. We find that for ensembles of generated models, those with canalyzing Boolean rules are remarkably stable, whereas those with random Boolean rules are only marginally stable. Furthermore, substantial parts of the generated networks are frozen, in the sense that they reach the same state regardless of initial state. Thus, our ensemble approach suggests that the yeast network shows highly ordered dynamics.

  17. Combinational Logic-Level Verification using Boolean Expression Diagrams

    DEFF Research Database (Denmark)

    Hulgaard, Henrik; Williams, Poul Frederick; Andersen, Henrik Reif

    1997-01-01

    Boolean Expression Diagrams (BEDs) is a new data structure for representing and manipulating Boolean functions. BEDs are a generalization of Binary Decision Diagrams (BDDs) that are capable of representing any Boolean circuit in linear space and still maintain many of the desirable properties...... of BDDs. This paper demonstrates that BEDs are well suited for solving the combinational logic-level verification problem which is, given two combinational circuits, to determine whether they implement the same Boolean functions. Based on all combinational circuits in the ISCAS 85 and LGSynth 91...

  18. The Number of Monotone and Self-Dual Boolean Functions

    Directory of Open Access Journals (Sweden)

    Haviarova L.

    2014-12-01

    Full Text Available In the present paper we study properties of pre-complete class of Boolean functions - monotone Boolean functions. We discuss interval graph, the abbreviated d.n.f., a minimal d.n.f. and a shortest d.n.f. of this function. Then we present a d.n.f. with the highest number of conjunctionsand we determinate the exact number of them. We count the number of monotone Boolean functions with some special properties. In the end we estimate the number of Boolean functionthat are monotone and self-dual at the same time.

  19. Boolean Differentiation Equations Applicable in Reconfigurable Computational Medium

    Directory of Open Access Journals (Sweden)

    Shidlovskiy Stanislav

    2016-01-01

    Full Text Available High performance computing environment synthesis with parallel architecture reconstructing throughout the process itself is described. Synthesized computational medium involving Boolean differential equation calculations so as to function in real-time image processing. Automaton imaging was illustrated involving the rearrangement of every processing medium element to calculate the partial differentials of n-th order in respect to Boolean function variables. The method of obtaining setting codes for each element was also described. An example in calculating 2nd -order Boolean derivative to two differentials in respect to Boolean functions, depending on three arguments within the reconstructible computational medium of 8×8 processing elements was given.

  20. Totally optimal decision trees for Boolean functions

    KAUST Repository

    Chikalov, Igor

    2016-07-28

    We study decision trees which are totally optimal relative to different sets of complexity parameters for Boolean functions. A totally optimal tree is an optimal tree relative to each parameter from the set simultaneously. We consider the parameters characterizing both time (in the worst- and average-case) and space complexity of decision trees, i.e., depth, total path length (average depth), and number of nodes. We have created tools based on extensions of dynamic programming to study totally optimal trees. These tools are applicable to both exact and approximate decision trees, and allow us to make multi-stage optimization of decision trees relative to different parameters and to count the number of optimal trees. Based on the experimental results we have formulated the following hypotheses (and subsequently proved): for almost all Boolean functions there exist totally optimal decision trees (i) relative to the depth and number of nodes, and (ii) relative to the depth and average depth.

  1. Boolean network robotics: a proof of concept

    CERN Document Server

    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.

  2. Energy and criticality in random Boolean networks

    Energy Technology Data Exchange (ETDEWEB)

    Andrecut, M. [Institute for Biocomplexity and Informatics, University of Calgary, 2500 University Drive NW, Calgary, Alberta, T2N 1N4 (Canada)], E-mail: mandrecu@ucalgary.ca; Kauffman, S.A. [Institute for Biocomplexity and Informatics, University of Calgary, 2500 University Drive NW, Calgary, Alberta, T2N 1N4 (Canada)

    2008-06-30

    The central issue of the research on the Random Boolean Networks (RBNs) model is the characterization of the critical transition between ordered and chaotic phases. Here, we discuss an approach based on the 'energy' associated with the unsatisfiability of the Boolean functions in the RBNs model, which provides an upper bound estimation for the energy used in computation. We show that in the ordered phase the RBNs are in a 'dissipative' regime, performing mostly 'downhill' moves on the 'energy' landscape. Also, we show that in the disordered phase the RBNs have to 'hillclimb' on the 'energy' landscape in order to perform computation. The analytical results, obtained using Derrida's approximation method, are in complete agreement with numerical simulations.

  3. Non-monotony and Boolean automata networks

    CERN Document Server

    Noual, Mathilde; Sené, Sylvain

    2011-01-01

    This paper aims at setting the keystone of a prospective theoretical study on the role of non-monotone interactions in biological regulation networks. Focusing on discrete models of these networks, namely, Boolean automata networks, we propose to analyse the contribution of non-monotony to the diversity and complexity in their dynamical behaviours. More precisely, in this paper, we start by detailing some motivations, both mathematical and biological, for our interest in non-monotony, and we discuss how it may account for phenomena that cannot be produced by monotony only. Then, to build some understanding in this direction, we propose some preliminary results on the dynamical behaviour of some specific non-monotone Boolean automata networks called XOR circulant networks.

  4. Classical Boolean logic gates with quantum systems

    Energy Technology Data Exchange (ETDEWEB)

    Renaud, N; Joachim, C, E-mail: n-renaud@northwestern.edu [Nanoscience Group and MANA Satellite CEMES/CNRS, 29 rue J Marvig, BP 94347, 31055 Toulouse Cedex (France)

    2011-04-15

    An analytical method is proposed to implement any classical Boolean function in a small quantum system by taking the advantage of its electronic transport properties. The logical input, {alpha} = {l_brace}{alpha}{sub 1}, ..., {alpha}{sub N}{r_brace}, is used to control well-identified parameters of the Hamiltonian of the system noted H{sub 0}({alpha}). The logical output is encoded in the tunneling current intensity passing through the quantum system when connected to conducting electrodes. It is demonstrated how to implement the six symmetric two-input/one-output Boolean functions in a quantum system. This system can be switched from one logic function to another by changing its structural parameters. The stability of the logic gates is discussed, perturbing the Hamiltonian with noise sources and studying the effect of decoherence.

  5. Estimation for the simple linear Boolean model

    OpenAIRE

    2006-01-01

    We consider the simple linear Boolean model, a fundamental coverage process also known as the Markov/General/infinity queue. In the model, line segments of independent and identically distributed length are located at the points of a Poisson process. The segments may overlap, resulting in a pattern of "clumps"-regions of the line that are covered by one or more segments-alternating with uncovered regions or "spacings". Study and application of the model have been impeded by the difficult...

  6. Improved Time Complexities for Learning Boolean Networks

    Directory of Open Access Journals (Sweden)

    Chee Keong Kwoh

    2013-09-01

    Full Text Available Existing algorithms for learning Boolean networks (BNs have time complexities of at least O(N · n0:7(k+1, where n is the number of variables, N is the number of samples and k is the number of inputs in Boolean functions. Some recent studies propose more efficient methods with O(N · n2 time complexities. However, these methods can only be used to learn monotonic BNs, and their performances are not satisfactory when the sample size is small. In this paper, we mathematically prove that OR/AND BNs, where the variables are related with logical OR/AND operations, can be found with the time complexity of O(k·(N+ logn·n2, if there are enough noiseless training samples randomly generated from a uniform distribution. We also demonstrate that our method can successfully learn most BNs, whose variables are not related with exclusive OR and Boolean equality operations, with the same order of time complexity for learning OR/AND BNs, indicating our method has good efficiency for learning general BNs other than monotonic BNs. When the datasets are noisy, our method can still successfully identify most BNs with the same efficiency. When compared with two existing methods with the same settings, our method achieves a better comprehensive performance than both of them, especially for small training sample sizes. More importantly, our method can be used to learn all BNs. However, of the two methods that are compared, one can only be used to learn monotonic BNs, and the other one has a much worse time complexity than our method. In conclusion, our results demonstrate that Boolean networks can be learned with improved time complexities.

  7. Boolean approach to common event analysis

    Energy Technology Data Exchange (ETDEWEB)

    Worrell, R.B.; Stack, D.W.

    1980-01-01

    Although different phenomena may be involved, the problem that must be solved for each kind of common event analysis is essentially the same: to determine the effect of common events on the behavior of a system. A Boolean approach to the problem is set forth. Because of the large equations that arise, processing must be done by computers. Vital location analysis is a particular kind of common event analysis that is used to study ways to prevent the sabotage of nuclear reactors. (RWR)

  8. Universal algebra

    CERN Document Server

    Grätzer, George

    1979-01-01

    Universal Algebra, heralded as ". . . the standard reference in a field notorious for the lack of standardization . . .," has become the most authoritative, consistently relied on text in a field with applications in other branches of algebra and other fields such as combinatorics, geometry, and computer science. Each chapter is followed by an extensive list of exercises and problems. The "state of the art" account also includes new appendices (with contributions from B. Jónsson, R. Quackenbush, W. Taylor, and G. Wenzel) and a well-selected additional bibliography of over 1250 papers and books which makes this a fine work for students, instructors, and researchers in the field. "This book will certainly be, in the years to come, the basic reference to the subject." --- The American Mathematical Monthly (First Edition) "In this reviewer's opinion [the author] has more than succeeded in his aim. The problems at the end of each chapter are well-chosen; there are more than 650 of them. The book is especially sui...

  9. Yoneda algebras of almost Koszul algebras

    Indian Academy of Sciences (India)

    Zheng Lijing

    2015-11-01

    Let be an algebraically closed field, a finite dimensional connected (, )-Koszul self-injective algebra with , ≥ 2. In this paper, we prove that the Yoneda algebra of is isomorphic to a twisted polynomial algebra $A^!$ [ ; ] in one indeterminate of degree +1 in which $A^!$ is the quadratic dual of , is an automorphism of $A^!$, and = () for each $t \\in A^!$. As a corollary, we recover Theorem 5.3 of [2].

  10. Reaction-contingency based bipartite Boolean modelling

    Science.gov (United States)

    2013-01-01

    Background Intracellular signalling systems are highly complex, rendering mathematical modelling of large signalling networks infeasible or impractical. Boolean modelling provides one feasible approach to whole-network modelling, but at the cost of dequantification and decontextualisation of activation. That is, these models cannot distinguish between different downstream roles played by the same component activated in different contexts. Results Here, we address this with a bipartite Boolean modelling approach. Briefly, we use a state oriented approach with separate update rules based on reactions and contingencies. This approach retains contextual activation information and distinguishes distinct signals passing through a single component. Furthermore, we integrate this approach in the rxncon framework to support automatic model generation and iterative model definition and validation. We benchmark this method with the previously mapped MAP kinase network in yeast, showing that minor adjustments suffice to produce a functional network description. Conclusions Taken together, we (i) present a bipartite Boolean modelling approach that retains contextual activation information, (ii) provide software support for automatic model generation, visualisation and simulation, and (iii) demonstrate its use for iterative model generation and validation. PMID:23835289

  11. Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function

    OpenAIRE

    Reichardt, Ben W.

    2009-01-01

    The general adversary bound is a semi-definite program (SDP) that lower-bounds the quantum query complexity of a function. We turn this lower bound into an upper bound, by giving a quantum walk algorithm based on the dual SDP that has query complexity at most the general adversary bound, up to a logarithmic factor. In more detail, the proof has two steps, each based on "span programs," a certain linear-algebraic model of computation. First, we give an SDP that outputs for any boolean function...

  12. Generalized exterior algebras

    CERN Document Server

    Marchuk, Nikolay

    2011-01-01

    Exterior algebras and differential forms are widely used in many fields of modern mathematics and theoretical physics. In this paper we define a notion of $N$-metric exterior algebra, which depends on $N$ matrices of structure constants. The usual exterior algebra (Grassmann algebra) can be considered as 0-metric exterior algebra. Clifford algebra can be considered as 1-metric exterior algebra. $N$-metric exterior algebras for $N\\geq2$ can be considered as generalizations of the Grassmann algebra and Clifford algebra. Specialists consider models of gravity that based on a mathematical formalism with two metric tensors. We hope that the considered in this paper 2-metric exterior algebra can be useful for development of this model in gravitation theory. Especially in description of fermions in presence of a gravity field.

  13. WEAKLY ALGEBRAIC REFLEXIVITY AND STRONGLY ALGEBRAIC REFLEXIVITY

    Institute of Scientific and Technical Information of China (English)

    TaoChangli; LuShijie; ChenPeixin

    2002-01-01

    Algebraic reflexivity introduced by Hadwin is related to linear interpolation. In this paper, the concepts of weakly algebraic reflexivity and strongly algebraic reflexivity which are also related to linear interpolation are introduced. Some properties of them are obtained and some relations between them revealed.

  14. Rigidification of algebras over essentially algebraic theories

    CERN Document Server

    Rosicky, J

    2012-01-01

    Badzioch and Bergner proved a rigidification theorem saying that each homotopy simplicial algebra is weakly equivalent to a simplicial algebra. The question is whether this result can be extended from algebraic theories to finite limit theories and from simplicial sets to more general monoidal model categories. We will present some answers to this question.

  15. Control of random Boolean networks via average sensitivity of Boolean functions

    Institute of Scientific and Technical Information of China (English)

    Chen Shi-Jian; Hong Yi-Guang

    2011-01-01

    In this paper, we discuss how to transform the disordered phase into an ordered phase in random Boolean networks. To increase the effectiveness, a control scheme is proposed, which periodically freezes a fraction of the network based on the average sensitivity of Boolean functions of the nodes. Theoretical analysis is carried out to estimate the expected critical value of the fraction, and shows that the critical value is reduced using this scheme compared to that of randomly freezing a fraction of the nodes. Finally, the simulation is given for illustrating the effectiveness of the proposed method.

  16. The Yoneda algebra of a K_2 algebra need not be another K_2 algebra

    OpenAIRE

    Cassidy, T.; Phan, Van C.; Shelton, B.

    2008-01-01

    The Yoneda algebra of a Koszul algebra or a D-Koszul algebra is Koszul. K2 algebras are a natural generalization of Koszul algebras, and one would hope that the Yoneda algebra of a K2 algebra would be another K2 algebra. We show that this is not necessarily the case by constructing a monomial K2 algebra for which the corresponding Yoneda algebra is not K2.

  17. Algebraic cobordism theory attached to algebraic equivalence

    CERN Document Server

    Krishna, Amalendu

    2012-01-01

    After the algebraic cobordism theory of Levine-Morel, we develop a theory of algebraic cobordism modulo algebraic equivalence. We prove that this theory can reproduce Chow groups modulo algebraic equivalence and the zero-th semi-topological K-groups. We also show that with finite coefficients, this theory agrees with the algebraic cobordism theory. We compute our cobordism theory for some low dimensional or special types of varieties. The results on infinite generation of some Griffiths groups by Clemens and on smash-nilpotence by Voevodsky and Voisin are also lifted and reinterpreted in terms of this cobordism theory.

  18. Workshop on Commutative Algebra

    CERN Document Server

    Simis, Aron

    1990-01-01

    The central theme of this volume is commutative algebra, with emphasis on special graded algebras, which are increasingly of interest in problems of algebraic geometry, combinatorics and computer algebra. Most of the papers have partly survey character, but are research-oriented, aiming at classification and structural results.

  19. Probabilistic Concurrent Kleene Algebra

    Directory of Open Access Journals (Sweden)

    Annabelle McIver

    2013-06-01

    Full Text Available We provide an extension of concurrent Kleene algebras to account for probabilistic properties. The algebra yields a unified framework containing nondeterminism, concurrency and probability and is sound with respect to the set of probabilistic automata modulo probabilistic simulation. We use the resulting algebra to generalise the algebraic formulation of a variant of Jones' rely/guarantee calculus.

  20. Generalized Quantum Current Algebras

    Institute of Scientific and Technical Information of China (English)

    ZHAO Liu

    2001-01-01

    Two general families of new quantum-deformed current algebras are proposed and identified both as infinite Hopf family of algebras, a structure which enables one to define "tensor products" of these algebras. The standard quantum affine algebras turn out to be a very special case of the two algebra families, in which case the infinite Hopf family structure degenerates into a standard Hopf algebra. The relationship between the two algebraic families as well as thefr various special examples are discussed, and the free boson representation is also considered.

  1. The Onsager Algebra

    CERN Document Server

    El-Chaar, Caroline

    2012-01-01

    In this thesis, four realizations of the Onsager algebra are explored. We begin with its original definition as introduced by Lars Onsager. We then examine how the Onsager algebra can be presented as a Lie algebra with two generators and two relations. The third realization of the Onsager algebra consists of viewing it as an equivariant map algebra which then gives us the tools to classify its closed ideals. Finally, we examine the Onsager algebra as a subalgebra of the tetrahedron algebra. Using this fourth realization, we explicitly describe all its ideals.

  2. Perturbations of planar algebras

    CERN Document Server

    Das, Paramita; Gupta, Ved Prakash

    2010-01-01

    We introduce the concept of {\\em weight} of a planar algebra $P$ and construct a new planar algebra referred as the {\\em perturbation of $P$} by the weight. We establish a one-to-one correspondence between pivotal structures on 2-categories and perturbations of planar algebras by weights. To each bifinite bimodule over $II_1$-factors, we associate a {\\em bimodule planar algebra} bimodule corresponds naturally with sphericality of the bimodule planar algebra. As a consequence of this, we reproduce an extension of Jones' theorem (of associating 'subfactor planar algebras' to extremal subfactors). Conversely, given a bimodule planar algebra, we construct a bifinite bimodule whose associated bimodule planar algebra is the one which we start with using perturbations and Jones-Walker-Shlyakhtenko-Kodiyalam-Sunder method of reconstructing an extremal subfactor from a subfactor planar algebra. We show that the perturbation class of a bimodule planar algebra contains a unique spherical unimodular bimodule planar algeb...

  3. Constructions of vector output Boolean functions with high generalized nonlinearity

    Institute of Scientific and Technical Information of China (English)

    KE Pin-hui; ZHANG Sheng-yuan

    2008-01-01

    Carlet et al. recently introduced generalized nonlinearity to measure the ability to resist the improved correlation attack of a vector output Boolean function. This article presents a construction of vector output Boolean functions with high generalized nonlinearity using the sample space. The relation between the resilient order and generalized nonlinearity is also discussed.

  4. Boolean Queries and Term Dependencies in Probabilistic Retrieval Models.

    Science.gov (United States)

    Croft, W. Bruce

    1986-01-01

    Proposes approach to integrating Boolean and statistical systems where Boolean queries are interpreted as a means of specifying term dependencies in relevant set of documents. Highlights include series of retrieval experiments designed to test retrieval strategy based on term dependence model and relation of results to other work. (18 references)…

  5. Yangians and transvector algebras

    OpenAIRE

    Molev, A. I.

    1998-01-01

    Olshanski's centralizer construction provides a realization of the Yangian for the Lie algebra gl(n) as a subalgebra in the projective limit of a chain of centralizers in the universal enveloping algebras. We give a modified version of this construction based on a quantum analog of Sylvester's theorem. We then use it to get an algebra homomorphism from the Yangian to the transvector algebra associated with the general linear Lie algebras. The results are applied to identify the elementary rep...

  6. On diamond-free subposets of the Boolean lattice

    CERN Document Server

    Kramer, Lucas; Young, Michael

    2012-01-01

    The Boolean lattice of dimension two, also known as the diamond, consists of four distinct elements with the following property: $A\\subset B,C\\subset D$. A diamond-free family in the $n$-dimensional Boolean lattice is a subposet such that no four elements form a diamond. Note that elements $B$ and $C$ may or may not be related. There is a diamond-free family in the $n$-dimensional Boolean lattice of size $(2-o(1)){n\\choose\\lfloor n/2\\rfloor}$. In this paper, we prove that any diamond-free family in the $n$-dimensional Boolean lattice has size at most $(2.25+o(1)){n\\choose\\lfloor n/2\\rfloor}$. Furthermore, we show that the so-called Lubell function of a diamond-free family in the $n$-dimensional Boolean lattice is at most $2.25+o(1)$, which is asympotically best possible.

  7. Controllability of time-delayed Boolean multiplex control networks under asynchronous stochastic update.

    Science.gov (United States)

    Luo, Chao; Wang, Xingyuan; Liu, Hong

    2014-12-17

    In this article, the controllability of asynchronous Boolean multiplex control networks (ABMCNs) with time delay is studied. Firstly, dynamical model of Boolean multiplex control networks is constructed, which is assumed to be under Harvey' asynchronous update and time delay is introduced both in states and controls. By using of semi-tensor product (STP) approach, the logical dynamics is converted into an equivalent algebraic form by obtaining the control-depending network transition matrices of delayed system. Secondly, a necessary and sufficient condition is proved that only control-depending fixed points of the studied dynamics can be controlled with probability one. Thirdly, respectively for two types of controls, the controllability of dynamical control system is investigated. When initial states and time delay are given, formulae are obtained to show a) the reachable set at time s under specified controls; b) the reachable set at time s under arbitrary controls; c) the reachable probabilities to different destination states. Furthermore, an approach is discussed to find a precise control sequence which can steer dynamical system into a specified target with the maximum reachable probability. Examples are shown to illustrate the feasibility of the proposed scheme.

  8. Controllability of time-delayed Boolean multiplex control networks under asynchronous stochastic update

    Science.gov (United States)

    Luo, Chao; Wang, Xingyuan; Liu, Hong

    2014-01-01

    In this article, the controllability of asynchronous Boolean multiplex control networks (ABMCNs) with time delay is studied. Firstly, dynamical model of Boolean multiplex control networks is constructed, which is assumed to be under Harvey' asynchronous update and time delay is introduced both in states and controls. By using of semi-tensor product (STP) approach, the logical dynamics is converted into an equivalent algebraic form by obtaining the control-depending network transition matrices of delayed system. Secondly, a necessary and sufficient condition is proved that only control-depending fixed points of the studied dynamics can be controlled with probability one. Thirdly, respectively for two types of controls, the controllability of dynamical control system is investigated. When initial states and time delay are given, formulae are obtained to show a) the reachable set at time s under specified controls; b) the reachable set at time s under arbitrary controls; c) the reachable probabilities to different destination states. Furthermore, an approach is discussed to find a precise control sequence which can steer dynamical system into a specified target with the maximum reachable probability. Examples are shown to illustrate the feasibility of the proposed scheme. PMID:25516009

  9. Piecewise-Koszul algebras

    Institute of Scientific and Technical Information of China (English)

    Jia-feng; Lü

    2007-01-01

    [1]Priddy S.Koszul resolutions.Trans Amer Math Soc,152:39-60 (1970)[2]Beilinson A,Ginszburg V,Soergel W.Koszul duality patterns in representation theory.J Amer Math Soc,9:473-525 (1996)[3]Aquino R M,Green E L.On modules with linear presentations over Koszul algebras.Comm Algebra,33:19-36 (2005)[4]Green E L,Martinez-Villa R.Koszul and Yoneda algebras.Representation theory of algebras (Cocoyoc,1994).In:CMS Conference Proceedings,Vol 18.Providence,RI:American Mathematical Society,1996,247-297[5]Berger R.Koszulity for nonquadratic algebras.J Algebra,239:705-734 (2001)[6]Green E L,Marcos E N,Martinez-Villa R,et al.D-Koszul algebras.J Pure Appl Algebra,193:141-162(2004)[7]He J W,Lu D M.Higher Koszul Algebras and A-infinity Algebras.J Algebra,293:335-362 (2005)[8]Green E L,Marcos E N.δ-Koszul algebras.Comm Algebra,33(6):1753-1764 (2005)[9]Keller B.Introduction to A-infinity algebras and modules.Homology Homotopy Appl,3:1-35 (2001)[10]Green E L,Martinez-Villa R,Reiten I,et al.On modules with linear presentations.J Algebra,205(2):578-604 (1998)[11]Keller B.A-infinity algebras in representation theory.Contribution to the Proceedings of ICRA Ⅸ.Beijing:Peking University Press,2000[12]Lu D M,Palmieri J H,Wu Q S,et al.A∞-algebras for ring theorists.Algebra Colloq,11:91-128 (2004)[13]Weibel C A.An Introduction to homological algebra.Cambridge Studies in Avanced Mathematics,Vol 38.Cambridge:Cambridge University Press,1995

  10. Reasoning formalism in Boolean operator fuzzy logic

    Institute of Scientific and Technical Information of China (English)

    邓安生; 刘叙华

    1995-01-01

    Based on the newly introduced concepts of true-level and false-level, the formal structure of reasoning in Boolean operator fuzzy logic is presented. As a generalization of the theory of epistemic process in open logic, a formalism is also proposed to describe human reasoning with uncertain, inconsistent and insufficient knowledge, which can characterize the knowledge increment and revision, as well as the epistemic evolution. The formalism provides an explanation to the dynamic properties of human reasoning, i. e. continuous revision and combination of beliefs.

  11. On the robustness of random Boolean formulae

    Energy Technology Data Exchange (ETDEWEB)

    Mozeika, Alexander; Saad, David [Non-linearity and Complexity Research Group, Aston University, Birmingham B4 7ET (United Kingdom); Raymond, Jack, E-mail: a.s.mozeika@aston.ac.u, E-mail: d.saad@aston.ac.u [Department of Physics, Hong Kong University of Science and Technology, Clear Water Bay (Hong Kong)

    2010-06-01

    Random Boolean formulae, generated by a growth process of noisy logical gates are analyzed using the generating functional methodology of statistical physics. We study the type of functions generated for different input distributions, their robustness for a given level of gate error and its dependence on the formulae depth and complexity and the gates used. Bounds on their performance, derived in the information theory literature for specific gates, are straightforwardly retrieved, generalized and identified as the corresponding typical-case phase transitions. Results for error-rates, function-depth and sensitivity of the generated functions are obtained for various gate-type and noise models.

  12. Uniform Frechet algebras

    CERN Document Server

    Goldmann, H

    1990-01-01

    The first part of this monograph is an elementary introduction to the theory of Fréchet algebras. Important examples of Fréchet algebras, which are among those considered, are the algebra of all holomorphic functions on a (hemicompact) reduced complex space, and the algebra of all continuous functions on a suitable topological space.The problem of finding analytic structure in the spectrum of a Fréchet algebra is the subject of the second part of the book. In particular, the author pays attention to function algebraic characterizations of certain Stein algebras (= algebras of holomorphic functions on Stein spaces) within the class of Fréchet algebras.

  13. Algebraic theory of numbers

    CERN Document Server

    Samuel, Pierre

    2008-01-01

    Algebraic number theory introduces students not only to new algebraic notions but also to related concepts: groups, rings, fields, ideals, quotient rings and quotient fields, homomorphisms and isomorphisms, modules, and vector spaces. Author Pierre Samuel notes that students benefit from their studies of algebraic number theory by encountering many concepts fundamental to other branches of mathematics - algebraic geometry, in particular.This book assumes a knowledge of basic algebra but supplements its teachings with brief, clear explanations of integrality, algebraic extensions of fields, Gal

  14. Linear associative algebras

    CERN Document Server

    Abian, Alexander

    1973-01-01

    Linear Associative Algebras focuses on finite dimensional linear associative algebras and the Wedderburn structure theorems.The publication first elaborates on semigroups and groups, rings and fields, direct sum and tensor product of rings, and polynomial and matrix rings. The text then ponders on vector spaces, including finite dimensional vector spaces and matrix representation of vectors. The book takes a look at linear associative algebras, as well as the idempotent and nilpotent elements of an algebra, ideals of an algebra, total matrix algebras and the canonical forms of matrices, matrix

  15. Clifford Algebra with Mathematica

    CERN Document Server

    Aragon-Camarasa, G; Aragon, J L; Rodriguez-Andrade, M A

    2008-01-01

    The Clifford algebra of a n-dimensional Euclidean vector space provides a general language comprising vectors, complex numbers, quaternions, Grassman algebra, Pauli and Dirac matrices. In this work, a package for Clifford algebra calculations for the computer algebra program Mathematica is introduced through a presentation of the main ideas of Clifford algebras and illustrative examples. This package can be a useful computational tool since allows the manipulation of all these mathematical objects. It also includes the possibility of visualize elements of a Clifford algebra in the 3-dimensional space.

  16. Normed BCI-algebras

    Institute of Scientific and Technical Information of China (English)

    PENG Jia-yin

    2011-01-01

    The notions of norm and distance in BCI-algebras are introduced,and some basic properties in normed BCI-algebras are given.It is obtained that the isomorphic(homomorphic)image and inverse image of a normed BCI-algebra are still normed BCI-algebras.The relations of normaled properties between BCI-algebra and Cartesian product of BCIalgebras are investigated.The limit notion of sequence of points in normed BCI-algebras is introduced,and its related properties are investigated.

  17. Lukasiewicz-Moisil algebras

    CERN Document Server

    Boicescu, V; Georgescu, G; Rudeanu, S

    1991-01-01

    The Lukasiewicz-Moisil algebras were created by Moisil as an algebraic counterpart for the many-valued logics of Lukasiewicz. The theory of LM-algebras has developed to a considerable extent both as an algebraic theory of intrinsic interest and in view of its applications to logic and switching theory.This book gives an overview of the theory, comprising both classical results and recent contributions, including those of the authors. N-valued and &THgr;-valued algebras are presented, as well as &THgr;-algebras with negation.Mathematicians interested in lattice theory or symbolic logic, and computer scientists, will find in this monograph stimulating material for further research.

  18. ADAM: Analysis of Discrete Models of Biological Systems Using Computer Algebra

    CERN Document Server

    Hinkelmann, Franziska; Guang, Bonny; McNeill, Rustin; Blekherman, Grigoriy; Veliz-Cuba, Alan; Laubenbacher, Reinhard

    2010-01-01

    Motivation: Many biological systems are modeled qualitatively with discrete models, such as probabilistic Boolean networks, logical models, bounded Petri nets, and agent-based models. Simulation is a common practice for analyzing discrete models, but many systems are far too large to capture all the relevant dynamical features through simulation alone. Results: We convert discrete models into algebraic models and apply tools from computational algebra to analyze their dynamics. The key feature of biological systems that is exploited by our algorithms is their sparsity: while the number of nodes in a biological network may be quite large, each node is affected only by a small number of other nodes. In our experience with models arising in systems biology and random models, this structure leads to fast computations when using algebraic models, and thus efficient analysis. Availability: All algorithms and methods are available in our package Analysis of Dynamic Algebraic Models (ADAM), a user friendly web-interf...

  19. Some Notes on G-algebras%关于G-代数的一些注记

    Institute of Scientific and Technical Information of China (English)

    朱怡权; 唐续俞; 张秋瑾

    2011-01-01

    引进了基于一般剩余格的G-代数-G(RL)-代数的概念,并且分别给出了G-滤子和(全序)G(RL)-代数的一系列特征刻画,同时还证明了任何正则的G(RL)-代数必为Boolean代数,本文所得结果分别是已有结果的一般化.%In this paper, the concept of G(RL)-algebras based on general residuated lattices is introduced,and some characterizations of G-filters and (totally ordered) G(RL)-algebras are respectively established.Moreover, it is proved that any regular G(RL)-algebra is a Boolean algebra.These results are respectively a generalization of some early results presented in the references.

  20. Intervention in Context-Sensitive Probabilistic Boolean Networks Revisited

    Directory of Open Access Journals (Sweden)

    Babak Faryabi

    2009-01-01

    Full Text Available An approximate representation for the state space of a context-sensitive probabilistic Boolean network has previously been proposed and utilized to devise therapeutic intervention strategies. Whereas the full state of a context-sensitive probabilistic Boolean network is specified by an ordered pair composed of a network context and a gene-activity profile, this approximate representation collapses the state space onto the gene-activity profiles alone. This reduction yields an approximate transition probability matrix, absent of context, for the Markov chain associated with the context-sensitive probabilistic Boolean network. As with many approximation methods, a price must be paid for using a reduced model representation, namely, some loss of optimality relative to using the full state space. This paper examines the effects on intervention performance caused by the reduction with respect to various values of the model parameters. This task is performed using a new derivation for the transition probability matrix of the context-sensitive probabilistic Boolean network. This expression of transition probability distributions is in concert with the original definition of context-sensitive probabilistic Boolean network. The performance of optimal and approximate therapeutic strategies is compared for both synthetic networks and a real case study. It is observed that the approximate representation describes the dynamics of the context-sensitive probabilistic Boolean network through the instantaneously random probabilistic Boolean network with similar parameters.

  1. Controllability of asynchronous Boolean multiplex control networks

    Science.gov (United States)

    Luo, Chao; Wang, Xingyuan; Liu, Hong

    2014-09-01

    In this article, the controllability of asynchronous Boolean multiplex control networks (ABMCNs) is studied. First, the model of Boolean multiplex control networks under Harvey' asynchronous update is presented. By means of semi-tensor product approach, the logical dynamics is converted into linear representation, and a generalized formula of control-depending network transition matrices is achieved. Second, a necessary and sufficient condition is proposed to verify that only control-depending fixed points of ABMCNs can be controlled with probability one. Third, using two types of controls, the controllability of system is studied and formulae are given to show: (a) when an initial state is given, the reachable set at time s under a group of specified controls; (b) the reachable set at time s under arbitrary controls; (c) the specific probability values from a given initial state to destination states. Based on the above formulae, an algorithm to calculate overall reachable states from a specified initial state is presented. Moreover, we also discuss an approach to find the particular control sequence which steers the system between two states with maximum probability. Examples are shown to illustrate the feasibility of the proposed scheme.

  2. Controllability of asynchronous Boolean multiplex control networks.

    Science.gov (United States)

    Luo, Chao; Wang, Xingyuan; Liu, Hong

    2014-09-01

    In this article, the controllability of asynchronous Boolean multiplex control networks (ABMCNs) is studied. First, the model of Boolean multiplex control networks under Harvey' asynchronous update is presented. By means of semi-tensor product approach, the logical dynamics is converted into linear representation, and a generalized formula of control-depending network transition matrices is achieved. Second, a necessary and sufficient condition is proposed to verify that only control-depending fixed points of ABMCNs can be controlled with probability one. Third, using two types of controls, the controllability of system is studied and formulae are given to show: (a) when an initial state is given, the reachable set at time s under a group of specified controls; (b) the reachable set at time s under arbitrary controls; (c) the specific probability values from a given initial state to destination states. Based on the above formulae, an algorithm to calculate overall reachable states from a specified initial state is presented. Moreover, we also discuss an approach to find the particular control sequence which steers the system between two states with maximum probability. Examples are shown to illustrate the feasibility of the proposed scheme.

  3. Synchronization of coupled Boolean phase oscillators

    Science.gov (United States)

    Rosin, David P.; Rontani, Damien; Gauthier, Daniel J.

    2014-04-01

    We design, characterize, and couple Boolean phase oscillators that include state-dependent feedback delay. The state-dependent delay allows us to realize an adjustable coupling strength, even though only Boolean signals are exchanged. Specifically, increasing the coupling strength via the range of state-dependent delay leads to larger locking ranges in uni- and bidirectional coupling of oscillators in both experiment and numerical simulation with a piecewise switching model. In the unidirectional coupling scheme, we unveil asymmetric triangular-shaped locking regions (Arnold tongues) that appear at multiples of the natural frequency of the oscillators. This extends observations of a single locking region reported in previous studies. In the bidirectional coupling scheme, we map out a symmetric locking region in the parameter space of frequency detuning and coupling strength. Because of the large scalability of our setup, our observations constitute a first step towards realizing large-scale networks of coupled oscillators to address fundamental questions on the dynamical properties of networks in a new experimental setting.

  4. Hom-alternative algebras and Hom-Jordan algebras

    CERN Document Server

    Makhlouf, Abdenacer

    2009-01-01

    The purpose of this paper is to introduce Hom-alternative algebras and Hom-Jordan algebras. We discuss some of their properties and provide construction procedures using ordinary alternative algebras or Jordan algebras. Also, we show that a polarization of Hom-associative algebra leads to Hom-Jordan algebra.

  5. Cellularity of diagram algebras as twisted semigroup algebras

    CERN Document Server

    Wilcox, Stewart

    2010-01-01

    The Temperley-Lieb and Brauer algebras and their cyclotomic analogues, as well as the partition algebra, are all examples of twisted semigroup algebras. We prove a general theorem about the cellularity of twisted semigroup algebras of regular semigroups. This theorem, which generalises a recent result of East about semigroup algebras of inverse semigroups, allows us to easily reproduce the cellularity of these algebras.

  6. 基于布尔语义的Gentzen推导模型%Gentzen Deduction Model Based on Boolean Logic Semantics

    Institute of Scientific and Technical Information of China (English)

    陈博; 眭跃飞

    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ÎΔ

  7. Equivalence Checking of Combinational Circuits using Boolean Expression Diagrams

    DEFF Research Database (Denmark)

    Hulgaard, Henrik; Williams, Poul Frederick; Andersen, Henrik Reif

    1999-01-01

    The combinational logic-level equivalence problem is to determine whether two given combinational circuits implement the same Boolean function. This problem arises in a number of CAD applications, for example when checking the correctness of incremental design changes (performed either manually...... or by a design automation tool).This paper introduces a data structure called Boolean Expression Diagrams (BEDs) and two algorithms for transforming a BED into a Reduced Ordered Binary Decision Diagram (OBDD). BEDs are capable of representing any Boolean circuit in linear space and can exploit structural...

  8. Lie Algebra of Noncommutative Inhomogeneous Hopf Algebra

    CERN Document Server

    Lagraa, M

    1997-01-01

    We construct the vector space dual to the space of right-invariant differential forms construct from a first order differential calculus on inhomogeneous quantum group. We show that this vector space is equipped with a structure of a Hopf algebra which closes on a noncommutative Lie algebra satisfying a Jacobi identity.

  9. Categories and Commutative Algebra

    CERN Document Server

    Salmon, P

    2011-01-01

    L. Badescu: Sur certaines singularites des varietes algebriques.- D.A. Buchsbaum: Homological and commutative algebra.- S. Greco: Anelli Henseliani.- C. Lair: Morphismes et structures algebriques.- B.A. Mitchell: Introduction to category theory and homological algebra.- R. Rivet: Anneaux de series formelles et anneaux henseliens.- P. Salmon: Applicazioni della K-teoria all'algebra commutativa.- M. Tierney: Axiomatic sheaf theory: some constructions and applications.- C.B. Winters: An elementary lecture on algebraic spaces.

  10. Algebraic statistics computational commutative algebra in statistics

    CERN Document Server

    Pistone, Giovanni; Wynn, Henry P

    2000-01-01

    Written by pioneers in this exciting new field, Algebraic Statistics introduces the application of polynomial algebra to experimental design, discrete probability, and statistics. It begins with an introduction to Gröbner bases and a thorough description of their applications to experimental design. A special chapter covers the binary case with new application to coherent systems in reliability and two level factorial designs. The work paves the way, in the last two chapters, for the application of computer algebra to discrete probability and statistical modelling through the important concept of an algebraic statistical model.As the first book on the subject, Algebraic Statistics presents many opportunities for spin-off research and applications and should become a landmark work welcomed by both the statistical community and its relatives in mathematics and computer science.

  11. Connecting Arithmetic to Algebra

    Science.gov (United States)

    Darley, Joy W.; Leapard, Barbara B.

    2010-01-01

    Algebraic thinking is a top priority in mathematics classrooms today. Because elementary school teachers lay the groundwork to develop students' capacity to think algebraically, it is crucial for teachers to have a conceptual understanding of the connections between arithmetic and algebra and be confident in communicating these connections. Many…

  12. Algebra of timed frames

    NARCIS (Netherlands)

    Bergstra, J.A.; Fokkink, W.J.; Middelburg, C.A.

    2008-01-01

    Timed frames are introduced as objects that can form a basis of a model theory for discrete time process algebra. An algebraic setting for timed frames is proposed and results concerning its connection with discrete time process algebra are given. The presented theory of timed frames captures the ba

  13. Deficiently Extremal Gorenstein Algebras

    Indian Academy of Sciences (India)

    Pavinder Singh

    2011-08-01

    The aim of this article is to study the homological properties of deficiently extremal Gorenstein algebras. We prove that if / is an odd deficiently extremal Gorenstein algebra with pure minimal free resolution, then the codimension of / must be odd. As an application, the structure of pure minimal free resolution of a nearly extremal Gorenstein algebra is obtained.

  14. REAL PIECEWISE ALGEBRAIC VARIETY

    Institute of Scientific and Technical Information of China (English)

    Ren-hong Wang; Yi-sheng Lai

    2003-01-01

    We give definitions of real piecewise algebraic variety and its dimension. By using the techniques of real radical ideal, P-radical ideal, affine Hilbert polynomial, Bernstein-net form of polynomials on simplex, and decomposition of semi-algebraic set, etc., we deal with the dimension of the real piecewise algebraic variety and real Nullstellensatz in Cμ spline ring.

  15. Bases of Schur algebras associated to cellularly stratified diagram algebras

    CERN Document Server

    Bowman, C

    2011-01-01

    We examine homomorphisms between induced modules for a certain class of cellularly stratified diagram algebras, including the BMW algebra, Temperley-Lieb algebra, Brauer algebra, and (quantum) walled Brauer algebra. We define the `permutation' modules for these algebras, these are one-sided ideals which allow us to study the diagrammatic Schur algebras of Hartmann, Henke, Koenig and Paget. We construct bases of these Schur algebras in terms of modified tableaux. On the way we prove that the (quantum) walled Brauer algebra and the Temperley-Lieb algebra are both cellularly stratified and therefore have well-defined Specht filtrations.

  16. Boolean Burritos: How the Faculty Ate Up Keyword Searching.

    Science.gov (United States)

    York, Sherry

    1999-01-01

    Describes an activity that librarians can use to acquaint teachers with keyword searching and Boolean operators to more successfully use the library's online catalog. Uses food ingredients to represent various possible combinations. (LRW)

  17. A Full Bayesian Approach for Boolean Genetic Network Inference

    Science.gov (United States)

    Han, Shengtong; Wong, Raymond K. W.; Lee, Thomas C. M.; Shen, Linghao; Li, Shuo-Yen R.; Fan, Xiaodan

    2014-01-01

    Boolean networks are a simple but efficient model for describing gene regulatory systems. A number of algorithms have been proposed to infer Boolean networks. However, these methods do not take full consideration of the effects of noise and model uncertainty. In this paper, we propose a full Bayesian approach to infer Boolean genetic networks. Markov chain Monte Carlo algorithms are used to obtain the posterior samples of both the network structure and the related parameters. In addition to regular link addition and removal moves, which can guarantee the irreducibility of the Markov chain for traversing the whole network space, carefully constructed mixture proposals are used to improve the Markov chain Monte Carlo convergence. Both simulations and a real application on cell-cycle data show that our method is more powerful than existing methods for the inference of both the topology and logic relations of the Boolean network from observed data. PMID:25551820

  18. QBF-Based Boolean Function Bi-Decomposition

    CERN Document Server

    Chen, Huan; Marques-Silva, Joao

    2011-01-01

    Boolean function bi-decomposition is ubiquitous in logic synthesis. It entails the decomposition of a Boolean function using two-input simple logic gates. Existing solutions for bi-decomposition are often based on BDDs and, more recently, on Boolean Satisfiability. In addition, the partition of the input set of variables is either assumed, or heuristic solutions are considered for finding good partitions. In contrast to earlier work, this paper proposes the use of Quantified Boolean Formulas (QBF) for computing bi- decompositions. These bi-decompositions are optimal in terms of the achieved disjointness and balancedness of the input set of variables. Experimental results, obtained on representative benchmarks, demonstrate clear improvements in the quality of computed decompositions, but also the practical feasibility of QBF-based bi-decomposition.

  19. A fast quantum algorithm for the affine Boolean function identification

    Science.gov (United States)

    Younes, Ahmed

    2015-02-01

    Bernstein-Vazirani algorithm (the one-query algorithm) can identify a completely specified linear Boolean function using a single query to the oracle with certainty. The first aim of the paper is to show that if the provided Boolean function is affine, then one more query to the oracle (the two-query algorithm) is required to identify the affinity of the function with certainty. The second aim of the paper is to show that if the provided Boolean function is incompletely defined, then the one-query and the two-query algorithms can be used as bounded-error quantum polynomial algorithms to identify certain classes of incompletely defined linear and affine Boolean functions respectively with probability of success at least 2/3.

  20. A full bayesian approach for boolean genetic network inference.

    Directory of Open Access Journals (Sweden)

    Shengtong Han

    Full Text Available Boolean networks are a simple but efficient model for describing gene regulatory systems. A number of algorithms have been proposed to infer Boolean networks. However, these methods do not take full consideration of the effects of noise and model uncertainty. In this paper, we propose a full Bayesian approach to infer Boolean genetic networks. Markov chain Monte Carlo algorithms are used to obtain the posterior samples of both the network structure and the related parameters. In addition to regular link addition and removal moves, which can guarantee the irreducibility of the Markov chain for traversing the whole network space, carefully constructed mixture proposals are used to improve the Markov chain Monte Carlo convergence. Both simulations and a real application on cell-cycle data show that our method is more powerful than existing methods for the inference of both the topology and logic relations of the Boolean network from observed data.

  1. A transition calculus for Boolean functions. [logic circuit analysis

    Science.gov (United States)

    Tucker, J. H.; Bennett, A. W.

    1974-01-01

    A transition calculus is presented for analyzing the effect of input changes on the output of logic circuits. The method is closely related to the Boolean difference, but it is more powerful. Both differentiation and integration are considered.

  2. On Various Nonlinearity Measures for Boolean Functions.

    Science.gov (United States)

    Boyar, Joan; Find, Magnus Gausdal; Peralta, René

    2016-07-01

    A necessary condition for the security of cryptographic functions is to be "sufficiently distant" from linear, and cryptographers have proposed several measures for this distance. In this paper, we show that six common measures, nonlinearity, algebraic degree, annihilator immunity, algebraic thickness, normality, and multiplicative complexity, are incomparable in the sense that for each pair of measures, μ1, μ2, there exist functions f1, f2 with f1 being more nonlinear than f2 according to μ1, but less nonlinear according to μ2. We also present new connections between two of these measures. Additionally, we give a lower bound on the multiplicative complexity of collision-free functions.

  3. Representing Boolean Functions by Decision Trees

    KAUST Repository

    Chikalov, Igor

    2011-01-01

    A Boolean or discrete function can be represented by a decision tree. A compact form of decision tree named binary decision diagram or branching program is widely known in logic design [2, 40]. This representation is equivalent to other forms, and in some cases it is more compact than values table or even the formula [44]. Representing a function in the form of decision tree allows applying graph algorithms for various transformations [10]. Decision trees and branching programs are used for effective hardware [15] and software [5] implementation of functions. For the implementation to be effective, the function representation should have minimal time and space complexity. The average depth of decision tree characterizes the expected computing time, and the number of nodes in branching program characterizes the number of functional elements required for implementation. Often these two criteria are incompatible, i.e. there is no solution that is optimal on both time and space complexity. © Springer-Verlag Berlin Heidelberg 2011.

  4. Multipath Detection Using Boolean Satisfiability Techniques

    Directory of Open Access Journals (Sweden)

    Fadi A. Aloul

    2011-01-01

    Full Text Available A new technique for multipath detection in wideband mobile radio systems is presented. The proposed scheme is based on an intelligent search algorithm using Boolean Satisfiability (SAT techniques to search through the uncertainty region of the multipath delays. The SAT-based scheme utilizes the known structure of the transmitted wideband signal, for example, pseudo-random (PN code, to effectively search through the entire space by eliminating subspaces that do not contain a possible solution. The paper presents a framework for modeling the multipath detection problem as a SAT application. It also provides simulation results that demonstrate the effectiveness of the proposed scheme in detecting the multipath components in frequency-selective Rayleigh fading channels.

  5. Boolean networks with robust and reliable trajectories

    Energy Technology Data Exchange (ETDEWEB)

    Schmal, Christoph; Peixoto, Tiago P; Drossel, Barbara, E-mail: schmal@physik.uni-bielefeld.d, E-mail: tiago@fkp.tu-darmstadt.d, E-mail: drossel@fkp.tu-darmstadt.d [Institut fuer Festkoerperphysik, TU Darmstadt, Hochschulstrasse 6, 64289 Darmstadt (Germany)

    2010-11-15

    We construct and investigate Boolean networks that follow a given reliable trajectory in state space, which is insensitive to fluctuations in the updating schedule and which is also robust against noise. Robustness is quantified as the probability that the dynamics return to the reliable trajectory after a perturbation of the state of a single node. In order to achieve high robustness, we navigate through the space of possible update functions by using an evolutionary algorithm. We constrain the networks to those having the minimum number of connections required to obtain the reliable trajectory. Surprisingly, we find that robustness always reaches values close to 100% during the evolutionary optimization process. The set of update functions can be evolved such that it differs only slightly from that of networks that were not optimized with respect to robustness. The state space of the optimized networks is dominated by the basin of attraction of the reliable trajectory.

  6. Message passing for quantified Boolean formulas

    CERN Document Server

    Zhang, Pan; Zdeborová, Lenka; Zecchina, Riccardo

    2012-01-01

    We introduce two types of message passing algorithms for quantified Boolean formulas (QBF). The first type is a message passing based heuristics that can prove unsatisfiability of the QBF by assigning the universal variables in such a way that the remaining formula is unsatisfiable. In the second type, we use message passing to guide branching heuristics of a Davis-Putnam Logemann-Loveland (DPLL) complete solver. Numerical experiments show that on random QBFs our branching heuristics gives robust exponential efficiency gain with respect to the state-of-art solvers. We also manage to solve some previously unsolved benchmarks from the QBFLIB library. Apart from this our study sheds light on using message passing in small systems and as subroutines in complete solvers.

  7. Reduction Mappings between Probabilistic Boolean Networks

    Directory of Open Access Journals (Sweden)

    Ivan Ivanov

    2004-01-01

    Full Text Available Probabilistic Boolean networks (PBNs comprise a model describing a directed graph with rule-based dependences between its nodes. The rules are selected, based on a given probability distribution which provides a flexibility when dealing with the uncertainty which is typical for genetic regulatory networks. Given the computational complexity of the model, the characterization of mappings reducing the size of a given PBN becomes a critical issue. Mappings between PBNs are important also from a theoretical point of view. They provide means for developing a better understanding about the dynamics of PBNs. This paper considers two kinds of mappings reduction and projection and their effect on the original probability structure of a given PBN.

  8. Robust Boolean Operation for Sculptured Models

    Institute of Scientific and Technical Information of China (English)

    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.

  9. A Boolean Approach to Airline Business Model Innovation

    DEFF Research Database (Denmark)

    Hvass, Kristian Anders

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

  10. optPBN: An Optimisation Toolbox for Probabilistic Boolean Networks

    Science.gov (United States)

    Trairatphisan, Panuwat; Mizera, Andrzej; Pang, Jun; Tantar, Alexandru Adrian; Sauter, Thomas

    2014-01-01

    Background There exist several computational tools which allow for the optimisation and inference of biological networks using a Boolean formalism. Nevertheless, the results from such tools yield only limited quantitative insights into the complexity of biological systems because of the inherited qualitative nature of Boolean networks. Results We introduce optPBN, a Matlab-based toolbox for the optimisation of probabilistic Boolean networks (PBN) which operates under the framework of the BN/PBN toolbox. optPBN offers an easy generation of probabilistic Boolean networks from rule-based Boolean model specification and it allows for flexible measurement data integration from multiple experiments. Subsequently, optPBN generates integrated optimisation problems which can be solved by various optimisers. In term of functionalities, optPBN allows for the construction of a probabilistic Boolean network from a given set of potential constitutive Boolean networks by optimising the selection probabilities for these networks so that the resulting PBN fits experimental data. Furthermore, the optPBN pipeline can also be operated on large-scale computational platforms to solve complex optimisation problems. Apart from exemplary case studies which we correctly inferred the original network, we also successfully applied optPBN to study a large-scale Boolean model of apoptosis where it allows identifying the inverse correlation between UVB irradiation, NFκB and Caspase 3 activations, and apoptosis in primary hepatocytes quantitatively. Also, the results from optPBN help elucidating the relevancy of crosstalk interactions in the apoptotic network. Summary The optPBN toolbox provides a simple yet comprehensive pipeline for integrated optimisation problem generation in the PBN formalism that can readily be solved by various optimisers on local or grid-based computational platforms. optPBN can be further applied to various biological studies such as the inference of gene regulatory

  11. Computer algebra and operators

    Science.gov (United States)

    Fateman, Richard; Grossman, Robert

    1989-01-01

    The symbolic computation of operator expansions is discussed. Some of the capabilities that prove useful when performing computer algebra computations involving operators are considered. These capabilities may be broadly divided into three areas: the algebraic manipulation of expressions from the algebra generated by operators; the algebraic manipulation of the actions of the operators upon other mathematical objects; and the development of appropriate normal forms and simplification algorithms for operators and their actions. Brief descriptions are given of the computer algebra computations that arise when working with various operators and their actions.

  12. Split Malcev Algebras

    Indian Academy of Sciences (India)

    Antonio J Calderón Martín; Manuel Forero Piulestán; José M Sánchez Delgado

    2012-05-01

    We study the structure of split Malcev algebras of arbitrary dimension over an algebraically closed field of characteristic zero. We show that any such algebras is of the form $M=\\mathcal{U}+\\sum_jI_j$ with $\\mathcal{U}$ a subspace of the abelian Malcev subalgebra and any $I_j$ a well described ideal of satisfying $[I_j, I_k]=0$ if ≠ . Under certain conditions, the simplicity of is characterized and it is shown that is the direct sum of a semisimple split Lie algebra and a direct sum of simple non-Lie Malcev algebras.

  13. Algorithms in Algebraic Geometry

    CERN Document Server

    Dickenstein, Alicia; Sommese, Andrew J

    2008-01-01

    In the last decade, there has been a burgeoning of activity in the design and implementation of algorithms for algebraic geometric computation. Some of these algorithms were originally designed for abstract algebraic geometry, but now are of interest for use in applications and some of these algorithms were originally designed for applications, but now are of interest for use in abstract algebraic geometry. The workshop on Algorithms in Algebraic Geometry that was held in the framework of the IMA Annual Program Year in Applications of Algebraic Geometry by the Institute for Mathematics and Its

  14. Boolean network model predicts knockout mutant phenotypes of fission yeast.

    Directory of Open Access Journals (Sweden)

    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.

  15. Boolean Network Model Predicts Knockout Mutant Phenotypes of Fission Yeast

    Science.gov (United States)

    Davidich, Maria I.; Bornholdt, Stefan

    2013-01-01

    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. PMID:24069138

  16. Lectures on algebraic statistics

    CERN Document Server

    Drton, Mathias; Sullivant, Seth

    2009-01-01

    How does an algebraic geometer studying secant varieties further the understanding of hypothesis tests in statistics? Why would a statistician working on factor analysis raise open problems about determinantal varieties? Connections of this type are at the heart of the new field of "algebraic statistics". In this field, mathematicians and statisticians come together to solve statistical inference problems using concepts from algebraic geometry as well as related computational and combinatorial techniques. The goal of these lectures is to introduce newcomers from the different camps to algebraic statistics. The introduction will be centered around the following three observations: many important statistical models correspond to algebraic or semi-algebraic sets of parameters; the geometry of these parameter spaces determines the behaviour of widely used statistical inference procedures; computational algebraic geometry can be used to study parameter spaces and other features of statistical models.

  17. Linear algebra meets Lie algebra: the Kostant-Wallach theory

    OpenAIRE

    Shomron, Noam; Parlett, Beresford N.

    2008-01-01

    In two languages, Linear Algebra and Lie Algebra, we describe the results of Kostant and Wallach on the fibre of matrices with prescribed eigenvalues of all leading principal submatrices. In addition, we present a brief introduction to basic notions in Algebraic Geometry, Integrable Systems, and Lie Algebra aimed at specialists in Linear Algebra.

  18. The Hall Algebra of Cyclic Serial Algebra

    Institute of Scientific and Technical Information of China (English)

    郭晋云

    1994-01-01

    In this paper, orders <1 and <2 on ((Z)+)nm are introduced and also regarded as orders on the isomorphism classes of finite modules of finite .cyclic algebra R with n simple modules and all the indecomposable projective modules have length m through a one-to-one correspondence between ((Z)+)nm and the isomorphism classes of finite R modules. Using this we prove that the Hall algebra of a cyclic serial algebra is identified with its Loewy subalgebra, and its rational extension has a basis of BPW type, and is a (((Z)+)nm, <2) filtered ring with the associated graded ring as an iterated skew polynomial ring. These results are also generalized to the Hall algebra of a tube over a finite field.

  19. Evolution algebras and their applications

    CERN Document Server

    Tian, Jianjun Paul

    2008-01-01

    Behind genetics and Markov chains, there is an intrinsic algebraic structure. It is defined as a type of new algebra: as evolution algebra. This concept lies between algebras and dynamical systems. Algebraically, evolution algebras are non-associative Banach algebras; dynamically, they represent discrete dynamical systems. Evolution algebras have many connections with other mathematical fields including graph theory, group theory, stochastic processes, dynamical systems, knot theory, 3-manifolds, and the study of the Ihara-Selberg zeta function. In this volume the foundation of evolution algebra theory and applications in non-Mendelian genetics and Markov chains is developed, with pointers to some further research topics.

  20. Structured adaptive grid generation using algebraic methods

    Science.gov (United States)

    Yang, Jiann-Cherng; Soni, Bharat K.; Roger, R. P.; Chan, Stephen C.

    1993-01-01

    of points to the grid redistribution scheme. The evaluation of the weighting mesh is accomplished by utilizing the weight function representing the solution variation and the equidistribution law. The selection of the weight function plays a key role in grid adaptation. A new weight function utilizing a properly weighted boolean sum of various flowfield characteristics is defined. The redistribution scheme is developed utilizing Non-Uniform Rational B-Splines (NURBS) representation. The application of NURBS representation results in a well distributed smooth grid by maintaining the fidelity of the geometry associated with boundary curves. Several algebraic methods are applied to smooth and/or nearly orthogonalize the grid lines. An elliptic solver is utilized to smooth the grid lines if there are grid crossings. Various computational examples of practical interest are presented to demonstrate the success of these methods.

  1. Finite-dimensional (*)-serial algebras

    Institute of Scientific and Technical Information of China (English)

    2010-01-01

    Let A be a finite-dimensional associative algebra with identity over a field k. In this paper we introduce the concept of (*)-serial algebras which is a generalization of serial algebras. We investigate the properties of (*)-serial algebras, and we obtain suficient and necessary conditions for an associative algebra to be (*)-serial.

  2. On hyper BCC-algebras

    Directory of Open Access Journals (Sweden)

    R. A. Borzooei

    2006-01-01

    Full Text Available We study hyper BCC-algebras which are a common generalization of BCC-algebras and hyper BCK-algebras. In particular, we investigate different types of hyper BCC-ideals and describe the relationship among them. Next, we calculate all nonisomorphic 22 hyper BCC-algebras of order 3 of which only three are not hyper BCK-algebras.

  3. On hyper BCC-algebras

    OpenAIRE

    Borzooei, R. A.; Dudek, W. A.; Koohestani, N.

    2006-01-01

    We study hyper BCC-algebras which are a common generalization of BCC-algebras and hyper BCK-algebras. In particular, we investigate different types of hyper BCC-ideals and describe the relationship among them. Next, we calculate all nonisomorphic 22 hyper BCC-algebras of order 3 of which only three are not hyper BCK-algebras.

  4. On the Toroidal Leibniz Algebras

    Institute of Scientific and Technical Information of China (English)

    Dong LIU; Lei LIN

    2008-01-01

    Toroidal Leibniz algebras are the universal central extensions of the iterated loop algebras gOC[t±11 ,...,t±v1] in the category of Leibniz algebras. In this paper, some properties and representations of toroidal Leibniz algebras are studied. Some general theories of central extensions of Leibniz algebras are also obtained.

  5. Lie algebras and applications

    CERN Document Server

    Iachello, Francesco

    2015-01-01

    This course-based primer provides an introduction to Lie algebras and some of their applications to the spectroscopy of molecules, atoms, nuclei and hadrons. In the first part, it concisely presents the basic concepts of Lie algebras, their representations and their invariants. The second part includes a description of how Lie algebras are used in practice in the treatment of bosonic and fermionic systems. Physical applications considered include rotations and vibrations of molecules (vibron model), collective modes in nuclei (interacting boson model), the atomic shell model, the nuclear shell model, and the quark model of hadrons. One of the key concepts in the application of Lie algebraic methods in physics, that of spectrum generating algebras and their associated dynamic symmetries, is also discussed. The book highlights a number of examples that help to illustrate the abstract algebraic definitions and includes a summary of many formulas of practical interest, such as the eigenvalues of Casimir operators...

  6. Developable algebraic surfaces

    Institute of Scientific and Technical Information of China (English)

    CHEN Dongren; WANG Guojin

    2004-01-01

    An algebraic surface can be defined by an implicit polynomial equation F(x,y,z)=0. In this paper, general characterizations of developable algebraic surfaces of arbitrary degree are presented. Using the shift operators of the subscripts of Bézier ordinates, the uniform apparent discriminants of developable algebraic surfaces to their Bézier ordinates are given directly. To degree 2 algebraic surfaces, which are widely used in computer aided geometric design and graphics, all possible developable surface types are obtained. For more conveniently applying algebraic surfaces of high degree to computer aided geometric design, the notion of ε-quasi-developable surfaces is introduced, and an example of using a quasi-developable algebraic surface of degree 3 to interpolate three curves of degree 2 is given.

  7. Order-to-chaos transition in the hardness of random Boolean satisfiability problems

    Science.gov (United States)

    Varga, Melinda; Sumi, Róbert; Toroczkai, Zoltán; Ercsey-Ravasz, Mária

    2016-05-01

    Transient chaos is a ubiquitous phenomenon characterizing the dynamics of phase-space trajectories evolving towards a steady-state attractor in physical systems as diverse as fluids, chemical reactions, and condensed matter systems. Here we show that transient chaos also appears in the dynamics of certain efficient algorithms searching for solutions of constraint satisfaction problems that include scheduling, circuit design, routing, database problems, and even Sudoku. In particular, we present a study of the emergence of hardness in Boolean satisfiability (k -SAT), a canonical class of constraint satisfaction problems, by using an analog deterministic algorithm based on a system of ordinary differential equations. Problem hardness is defined through the escape rate κ , an invariant measure of transient chaos of the dynamical system corresponding to the analog algorithm, and it expresses the rate at which the trajectory approaches a solution. We show that for a given density of constraints and fixed number of Boolean variables N , the hardness of formulas in random k -SAT ensembles has a wide variation, approximable by a lognormal distribution. We also show that when increasing the density of constraints α , hardness appears through a second-order phase transition at αχ in the random 3-SAT ensemble where dynamical trajectories become transiently chaotic. A similar behavior is found in 4-SAT as well, however, such a transition does not occur for 2-SAT. This behavior also implies a novel type of transient chaos in which the escape rate has an exponential-algebraic dependence on the critical parameter κ ˜NB |α - αχ|1-γ with 0 <γ <1 . We demonstrate that the transition is generated by the appearance of metastable basins in the solution space as the density of constraints α is increased.

  8. Algebra Automorphisms of Quantized Enveloping Algebras Uq(■)

    Institute of Scientific and Technical Information of China (English)

    查建国

    1994-01-01

    The algebra automorphisms of the quantized enveloping algebra Uq(g) are discussed, where q is generic. To some extent, all quantum deformations of automorphisms of the simple Lie algebra g have been determined.

  9. Cayley-Dickson and Clifford Algebras as Twisted Group Algebras

    CERN Document Server

    Bales, John W

    2011-01-01

    The effect of some properties of twisted groups on the associated algebras, particularly Cayley-Dickson and Clifford algebras. It is conjectured that the Hilbert space of square-summable sequences is a Cayley-Dickson algebra.

  10. Symmetric Extended Ockham Algebras

    Institute of Scientific and Technical Information of China (English)

    T.S. Blyth; Jie Fang

    2003-01-01

    The variety eO of extended Ockham algebras consists of those algealgebra with an additional endomorphism k such that the unary operations f and k commute. Here, we consider the cO-algebras which have a property of symmetry. We show that there are thirty two non-isomorphic subdirectly irreducible symmetric extended MS-algebras and give a complete description of them.2000 Mathematics Subject Classification: 06D15, 06D30

  11. Lax operator algebras

    OpenAIRE

    Krichever, Igor M.; Sheinman, Oleg K.

    2007-01-01

    In this paper we develop a general concept of Lax operators on algebraic curves introduced in [1]. We observe that the space of Lax operators is closed with respect to their usual multiplication as matrix-valued functions. We construct the orthogonal and symplectic analogs of Lax operators, prove that they constitute almost graded Lie algebras and construct local central extensions of those Lie algebras.

  12. Prediction of Algebraic Instabilities

    Science.gov (United States)

    Zaretzky, Paula; King, Kristina; Hill, Nicole; Keithley, Kimberlee; Barlow, Nathaniel; Weinstein, Steven; Cromer, Michael

    2016-11-01

    A widely unexplored type of hydrodynamic instability is examined - large-time algebraic growth. Such growth occurs on the threshold of (exponentially) neutral stability. A new methodology is provided for predicting the algebraic growth rate of an initial disturbance, when applied to the governing differential equation (or dispersion relation) describing wave propagation in dispersive media. Several types of algebraic instabilities are explored in the context of both linear and nonlinear waves.

  13. Cohomology of Effect Algebras

    Directory of Open Access Journals (Sweden)

    Frank Roumen

    2017-01-01

    Full Text Available We will define two ways to assign cohomology groups to effect algebras, which occur in the algebraic study of quantum logic. The first way is based on Connes' cyclic cohomology. The resulting cohomology groups are related to the state space of the effect algebra, and can be computed using variations on the Kunneth and Mayer-Vietoris sequences. The second way involves a chain complex of ordered abelian groups, and gives rise to a cohomological characterization of state extensions on effect algebras. This has applications to no-go theorems in quantum foundations, such as Bell's theorem.

  14. Algebraic extensions of fields

    CERN Document Server

    McCarthy, Paul J

    1991-01-01

    ""...clear, unsophisticated and direct..."" - MathThis textbook is intended to prepare graduate students for the further study of fields, especially algebraic number theory and class field theory. It presumes some familiarity with topology and a solid background in abstract algebra. Chapter 1 contains the basic results concerning algebraic extensions. In addition to separable and inseparable extensions and normal extensions, there are sections on finite fields, algebraically closed fields, primitive elements, and norms and traces. Chapter 2 is devoted to Galois theory. Besides the fundamenta

  15. On coalgebras over algebras

    CERN Document Server

    Balan, Adriana

    2010-01-01

    We extend Barr's well-known characterization of the final coalgebra of a $Set$-endofunctor as the completion of its initial algebra to the Eilenberg-Moore category of algebras for a $Set$-monad $\\mathbf{M}$ for functors arising as liftings. As an application we introduce the notion of commuting pair of endofunctors with respect to the monad $\\mathbf{M}$ and show that under reasonable assumptions, the final coalgebra of one of the endofunctors involved can be obtained as the free algebra generated by the initial algebra of the other endofunctor.

  16. Lectures in general algebra

    CERN Document Server

    Kurosh, A G; Stark, M; Ulam, S

    1965-01-01

    Lectures in General Algebra is a translation from the Russian and is based on lectures on specialized courses in general algebra at Moscow University. The book starts with the basics of algebra. The text briefly describes the theory of sets, binary relations, equivalence relations, partial ordering, minimum condition, and theorems equivalent to the axiom of choice. The text gives the definition of binary algebraic operation and the concepts of groups, groupoids, and semigroups. The book examines the parallelism between the theory of groups and the theory of rings; such examinations show the

  17. Fundamentals of Hopf algebras

    CERN Document Server

    Underwood, Robert G

    2015-01-01

    This text aims to provide graduate students with a self-contained introduction to topics that are at the forefront of modern algebra, namely, coalgebras, bialgebras, and Hopf algebras.  The last chapter (Chapter 4) discusses several applications of Hopf algebras, some of which are further developed in the author’s 2011 publication, An Introduction to Hopf Algebras.  The book may be used as the main text or as a supplementary text for a graduate algebra course.  Prerequisites for this text include standard material on groups, rings, modules, algebraic extension fields, finite fields, and linearly recursive sequences. The book consists of four chapters. Chapter 1 introduces algebras and coalgebras over a field K; Chapter 2 treats bialgebras; Chapter 3 discusses Hopf algebras and Chapter 4 consists of three applications of Hopf algebras. Each chapter begins with a short overview and ends with a collection of exercises which are designed to review and reinforce the material. Exercises range from straightforw...

  18. Relations Between BZMVdM-Algebra and Other Algebras

    Institute of Scientific and Technical Information of China (English)

    高淑萍; 邓方安; 刘三阳

    2003-01-01

    Some properties of BZMVdM-algebra are proved, and a new operator is introduced. It is shown that the substructure of BZMVdM-algebra can produce a quasi-lattice implication algebra. The relations between BZMVdM-algebra and other algebras are discussed in detail. A pseudo-distance function is defined in linear BZMVdM-algebra, and its properties are derived.

  19. Differential Hopf algebra structures on the universal enveloping algebra ofa Lie algebra

    NARCIS (Netherlands)

    Hijligenberg, N.W. van den; Martini, R.

    1995-01-01

    We discuss a method to construct a De Rham complex (differential algebra) of Poincar'e-Birkhoff-Witt-type on the universal enveloping algebra of a Lie algebra $g$. We determine the cases in which this gives rise to a differential Hopf algebra that naturally extends the Hopf algebra structure of $U(g

  20. Identifying a Probabilistic Boolean Threshold Network From Samples.

    Science.gov (United States)

    Melkman, Avraham A; Cheng, Xiaoqing; Ching, Wai-Ki; Akutsu, Tatsuya

    2017-01-25

    This paper studies the problem of exactly identifying the structure of a probabilistic Boolean network (PBN) from a given set of samples, where PBNs are probabilistic extensions of Boolean networks. Cheng et al. studied the problem while focusing on PBNs consisting of pairs of AND/OR functions. This paper considers PBNs consisting of Boolean threshold functions while focusing on those threshold functions that have unit coefficients. The treatment of Boolean threshold functions, and triplets and n-tuplets of such functions, necessitates a deepening of the theoretical analyses. It is shown that wide classes of PBNs with such threshold functions can be exactly identified from samples under reasonable constraints, which include: 1) PBNs in which any number of threshold functions can be assigned provided that all have the same number of input variables and 2) PBNs consisting of pairs of threshold functions with different numbers of input variables. It is also shown that the problem of deciding the equivalence of two Boolean threshold functions is solvable in pseudopolynomial time but remains co-NP complete.

  1. Tubular algebras and affine Kac-Moody algebras

    Institute of Scientific and Technical Information of China (English)

    2007-01-01

    The purpose of this paper is to construct quotient algebras L(A)1C/I(A) of complex degenerate composition Lie algebras L(A)1C by some ideals, where L(A)1C is defined via Hall algebras of tubular algebras A, and to prove that the quotient algebras L(A)1C/I(A) are isomorphic to the corresponding affine Kac-Moody algebras. Moreover, it is shown that the Lie algebra Lre(A)1C generated by A-modules with a real root coincides with the degenerate composition Lie algebra L(A)1C generated by simple A-modules.

  2. Tubular algebras and affine Kac-Moody algebras

    Institute of Scientific and Technical Information of China (English)

    Zheng-xin CHEN; Ya-nan LIN

    2007-01-01

    The purpose of this paper is to construct quotient algebras L(A)C1/I(A) of complex degenerate composition Lie algebras L(A)C1 by some ideals, where L(A)C1 is defined via Hall algebras of tubular algebras A, and to prove that the quotient algebras L(A)C1/I(A) are isomorphic to the corresponding affine Kac-Moody algebras. Moreover, it is shown that the Lie algebra Lre(A)C1 generated by A-modules with a real root coincides with the degenerate composition Lie algebra L(A)C1 generated by simple A-modules.

  3. Boolean Logic: An Aid for Searching Computer Databases in Special Education and Rehabilitation.

    Science.gov (United States)

    Summers, Edward G.

    1989-01-01

    The article discusses using Boolean logic as a tool for searching computerized information retrieval systems in special education and rehabilitation technology. It includes discussion of the Boolean search operators AND, OR, and NOT; Venn diagrams; and disambiguating parentheses. Six suggestions are offered for development of good Boolean logic…

  4. Fields and Forms on -Algebras

    Indian Academy of Sciences (India)

    Cătălin Ciupală

    2005-02-01

    In this paper we introduce non-commutative fields and forms on a new kind of non-commutative algebras: -algebras. We also define the Frölicher–Nijenhuis bracket in the non-commutative geometry on -algebras.

  5. Efficient Analog Circuits for Boolean Satisfiability

    CERN Document Server

    Yin, Xunzhao; 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 analog time-complexity on even the hardest benchmark $k$-SAT ($k \\geq 3$) formulas, but at an energy cost through exponentially driven auxiliary variables. With some modifications to the CTDS equations, here we present a novel analog hardware SAT solver, AC-SAT, implementing the CTDS. AC-SAT is intended to be used as a co-processor, and with its modular design can be readily extended to different problem sizes. The circuit is designed and simulated based on a 32nm CMOS technology. SPICE simulation results show speedup factor...

  6. Boolean Satisfiability using Noise Based Logic

    CERN Document Server

    Lin, Pey-Chang Kent; Khatri, Sunil P

    2011-01-01

    In this paper, we present a novel algorithm to solve the Boolean Satisfiability (SAT) problem, using noise-based logic (NBL). Contrary to what the name may suggest, NBL is not a random/fuzzy logic system. In fact, it is a completely deterministic logic system. A key property of NBL is that it allows us to apply a superposition of many input vectors to a SAT instance at the same time, circumventing a key restriction and assumption in the traditional approach to solving SAT. By exploiting the superposition property of NBL, our NBL-based SAT algorithm can determine whether an instance is SAT or not in a single operation. A satisfying solution can be found by iteratively performing SAT check operations up to n times, where n is the number of variables in the SAT instance. Although this paper does not focus on the realization of an NBL-based SAT engine, such an engine can be conceived using analog circuits (wide-band amplifiers, adders and multipliers), FPGAs or ASICs. Additionally, we also discus scalability of o...

  7. Automorphism groups of some algebras

    Institute of Scientific and Technical Information of China (English)

    PARK; Hong; Goo; LEE; Jeongsig; CHOI; Seul; Hee; NAM; Ki-Bong

    2009-01-01

    The automorphism groups of algebras are found in many papers. Using auto-invariance, we find the automorphism groups of the Laurent extension of the polynomial ring and the quantum n-plane (respectively, twisting polynomial ring) in this work. As an application of the results of this work, we can find the automorphism group of a twisting algebra. We define a generalized Weyl algebra and show that the generalized Weyl algebra is simple. We also find the automorphism group of a generalized Weyl algebra. We show that the generalized Weyl algebra Am,m+n is the universal enveloping algebra of the generalized Witt algebra W(m,m + n).

  8. Automorphism groups of some algebras

    Institute of Scientific and Technical Information of China (English)

    PARK Hong Goo; LEE Jeongsig; CHOI Seul Hee; CHEN XueQing; NAM Ki-Bong

    2009-01-01

    The automorphism groups of algebras are found in many papers. Using auto-invariance, we find the automorphism groups of the Laurent extension of the polynomial ring and the quantum n-plane (respectively, twisting polynomial ring) in this work. As an application of the results of this work, we can find the automorphism group of a twisting algebra. We define a generalized Weyl algebra and show that the generalized Weyl algebra is simple. We also find the automorphism group of a generalized Weyl algebra. We show that the generalized Weyl algebra Am,m+n is the universal enveloping algebra of the generalized Witt algebra W(m, m+n).

  9. The Influence of Canalization on the Robustness of Boolean Networks

    CERN Document Server

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

  10. Constant-Overhead Secure Computation of Boolean Circuits using Preprocessing

    DEFF Research Database (Denmark)

    Damgård, Ivan Bjerre; Zakarias, Sarah Nouhad Haddad

    We present a protocol for securely computing a Boolean circuit $C$ in presence of a dishonest and malicious majority. The protocol is unconditionally secure, assuming access to a preprocessing functionality that is not given the inputs to compute on. For a large number of players the work done...... by each player is the same as the work needed to compute the circuit in the clear, up to a constant factor. Our protocol is the first to obtain these properties for Boolean circuits. On the technical side, we develop new homomorphic authentication schemes based on asymptotically good codes...... with an additional multiplication property. We also show a new algorithm for verifying the product of Boolean matrices in quadratic time with exponentially small error probability, where previous methods would only give a constant error....

  11. Piecewise linear and Boolean models of chemical reaction networks.

    Science.gov (United States)

    Veliz-Cuba, Alan; Kumar, Ajit; Josić, Krešimir

    2014-12-01

    Models of biochemical networks are frequently complex and high-dimensional. Reduction methods that preserve important dynamical properties are therefore essential for their study. Interactions in biochemical networks are frequently modeled using Hill functions ([Formula: see text]). Reduced ODEs and Boolean approximations of such model networks have been studied extensively when the exponent [Formula: see text] is large. However, while the case of small constant [Formula: see text] appears in practice, it is not well understood. We provide a mathematical analysis of this limit and show that a reduction to a set of piecewise linear ODEs and Boolean networks can be mathematically justified. The piecewise linear systems have closed-form solutions that closely track those of the fully nonlinear model. The simpler, Boolean network can be used to study the qualitative behavior of the original system. We justify the reduction using geometric singular perturbation theory and compact convergence, and illustrate the results in network models of a toggle switch and an oscillator.

  12. A more robust Boolean model describing inhibitor binding

    Institute of Scientific and Technical Information of China (English)

    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.

  13. Exploiting Surroundedness for Saliency Detection: A Boolean Map Approach.

    Science.gov (United States)

    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.

  14. Control of Large-Scale Boolean Networks via Network Aggregation.

    Science.gov (United States)

    Zhao, Yin; Ghosh, Bijoy K; Cheng, Daizhan

    2016-07-01

    A major challenge to solve problems in control of Boolean networks is that the computational cost increases exponentially when the number of nodes in the network increases. We consider the problem of controllability and stabilizability of Boolean control networks, address the increasing cost problem by partitioning the network graph into several subnetworks, and analyze the subnetworks separately. Easily verifiable necessary conditions for controllability and stabilizability are proposed for a general aggregation structure. For acyclic aggregation, we develop a sufficient condition for stabilizability. It dramatically reduces the computational complexity if the number of nodes in each block of the acyclic aggregation is small enough compared with the number of nodes in the entire Boolean network.

  15. Constant-overhead secure computation of Boolean circuits using preprocessing

    DEFF Research Database (Denmark)

    Damgård, Ivan Bjerre; Zakarias, S.

    2013-01-01

    We present a protocol for securely computing a Boolean circuit C in presence of a dishonest and malicious majority. The protocol is unconditionally secure, assuming a preprocessing functionality that is not given the inputs. For a large number of players the work for each player is the same...... as computing the circuit in the clear, up to a constant factor. Our protocol is the first to obtain these properties for Boolean circuits. On the technical side, we develop new homomorphic authentication schemes based on asymptotically good codes with an additional multiplication property. We also show a new...... algorithm for verifying the product of Boolean matrices in quadratic time with exponentially small error probability, where previous methods only achieved constant error....

  16. Piecewise linear and Boolean models of chemical reaction networks

    Science.gov (United States)

    Veliz-Cuba, Alan; Kumar, Ajit; Josić, Krešimir

    2014-01-01

    Models of biochemical networks are frequently complex and high-dimensional. Reduction methods that preserve important dynamical properties are therefore essential for their study. Interactions in biochemical networks are frequently modeled using Hill functions (xn/(Jn + xn)). Reduced ODEs and Boolean approximations of such model networks have been studied extensively when the exponent n is large. However, while the case of small constant J appears in practice, it is not well understood. We provide a mathematical analysis of this limit, and show that a reduction to a set of piecewise linear ODEs and Boolean networks can be mathematically justified. The piecewise linear systems have closed form solutions that closely track those of the fully nonlinear model. The simpler, Boolean network can be used to study the qualitative behavior of the original system. We justify the reduction using geometric singular perturbation theory and compact convergence, and illustrate the results in network models of a toggle switch and an oscillator. PMID:25412739

  17. A comparison of hypertext and Boolean access to biomedical information.

    Science.gov (United States)

    Friedman, C P; Wildemuth, B M; Muriuki, M; Gant, S P; Downs, S M; Twarog, R G; de Bliek, R

    1996-01-01

    This study explored which of two modes of access to a biomedical database better supported problem solving in bacteriology. Boolean access, which allowed subjects to frame their queries as combinations of keywords, was compared to hypertext access, which allowed subjects to navigate from one database node to another. The accessible biomedical data were identical across systems. Data were collected from 42 first year medical students, each randomized to the Boolean or hypertext system, before and after their bacteriology course. Subjects worked eight clinical case problems, first using only their personal knowledge and, subsequently, with aid from the database. Database retrievals enabled students to answer questions they could not answer based on personal knowledge only. This effect was greater when personal knowledge of bacteriology was lower. The results also suggest that hypertext was superior to Boolean access in helping subjects identify possible infectious agents in these clinical case problems.

  18. Derived equivalence of algebras

    Institute of Scientific and Technical Information of China (English)

    杜先能

    1997-01-01

    The derived equivalence and stable equivalence of algebras RmA and RmB are studied It is proved, using the tilting complex, that RmA and RmB are derived-equivalent whenever algebras A and B are derived-equivalent

  19. Ready, Set, Algebra?

    Science.gov (United States)

    Levy, Alissa Beth

    2012-01-01

    The California Department of Education (CDE) has long asserted that success Algebra I by Grade 8 is the goal for all California public school students. In fact, the state's accountability system penalizes schools that do not require all of their students to take the Algebra I end-of-course examination by Grade 8 (CDE, 2009). In this dissertation,…

  20. Linear-Algebra Programs

    Science.gov (United States)

    Lawson, C. L.; Krogh, F. T.; Gold, S. S.; Kincaid, D. R.; Sullivan, J.; Williams, E.; Hanson, R. J.; Haskell, K.; Dongarra, J.; Moler, C. B.

    1982-01-01

    The Basic Linear Algebra Subprograms (BLAS) library is a collection of 38 FORTRAN-callable routines for performing basic operations of numerical linear algebra. BLAS library is portable and efficient source of basic operations for designers of programs involving linear algebriac computations. BLAS library is supplied in portable FORTRAN and Assembler code versions for IBM 370, UNIVAC 1100 and CDC 6000 series computers.

  1. Who Takes College Algebra?

    Science.gov (United States)

    Herriott, Scott R.; Dunbar, Steven R.

    2009-01-01

    The common understanding within the mathematics community is that the role of the college algebra course is to prepare students for calculus. Though exceptions are emerging, the curriculum of most college algebra courses and the content of most textbooks on the market both reflect that assumption. This article calls that assumption into question…

  2. Ready, Set, Algebra?

    Science.gov (United States)

    Levy, Alissa Beth

    2012-01-01

    The California Department of Education (CDE) has long asserted that success Algebra I by Grade 8 is the goal for all California public school students. In fact, the state's accountability system penalizes schools that do not require all of their students to take the Algebra I end-of-course examination by Grade 8 (CDE, 2009). In this…

  3. Boolean versus ranked querying for biomedical systematic reviews

    Directory of Open Access Journals (Sweden)

    Cavedon Lawrence

    2010-10-01

    Full Text Available Abstract Background The process of constructing a systematic review, a document that compiles the published evidence pertaining to a specified medical topic, is intensely time-consuming, often taking a team of researchers over a year, with the identification of relevant published research comprising a substantial portion of the effort. The standard paradigm for this information-seeking task is to use Boolean search; however, this leaves the user(s the requirement of examining every returned result. Further, our experience is that effective Boolean queries for this specific task are extremely difficult to formulate and typically require multiple iterations of refinement before being finalized. Methods We explore the effectiveness of using ranked retrieval as compared to Boolean querying for the purpose of constructing a systematic review. We conduct a series of experiments involving ranked retrieval, using queries defined methodologically, in an effort to understand the practicalities of incorporating ranked retrieval into the systematic search task. Results Our results show that ranked retrieval by itself is not viable for this search task requiring high recall. However, we describe a refinement of the standard Boolean search process and show that ranking within a Boolean result set can improve the overall search performance by providing early indication of the quality of the results, thereby speeding up the iterative query-refinement process. Conclusions Outcomes of experiments suggest that an interactive query-development process using a hybrid ranked and Boolean retrieval system has the potential for significant time-savings over the current search process in the systematic reviewing.

  4. Introduction to noncommutative algebra

    CERN Document Server

    Brešar, Matej

    2014-01-01

    Providing an elementary introduction to noncommutative rings and algebras, this textbook begins with the classical theory of finite dimensional algebras. Only after this, modules, vector spaces over division rings, and tensor products are introduced and studied. This is followed by Jacobson's structure theory of rings. The final chapters treat free algebras, polynomial identities, and rings of quotients. Many of the results are not presented in their full generality. Rather, the emphasis is on clarity of exposition and simplicity of the proofs, with several being different from those in other texts on the subject. Prerequisites are kept to a minimum, and new concepts are introduced gradually and are carefully motivated. Introduction to Noncommutative Algebra is therefore accessible to a wide mathematical audience. It is, however, primarily intended for beginning graduate and advanced undergraduate students encountering noncommutative algebra for the first time.

  5. Elements of mathematics algebra

    CERN Document Server

    Bourbaki, Nicolas

    2003-01-01

    This is a softcover reprint of the English translation of 1990 of the revised and expanded version of Bourbaki's, Algèbre, Chapters 4 to 7 (1981). This completes Algebra, 1 to 3, by establishing the theories of commutative fields and modules over a principal ideal domain. Chapter 4 deals with polynomials, rational fractions and power series. A section on symmetric tensors and polynomial mappings between modules, and a final one on symmetric functions, have been added. Chapter 5 was entirely rewritten. After the basic theory of extensions (prime fields, algebraic, algebraically closed, radical extension), separable algebraic extensions are investigated, giving way to a section on Galois theory. Galois theory is in turn applied to finite fields and abelian extensions. The chapter then proceeds to the study of general non-algebraic extensions which cannot usually be found in textbooks: p-bases, transcendental extensions, separability criterions, regular extensions. Chapter 6 treats ordered groups and fields and...

  6. Characterization of Linearly Separable Boolean Functions: A Graph-Theoretic Perspective.

    Science.gov (United States)

    Rao, Yanyi; Zhang, Xianda

    2016-04-05

    In this paper, we present a novel approach for studying Boolean function in a graph-theoretic perspective. In particular, we first transform a Boolean function f of n variables into an induced subgraph Hf of the n-dimensional hypercube, and then, we show the properties of linearly separable Boolean functions on the basis of the analysis of the structure of Hf. We define a new class of graphs, called hyperstar, and prove that the induced subgraph Hf of any linearly separable Boolean function f is a hyperstar. The proposal of hyperstar helps us uncover a number of fundamental properties of linearly separable Boolean functions in this paper.

  7. On Kolmogorov's superpositions and Boolean functions

    Energy Technology Data Exchange (ETDEWEB)

    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.

  8. Analysis of Boolean Equation Systems through Structure Graphs

    CERN Document Server

    Reniers, Michel A; 10.4204/EPTCS.18.7

    2010-01-01

    We analyse the problem of solving Boolean equation systems through the use of structure graphs. The latter are obtained through an elegant set of Plotkin-style deduction rules. Our main contribution is that we show that equation systems with bisimilar structure graphs have the same solution. We show that our work conservatively extends earlier work, conducted by Keiren and Willemse, in which dependency graphs were used to analyse a subclass of Boolean equation systems, viz., equation systems in standard recursive form. We illustrate our approach by a small example, demonstrating the effect of simplifying an equation system through minimisation of its structure graph.

  9. Perturbation propagation in random and evolved Boolean networks

    Energy Technology Data Exchange (ETDEWEB)

    Fretter, Christoph [Instistut fuer Informatik, Martin-Luther-Universitaet Halle-Wittenberg, Von-Seckendorffplatz 1, 06120 Halle (Germany); Szejka, Agnes; Drossel, Barbara [Institut fuer Festkoerperphysik, Technische Universitaet Darmstadt, Hochschulstrasse 6, 64289 Darmstadt (Germany)], E-mail: Christoph.Fretter@informatik.uni-halle.de

    2009-03-15

    In this paper, we investigate the propagation of perturbations in Boolean networks by evaluating the Derrida plot and its modifications. We show that even small random Boolean networks agree well with the predictions of the annealed approximation, but nonrandom networks show a very different behaviour. We focus on networks that were evolved for high dynamical robustness. The most important conclusion is that the simple distinction between frozen, critical and chaotic networks is no longer useful, since such evolved networks can display the properties of all three types of networks. Furthermore, we evaluate a simplified empirical network and show how its specific state space properties are reflected in the modified Derrida plots.

  10. Optimization-Based Approaches to Control of Probabilistic Boolean Networks

    Directory of Open Access Journals (Sweden)

    Koichi Kobayashi

    2017-02-01

    Full Text Available Control of gene regulatory networks is one of the fundamental topics in systems biology. In the last decade, control theory of Boolean networks (BNs, which is well known as a model of gene regulatory networks, has been widely studied. In this review paper, our previously proposed methods on optimal control of probabilistic Boolean networks (PBNs are introduced. First, the outline of PBNs is explained. Next, an optimal control method using polynomial optimization is explained. The finite-time optimal control problem is reduced to a polynomial optimization problem. Furthermore, another finite-time optimal control problem, which can be reduced to an integer programming problem, is also explained.

  11. Periodic pattern detection in sparse boolean sequences

    Directory of Open Access Journals (Sweden)

    Hérisson Joan

    2010-09-01

    Full Text Available Abstract Background The specific position of functionally related genes along the DNA has been shown to reflect the interplay between chromosome structure and genetic regulation. By investigating the statistical properties of the distances separating such genes, several studies have highlighted various periodic trends. In many cases, however, groups built up from co-functional or co-regulated genes are small and contain wrong information (data contamination so that the statistics is poorly exploitable. In addition, gene positions are not expected to satisfy a perfectly ordered pattern along the DNA. Within this scope, we present an algorithm that aims to highlight periodic patterns in sparse boolean sequences, i.e. sequences of the type 010011011010... where the ratio of the number of 1's (denoting here the transcription start of a gene to 0's is small. Results The algorithm is particularly robust with respect to strong signal distortions such as the addition of 1's at arbitrary positions (contaminated data, the deletion of existing 1's in the sequence (missing data and the presence of disorder in the position of the 1's (noise. This robustness property stems from an appropriate exploitation of the remarkable alignment properties of periodic points in solenoidal coordinates. Conclusions The efficiency of the algorithm is demonstrated in situations where standard Fourier-based spectral methods are poorly adapted. We also show how the proposed framework allows to identify the 1's that participate in the periodic trends, i.e. how the framework allows to allocate a positional score to genes, in the same spirit of the sequence score. The software is available for public use at http://www.issb.genopole.fr/MEGA/Softwares/iSSB_SolenoidalApplication.zip.

  12. The Planar Algebra of a Semisimple and Cosemisimple Hopf Algebra

    Indian Academy of Sciences (India)

    Vijay Kodiyalam; V S Sunder

    2006-11-01

    To a semisimple and cosemisimple Hopf algebra over an algebraically closed field, we associate a planar algebra defined by generators and relations and show that it is a connected, irreducible, spherical, non-degenerate planar algebra with non-zero modulus and of depth two. This association is shown to yield a bijection between (the isomorphism classes, on both sides, of) such objects.

  13. Graded Lie Algebra Generating of Parastatistical Algebraic Relations

    Institute of Scientific and Technical Information of China (English)

    JING Si-Cong; YANG Wei-Min; LI Ping

    2001-01-01

    A new kind of graded Lie algebra (We call it Z2,2 graded Lie algebra) is introduced as a framework for formulating parasupersymmetric theories. By choosing suitable Bose subspace of the Z2,2 graded Lie algebra and using relevant generalized Jacobi identities, we generate the whole algebraic structure of parastatistics.

  14. Crisp Sets and Boolean Algebra: A Research Strategy for Student Affairs

    Science.gov (United States)

    Banning, James; Eversole, Barbara; Most, David; Kuk, Linda

    2008-01-01

    A review of student affairs journals clearly points out that most, if not all, research strategies within the field fall within traditional approaches based on quantitative methods and, more recently, qualitative methods. The purpose of this article is not to discourage use of these time honored research strategies, but to suggest the inclusion of…

  15. FP-soft Boolean Algebra%FP-软布尔代数

    Institute of Scientific and Technical Information of China (English)

    刘卫锋; 许宏伟; 何霞

    2015-01-01

    将FP-软集(Fuzzy Parameterized Soft Sets)与布尔代数相结合,定义了FP-软布尔代数、FP-软布尔子代数、FP-软布尔代数的FP-软理想、FP-理想软布尔代数等概念,研究了它们的相关性质.最后,讨论了FP-软布尔代数的同态.

  16. Derivations of Atomic Boolean Lattice Algebras%原子Boolean格代数的导子

    Institute of Scientific and Technical Information of China (English)

    徐本龙; 马吉溥

    1999-01-01

    设ふ是Banach空间X上的原子Boolean子空间格,δ是algふ的任一导子,则存在X中的一个稠定线性算子T,使得δ(A)=AT-TA(A∈algふ)在T的定义域ふ(T)上成立.另外,如果ふ还是一个有限格,并且对ふ的任一原子L,L+L′闭,则δ是连续的和内的.

  17. The Boolean sub-algebra on Quantales%Quantale上的Boolean子代数

    Institute of Scientific and Technical Information of China (English)

    潘芳芳; 王顺钦

    2008-01-01

    给出了单位Quantale上的Boolean子代数的概念,并讨论了Boolean子代数若干性质;同时介绍了左(右)保持元和左(右)零化子,并研究了最小左保持与最大左零化子限制在完备Boolean子代数上两者之间的关系.

  18. Leibniz algebras associated with representations of filiform Lie algebras

    Science.gov (United States)

    Ayupov, Sh. A.; Camacho, L. M.; Khudoyberdiyev, A. Kh.; Omirov, B. A.

    2015-12-01

    In this paper we investigate Leibniz algebras whose quotient Lie algebra is a naturally graded filiform Lie algebra nn,1. We introduce a Fock module for the algebra nn,1 and provide classification of Leibniz algebras L whose corresponding Lie algebra L / I is the algebra nn,1 with condition that the ideal I is a Fock nn,1-module, where I is the ideal generated by squares of elements from L. We also consider Leibniz algebras with corresponding Lie algebra nn,1 and such that the action I ×nn,1 → I gives rise to a minimal faithful representation of nn,1. The classification up to isomorphism of such Leibniz algebras is given for the case of n = 4.

  19. On Linear Algebra Education

    Directory of Open Access Journals (Sweden)

    Sinan AYDIN

    2009-04-01

    Full Text Available Linear algebra is a basic course followed in mathematics, science, and engineering university departments.Generally, this course is taken in either the first or second year but there have been difficulties in teachingand learning. This type of active algebra has resulted in an increase in research by mathematics educationresearchers. But there is insufficient information on this subject in Turkish and therefore it has not beengiven any educational status. This paper aims to give a general overview of this subject in teaching andlearning. These education studies can be considered quadruple: a the history of linear algebra, b formalismobstacles of linear algebra and cognitive flexibility to improve teaching and learning, c the relation betweenlinear algebra and geometry, d using technology in the teaching and learning linear algebra.Mathematicseducation researchers cannot provide an absolute solution to overcome the teaching and learning difficultiesof linear algebra. Epistemological analyses and experimental teaching have shown the learning difficulties.Given these results, further advice and assistance can be offered locally.

  20. Linear algebraic groups

    CERN Document Server

    Springer, T A

    1998-01-01

    "[The first] ten chapters...are an efficient, accessible, and self-contained introduction to affine algebraic groups over an algebraically closed field. The author includes exercises and the book is certainly usable by graduate students as a text or for self-study...the author [has a] student-friendly style… [The following] seven chapters... would also be a good introduction to rationality issues for algebraic groups. A number of results from the literature…appear for the first time in a text." –Mathematical Reviews (Review of the Second Edition) "This book is a completely new version of the first edition. The aim of the old book was to present the theory of linear algebraic groups over an algebraically closed field. Reading that book, many people entered the research field of linear algebraic groups. The present book has a wider scope. Its aim is to treat the theory of linear algebraic groups over arbitrary fields. Again, the author keeps the treatment of prerequisites self-contained. The material of t...

  1. On dibaric and evolution algebras

    CERN Document Server

    Ladra, M; Rozikov, U A

    2011-01-01

    We find conditions on ideals of an algebra under which the algebra is dibaric. Dibaric algebras have not non-zero homomorphisms to the set of the real numbers. We introduce a concept of bq-homomorphism (which is given by two linear maps $f, g$ of the algebra to the set of the real numbers) and show that an algebra is dibaric if and only if it admits a non-zero bq-homomorphism. Using the pair $(f,g)$ we define conservative algebras and establish criteria for a dibaric algebra to be conservative. Moreover, the notions of a Bernstein algebra and an algebra induced by a linear operator are introduced and relations between these algebras are studied. For dibaric algebras we describe a dibaric algebra homomorphism and study their properties by bq-homomorphisms of the dibaric algebras. We apply the results to the (dibaric) evolution algebra of a bisexual population. For this dibaric algebra we describe all possible bq-homomorphisms and find conditions under which the algebra of a bisexual population is induced by a ...

  2. Classification of Noncommutative Domain Algebras

    CERN Document Server

    Arias, Alvaro

    2012-01-01

    Noncommutative domain algebras are noncommutative analogues of the algebras of holomorphic functions on domains of $\\C^n$ defined by holomorphic polynomials, and they generalize the noncommutative Hardy algebras. We present here a complete classification of these algebras based upon techniques inspired by multivariate complex analysis, and more specifically the classification of domains in hermitian spaces up to biholomorphic equivalence.

  3. Process algebra for Hybrid systems

    NARCIS (Netherlands)

    Bergstra, J.A.; Middelburg, C.A.

    2008-01-01

    We propose a process algebra obtained by extending a combination of the process algebra with continuous relative timing from Baeten and Middelburg [Process Algebra with Timing, Springer, Chap. 4, 2002] and the process algebra with propositional signals from Baeten and Bergstra [Theoretical Computer

  4. Process algebra for hybrid systems

    NARCIS (Netherlands)

    Bergstra, J.A.; Middelburg, C.A.

    2005-01-01

    We propose a process algebra obtained by extending a combination of the process algebra with continuous relative timing from Baeten and Middelburg (Process Algebra with Timing, Springer,Berlin, 2002, Chapter 4), and the process algebra with propositional signals from Baeten and Bergstra(Theoret. Com

  5. Brauer algebras of type B

    NARCIS (Netherlands)

    Cohen, A.M.; Liu, S.

    2015-01-01

    For each n ≥ 1, we define an algebra having many properties that one might expect to hold for a Brauer algebra of type Bn. It is defined by means of a presentation by generators and relations. We show that this algebra is a subalgebra of the Brauer algebra of type Dn+1 and point out a cellular struc

  6. Symplectic algebraic dynamics algorithm

    Institute of Scientific and Technical Information of China (English)

    2007-01-01

    Based on the algebraic dynamics solution of ordinary differential equations andintegration of  ,the symplectic algebraic dynamics algorithm sn is designed,which preserves the local symplectic geometric structure of a Hamiltonian systemand possesses the same precision of the na ve algebraic dynamics algorithm n.Computer experiments for the 4th order algorithms are made for five test modelsand the numerical results are compared with the conventional symplectic geometric algorithm,indicating that sn has higher precision,the algorithm-inducedphase shift of the conventional symplectic geometric algorithm can be reduced,and the dynamical fidelity can be improved by one order of magnitude.

  7. Bundles of Banach algebras

    Directory of Open Access Journals (Sweden)

    J. W. Kitchen

    1994-01-01

    Full Text Available We study bundles of Banach algebras π:A→X, where each fiber Ax=π−1({x} is a Banach algebra and X is a compact Hausdorff space. In the case where all fibers are commutative, we investigate how the Gelfand representation of the section space algebra Γ(π relates to the Gelfand representation of the fibers. In the general case, we investigate how adjoining an identity to the bundle π:A→X relates to the standard adjunction of identities to the fibers.

  8. Matrices and linear algebra

    CERN Document Server

    Schneider, Hans

    1989-01-01

    Linear algebra is one of the central disciplines in mathematics. A student of pure mathematics must know linear algebra if he is to continue with modern algebra or functional analysis. Much of the mathematics now taught to engineers and physicists requires it.This well-known and highly regarded text makes the subject accessible to undergraduates with little mathematical experience. Written mainly for students in physics, engineering, economics, and other fields outside mathematics, the book gives the theory of matrices and applications to systems of linear equations, as well as many related t

  9. Boolean approaches to graph embeddings related to VLSI

    Institute of Scientific and Technical Information of China (English)

    刘彦佩

    2001-01-01

    This paper discusses the development of Boolean methods in some topics on graph em-beddings which are related to VLSI. They are mainly the general theory of graph embeddability, the orientabilities of a graph and the rectilinear layout of an electronic circuit.

  10. Learning restricted Boolean network model by time-series data.

    Science.gov (United States)

    Ouyang, Hongjia; Fang, Jie; Shen, Liangzhong; Dougherty, Edward R; Liu, Wenbin

    2014-01-01

    Restricted Boolean networks are simplified Boolean networks that are required for either negative or positive regulations between genes. Higa et al. (BMC Proc 5:S5, 2011) proposed a three-rule algorithm to infer a restricted Boolean network from time-series data. However, the algorithm suffers from a major drawback, namely, it is very sensitive to noise. In this paper, we systematically analyze the regulatory relationships between genes based on the state switch of the target gene and propose an algorithm with which restricted Boolean networks may be inferred from time-series data. We compare the proposed algorithm with the three-rule algorithm and the best-fit algorithm based on both synthetic networks and a well-studied budding yeast cell cycle network. The performance of the algorithms is evaluated by three distance metrics: the normalized-edge Hamming distance [Formula: see text], the normalized Hamming distance of state transition [Formula: see text], and the steady-state distribution distance μ (ssd). Results show that the proposed algorithm outperforms the others according to both [Formula: see text] and [Formula: see text], whereas its performance according to μ (ssd) is intermediate between best-fit and the three-rule algorithms. Thus, our new algorithm is more appropriate for inferring interactions between genes from time-series data.

  11. Profiling of genetic switches using boolean implications in expression data.

    Science.gov (United States)

    Çakır, Mehmet Volkan; Binder, Hans; Wirth, Henry

    2014-01-01

    Correlation analysis assuming coexpression of the genes is a widely used method for gene expression analysis in molecular biology. Yet growing extent, quality and dimensionality of the molecular biological data permits emerging, more sophisticated approaches like Boolean implications. We present an approach which is a combination of the SOM (self organizing maps) machine learning method and Boolean implication analysis to identify relations between genes, metagenes and similarly behaving metagene groups (spots). Our method provides a way to assign Boolean states to genes/metagenes/spots and offers a functional view over significantly variant elements of gene expression data on these three different levels. While being able to cover relations between weakly correlated entities Boolean implication method also decomposes these relations into six implication classes. Our method allows one to validate or identify potential relationships between genes and functional modules of interest and to assess their switching behaviour. Furthermore the output of the method renders it possible to construct and study the network of genes. By providing logical implications as updating rules for the network it can also serve to aid modelling approaches.

  12. Linear Strategy for Boolean Ring Based Theorem Proving

    Institute of Scientific and Technical Information of China (English)

    WU Jinzhao; LIU Zhuojun

    2000-01-01

    Two inference rules are discussed in boolean ring based theorem proving, and linear strategy is developed. It is shown that both of them are complete for linear strategy. Moreover, by introducing a partial ordering on atoms, pseudo O-linear and O-linear strategies are presented. The former is complete, the latter, however, is complete for clausal theorem proving.

  13. Boolean linear differential operators on elementary cellular automata

    Science.gov (United States)

    Martín Del Rey, Ángel

    2014-12-01

    In this paper, the notion of boolean linear differential operator (BLDO) on elementary cellular automata (ECA) is introduced and some of their more important properties are studied. Special attention is paid to those differential operators whose coefficients are the ECA with rule numbers 90 and 150.

  14. New Considerations for Spectral Classification of Boolean Switching Functions

    Directory of Open Access Journals (Sweden)

    J. E. Rice

    2011-01-01

    Full Text Available This paper presents some new considerations for spectral techniques for classification of Boolean functions. These considerations incorporate discussions of the feasibility of extending this classification technique beyond n=5. A new implementation is presented along with a basic analysis of the complexity of the problem. We also note a correction to results in this area that were reported in previous work.

  15. Pointwise Approximation for the Iterated Boolean Sums of Bernstein Operators

    Institute of Scientific and Technical Information of China (English)

    HUO Xiao-yan; LI Cui-xiang; YAO Qiu-mei

    2013-01-01

    In this paper,with the help of modulus of smoothness ω2r(4)(f,t),we discuss the pointwise approximation properties for the iterated Boolean sums of Bernstein operator Bnn and obtain direct and inverse theorems when 1-1/r ≤ λ ≤ 1,r ∈ N.

  16. Learning restricted Boolean network model by time-series data

    Science.gov (United States)

    2014-01-01

    Restricted Boolean networks are simplified Boolean networks that are required for either negative or positive regulations between genes. Higa et al. (BMC Proc 5:S5, 2011) proposed a three-rule algorithm to infer a restricted Boolean network from time-series data. However, the algorithm suffers from a major drawback, namely, it is very sensitive to noise. In this paper, we systematically analyze the regulatory relationships between genes based on the state switch of the target gene and propose an algorithm with which restricted Boolean networks may be inferred from time-series data. We compare the proposed algorithm with the three-rule algorithm and the best-fit algorithm based on both synthetic networks and a well-studied budding yeast cell cycle network. The performance of the algorithms is evaluated by three distance metrics: the normalized-edge Hamming distance μhame, the normalized Hamming distance of state transition μhamst, and the steady-state distribution distance μssd. Results show that the proposed algorithm outperforms the others according to both μhame and μhamst, whereas its performance according to μssd is intermediate between best-fit and the three-rule algorithms. Thus, our new algorithm is more appropriate for inferring interactions between genes from time-series data. PMID:25093019

  17. Unlimited multistability and Boolean logic in microbial signalling

    DEFF Research Database (Denmark)

    Kothamachu, Varun B; Feliu, Elisenda; Cardelli, Luca;

    2015-01-01

    further prove that sharing of downstream components allows a system with n multi-domain hybrid HKs to attain 3n steady states. We find that such systems, when sensing distinct signals, can readily implement Boolean logic functions on these signals. Using two experimentally studied examples of two...

  18. Complexity of Identification and Dualization of Positive Boolean Functions

    NARCIS (Netherlands)

    J.C. Bioch (Cor); T. Ibaraki

    1995-01-01

    textabstractWe consider in this paper the problem of identifying min T(f{hook}) and max F(f{hook}) of a positive (i.e., monotone) Boolean function f{hook}, by using membership queries only, where min T(f{hook}) (max F(f{hook})) denotes the set of minimal true vectors (maximal false vectors) of f{hoo

  19. On isomorphisms of integral table algebras

    Institute of Scientific and Technical Information of China (English)

    FAN; Yun(樊恽); SUN; Daying(孙大英)

    2002-01-01

    For integral table algebras with integral table basis T, we can consider integral R-algebra RT over a subring R of the ring of the algebraic integers. It is proved that an R-algebra isomorphism between two integral table algebras must be an integral table algebra isomorphism if it is compatible with the so-called normalizings of the integral table algebras.

  20. Synchronization Analysis and Design of Coupled Boolean Networks Based on Periodic Switching Sequences.

    Science.gov (United States)

    Zhang, Huaguang; Tian, Hui; Wang, Zhanshan; Hou, Yanfang

    2016-12-01

    A novel synchronization analysis method is developed to solve the complete synchronization problem of many Boolean networks (BNs) coupled in the leader-follower configuration. First, an error system is constructed in terms of the algebraic representation using the semitensor product of matrices. Then, the synchronization problem of coupled BNs is converted into a problem whether all the trajectories of the error system are convergent to the zero vector. Second, according to the structure analysis of this error system, which is in the form of a switched system with leader BN states as the switching signal, a necessary and sufficient synchronization condition is derived. An algorithm is developed, which helps to determine as soon as possible whether complete synchronization among coupled BNs is achieved. Finally, a constructive design approach to follower BNs is provided. All of these follower BNs designed by our approach can completely synchronize with a given leader BN from the (Tt+1) th step at most, where Tt is the transient period of the leader BN.

  1. Introduction to algebra

    CERN Document Server

    Cameron, Peter J

    2007-01-01

    This Second Edition of a classic algebra text includes updated and comprehensive introductory chapters,. new material on axiom of Choice, p-groups and local rings, discussion of theory and applications, and over 300 exercises. It is an ideal introductory text for all Year 1 and 2 undergraduate students in mathematics. - ;Developed to meet the needs of modern students, this Second Edition of the classic algebra text by Peter Cameron covers all the abstract algebra an undergraduate student is likely to need. Starting with an introductory overview of numbers, sets and functions, matrices, polynomials, and modular arithmetic, the text then introduces the most important algebraic structures: groups, rings and fields, and their properties. This is followed by coverage of vector spaces and modules with. applications to abelian groups and canonical forms before returning to the construction of the number systems, including the existence of transcendental numbers. The final chapters take the reader further into the th...

  2. The Algebra of -relations

    Indian Academy of Sciences (India)

    Vijay Kodiyalam; R Srinivasan; V S Sunder

    2000-08-01

    In this paper, we study a tower $\\{A^G_n(d):n≥ 1\\}$ of finite-dimensional algebras; here, represents an arbitrary finite group, denotes a complex parameter, and the algebra $A^G_n(d)$ has a basis indexed by `-stable equivalence relations' on a set where acts freely and has 2 orbits. We show that the algebra $A^G_n(d)$ is semi-simple for all but a finite set of values of , and determine the representation theory (or, equivalently, the decomposition into simple summands) of this algebra in the `generic case'. Finally we determine the Bratteli diagram of the tower $\\{A^G_n(d): n≥ 1\\}$ (in the generic case).

  3. Weyl n-Algebras

    Science.gov (United States)

    Markarian, Nikita

    2017-03-01

    We introduce Weyl n-algebras and show how their factorization complex may be used to define invariants of manifolds. In the appendix, we heuristically explain why these invariants must be perturbative Chern-Simons invariants.

  4. Linear algebra done right

    CERN Document Server

    Axler, Sheldon

    2015-01-01

    This best-selling textbook for a second course in linear algebra is aimed at undergrad math majors and graduate students. The novel approach taken here banishes determinants to the end of the book. The text focuses on the central goal of linear algebra: understanding the structure of linear operators on finite-dimensional vector spaces. The author has taken unusual care to motivate concepts and to simplify proofs. A variety of interesting exercises in each chapter helps students understand and manipulate the objects of linear algebra. The third edition contains major improvements and revisions throughout the book. More than 300 new exercises have been added since the previous edition. Many new examples have been added to illustrate the key ideas of linear algebra. New topics covered in the book include product spaces, quotient spaces, and dual spaces. Beautiful new formatting creates pages with an unusually pleasant appearance in both print and electronic versions. No prerequisites are assumed other than the ...

  5. Parametrizing Algebraic Curves

    OpenAIRE

    Lemmermeyer, Franz

    2011-01-01

    We present the technique of parametrization of plane algebraic curves from a number theorist's point of view and present Kapferer's simple and beautiful (but little known) proof that nonsingular curves of degree > 2 cannot be parametrized by rational functions.

  6. Dynamic network-based epistasis analysis: Boolean examples

    Directory of Open Access Journals (Sweden)

    Eugenio eAzpeitia

    2011-12-01

    Full Text Available In this review we focus on how the hierarchical and single-path assumptions of epistasis analysis can bias the topologies of gene interactions infered. This has been acknowledged in several previous papers and reviews, but here we emphasize the critical importance of dynamic analyses, and specifically illustrate the use of Boolean network models. Epistasis in a broad sense refers to gene interactions, however, as originally proposed by Bateson (herein, classical epistasis, defined as the blocking of a particular allelic effect due to the effect of another allele at a different locus. Classical epistasis analysis has proven powerful and useful, allowing researchers to infer and assign directionality to gene interactions. As larger data sets are becoming available, the analysis of classical epistasis is being complemented with computer science tools and system biology approaches. We show that when the hierarchical and single-path assumptions are not met in classical epistasis analysis, the access to relevant information and the correct gene interaction topologies are hindered, and it becomes necessary to consider the temporal dynamics of gene interactions. The use of dynamical networks can overcome these limitations. We particularly focus on the use of Boolean networks that, like classical epistasis analysis, relies on logical formalisms, and hence can complement classical epistasis analysis and relax its assumptions. We develop a couple of theoretical examples and analyze them from a dynamic Boolean network model perspective. Boolean networks could help to guide additional experiments and discern among alternative regulatory schemes that would be impossible or difficult to infer without the elimination of these assumption from the classical epistasis analysis. We also use examples from the literature to show how a Boolean network-based approach has resolved ambiguities and guided epistasis analysis. Our review complements previous accounts, not

  7. Beginning algebra a textworkbook

    CERN Document Server

    McKeague, Charles P

    1985-01-01

    Beginning Algebra: A Text/Workbook, Second Edition focuses on the principles, operations, and approaches involved in algebra. The publication first elaborates on the basics, linear equations and inequalities, and graphing and linear systems. Discussions focus on solving linear systems by graphing, elimination method, graphing ordered pairs and straight lines, linear and compound inequalities, addition and subtraction of real numbers, and properties of real numbers. The text then examines exponents and polynomials, factoring, and rational expressions. Topics include multiplication and division

  8. Intermediate algebra a textworkbook

    CERN Document Server

    McKeague, Charles P

    1985-01-01

    Intermediate Algebra: A Text/Workbook, Second Edition focuses on the principles, operations, and approaches involved in intermediate algebra. The publication first takes a look at basic properties and definitions, first-degree equations and inequalities, and exponents and polynomials. Discussions focus on properties of exponents, polynomials, sums, and differences, multiplication of polynomials, inequalities involving absolute value, word problems, first-degree inequalities, real numbers, opposites, reciprocals, and absolute value, and addition and subtraction of real numbers. The text then ex

  9. Introduction to abstract algebra

    CERN Document Server

    Nicholson, W Keith

    2012-01-01

    Praise for the Third Edition ". . . an expository masterpiece of the highest didactic value that has gained additional attractivity through the various improvements . . ."-Zentralblatt MATH The Fourth Edition of Introduction to Abstract Algebra continues to provide an accessible approach to the basic structures of abstract algebra: groups, rings, and fields. The book's unique presentation helps readers advance to abstract theory by presenting concrete examples of induction, number theory, integers modulo n, and permutations before the abstract structures are defined. Readers can immediately be

  10. Noncommutative algebra and geometry

    CERN Document Server

    De Concini, Corrado; Vavilov, Nikolai 0

    2005-01-01

    Finite Galois Stable Subgroups of Gln. Derived Categories for Nodal Rings and Projective Configurations. Crowns in Profinite Groups and Applications. The Galois Structure of Ambiguous Ideals in Cyclic Extensions of Degree 8. An Introduction to Noncommutative Deformations of Modules. Symmetric Functions, Noncommutative Symmetric Functions and Quasisymmetric Functions II. Quotient Grothendieck Representations. On the Strong Rigidity of Solvable Lie Algebras. The Role of Bergman in Invesigating Identities in Matrix Algebras with Symplectic Involution. The Triangular Structure of Ladder Functors.

  11. Generalized braided Hopf algebras

    Institute of Scientific and Technical Information of China (English)

    LU Zhong-jian; FANG Xiao-li

    2009-01-01

    The concept of (f, σ)-pair (B, H)is introduced, where B and H are Hopf algebras. A braided tensor category which is a tensor subcategory of the category HM of left H-comodules through an (f, σ)-pair is constructed. In particularly, a Yang-Baxter equation is got. A Hopf algebra is constructed as well in the Yetter-Drinfel'd category HHYD by twisting the multiplication of B.

  12. Elementary linear algebra

    CERN Document Server

    Andrilli, Stephen

    2010-01-01

    Elementary Linear Algebra develops and explains in careful detail the computational techniques and fundamental theoretical results central to a first course in linear algebra. This highly acclaimed text focuses on developing the abstract thinking essential for further mathematical study. The authors give early, intensive attention to the skills necessary to make students comfortable with mathematical proofs. The text builds a gradual and smooth transition from computational results to general theory of abstract vector spaces. It also provides flexbile coverage of practical applications, expl

  13. Intermediate algebra & analytic geometry

    CERN Document Server

    Gondin, William R

    1967-01-01

    Intermediate Algebra & Analytic Geometry Made Simple focuses on the principles, processes, calculations, and methodologies involved in intermediate algebra and analytic geometry. The publication first offers information on linear equations in two unknowns and variables, functions, and graphs. Discussions focus on graphic interpretations, explicit and implicit functions, first quadrant graphs, variables and functions, determinate and indeterminate systems, independent and dependent equations, and defective and redundant systems. The text then examines quadratic equations in one variable, system

  14. Differential Hopf algebra structures on the universal enveloping algebra of a lie algebra

    OpenAIRE

    Hijligenberg, van den, N.W.; Martini, R.

    1995-01-01

    We discuss a method to construct a De Rham complex (differential algebra) of Poincar'e-Birkhoff-Witt-type on the universal enveloping algebra of a Lie algebra $g$. We determine the cases in which this gives rise to a differential Hopf algebra that naturally extends the Hopf algebra structure of $U(g)$. The construction of such differential structures is interpreted in terms of colour Lie superalgebras.

  15. Topological ∗-algebras with *-enveloping Algebras II

    Indian Academy of Sciences (India)

    S J Bhatt

    2001-02-01

    Universal *-algebras *() exist for certain topological ∗-algebras called algebras with a *-enveloping algebra. A Frechet ∗-algebra has a *-enveloping algebra if and only if every operator representation of maps into bounded operators. This is proved by showing that every unbounded operator representation , continuous in the uniform topology, of a topological ∗-algebra , which is an inverse limit of Banach ∗-algebras, is a direct sum of bounded operator representations, thereby factoring through the enveloping pro-* algebra () of . Given a *-dynamical system (, , ), any topological ∗-algebra containing (, ) as a dense ∗-subalgebra and contained in the crossed product *-algebra *(, , ) satisfies ()=*(, , ). If $G = \\mathbb{R}$, if is an -invariant dense Frechet ∗-subalgebra of such that () = , and if the action on is -tempered, smooth and by continuous ∗-automorphisms: then the smooth Schwartz crossed product $S(\\mathbb{R}, B, )$ satisfies $E(S(\\mathbb{R}, B, )) = C^*(\\mathbb{R}, A, )$. When is a Lie group, the ∞-elements ∞(), the analytic elements () as well as the entire analytic elements () carry natural topologies making them algebras with a *-enveloping algebra. Given a non-unital *-algebra , an inductive system of ideals is constructed satisfying $A = C^*-\\mathrm{ind} \\lim I_$; and the locally convex inductive limit $\\mathrm{ind}\\lim I_$ is an -convex algebra with the *-enveloping algebra and containing the Pedersen ideal of . Given generators with weakly Banach admissible relations , we construct universal topological ∗-algebra (, ) and show that it has a *-enveloping algebra if and only if (, ) is *-admissible.

  16. L-o cto-algebras

    Institute of Scientific and Technical Information of China (English)

    An Hui-hui; Wang Zhi-chun

    2016-01-01

    L-octo-algebra with 8 operations as the Lie algebraic analogue of octo-algebra such that the sum of 8 operations is a Lie algebra is discussed. Any octo-algebra is an L-octo-algebra. The relationships among L-octo-algebras, L-quadri-algebras, L-dendriform algebras, pre-Lie algebras and Lie algebras are given. The close relationships between L-octo-algebras and some interesting structures like Rota-Baxter operators, classical Yang-Baxter equations and some bilinear forms satisfying certain conditions are given also.

  17. Universal Algebra Applied to Hom-Associative Algebras, and More

    OpenAIRE

    Hellström, Lars; Makhlouf, Abdenacer; Silvestrov, Sergei D.

    2014-01-01

    The purpose of this paper is to discuss the universal algebra theory of hom-algebras. This kind of algebra involves a linear map which twists the usual identities. We focus on hom-associative algebras and hom-Lie algebras for which we review the main results. We discuss the envelopment problem, operads, and the Diamond Lemma; the usual tools have to be adapted to this new situation. Moreover we study Hilbert series for the hom-associative operad and free algebra, and describe them up to total...

  18. Axis Problem of Rough 3-Valued Algebras

    Institute of Scientific and Technical Information of China (English)

    Jianhua Dai; Weidong Chen; Yunhe Pan

    2006-01-01

    The collection of all the rough sets of an approximation space has been given several algebraic interpretations, including Stone algebras, regular double Stone algebras, semi-simple Nelson algebras, pre-rough algebras and 3-valued Lukasiewicz algebras. A 3-valued Lukasiewicz algebra is a Stone algebra, a regular double Stone algebra, a semi-simple Nelson algebra, a pre-rough algebra. Thus, we call the algebra constructed by the collection of rough sets of an approximation space a rough 3-valued Lukasiewicz algebra. In this paper,the rough 3-valued Lukasiewicz algebras, which are a special kind of 3-valued Lukasiewicz algebras, are studied. Whether the rough 3-valued Lukasiewicz algebra is a axled 3-valued Lukasiewicz algebra is examined.

  19. Simple algebras of Weyl type

    Institute of Scientific and Technical Information of China (English)

    2001-01-01

    Over a field F of arbitrary characteristic, we define the associative and the Lie algebras of Weyl type on the same vector space A[D]=A[D] from any pair of a commutative associative algebra A with an identity element and the polynomial algebra [D] of a commutative derivation subalgebra D of A. We prove that A[D], as a Lie algebra (modulo its center) or as an associative algebra, is simple if and only if A is D-simple and A[D] acts faithfully on A. Thus we obtain a lot of simple algebras.

  20. Algebra II workbook for dummies

    CERN Document Server

    Sterling, Mary Jane

    2014-01-01

    To succeed in Algebra II, start practicing now Algebra II builds on your Algebra I skills to prepare you for trigonometry, calculus, and a of myriad STEM topics. Working through practice problems helps students better ingest and retain lesson content, creating a solid foundation to build on for future success. Algebra II Workbook For Dummies, 2nd Edition helps you learn Algebra II by doing Algebra II. Author and math professor Mary Jane Sterling walks you through the entire course, showing you how to approach and solve the problems you encounter in class. You'll begin by refreshing your Algebr

  1. Simple Algebras of Invariant Operators

    Institute of Scientific and Technical Information of China (English)

    Xiaorong Shen; J.D.H. Smith

    2001-01-01

    Comtrans algebras were introduced in as algebras with two trilinear operators, a commutator [x, y, z] and a translator , which satisfy certain identities. Previously known simple comtrans algebras arise from rectangular matrices, simple Lie algebras, spaces equipped with a bilinear form having trivial radical, spaces of hermitian operators over a field with a minimum polynomial x2+1. This paper is about generalizing the hermitian case to the so-called invariant case. The main result of this paper shows that the vector space of n-dimensional invariant operators furnishes some comtrans algebra structures, which are simple provided that certain Jordan and Lie algebras are simple.

  2. An efficient approach of attractor calculation for large-scale Boolean gene regulatory networks.

    Science.gov (United States)

    He, Qinbin; Xia, Zhile; Lin, Bin

    2016-11-07

    Boolean network models provide an efficient way for studying gene regulatory networks. The main dynamics of a Boolean network is determined by its attractors. Attractor calculation plays a key role for analyzing Boolean gene regulatory networks. An approach of attractor calculation was proposed in this study, which improved the predecessor-based approach. Furthermore, the proposed approach combined with the identification of constant nodes and simplified Boolean networks to accelerate attractor calculation. The proposed algorithm is effective to calculate all attractors for large-scale Boolean gene regulatory networks. If the average degree of the network is not too large, the algorithm can get all attractors of a Boolean network with dozens or even hundreds of nodes.

  3. Interactions Between Representation Ttheory, Algebraic Topology and Commutative Algebra

    CERN Document Server

    Pitsch, Wolfgang; Zarzuela, Santiago

    2016-01-01

    This book includes 33 expanded abstracts of selected talks given at the two workshops "Homological Bonds Between Commutative Algebra and Representation Theory" and "Brave New Algebra: Opening Perspectives," and the conference "Opening Perspectives in Algebra, Representations, and Topology," held at the Centre de Recerca Matemàtica (CRM) in Barcelona between January and June 2015. These activities were part of the one-semester intensive research program "Interactions Between Representation Theory, Algebraic Topology and Commutative Algebra (IRTATCA)." Most of the abstracts present preliminary versions of not-yet published results and cover a large number of topics (including commutative and non commutative algebra, algebraic topology, singularity theory, triangulated categories, representation theory) overlapping with homological methods. This comprehensive book is a valuable resource for the community of researchers interested in homological algebra in a broad sense, and those curious to learn the latest dev...

  4. An Evaluation of Methods for Inferring Boolean Networks from Time-Series Data.

    Science.gov (United States)

    Berestovsky, Natalie; Nakhleh, Luay

    2013-01-01

    Regulatory networks play a central role in cellular behavior and decision making. Learning these regulatory networks is a major task in biology, and devising computational methods and mathematical models for this task is a major endeavor in bioinformatics. Boolean networks have been used extensively for modeling regulatory networks. In this model, the state of each gene can be either 'on' or 'off' and that next-state of a gene is updated, synchronously or asynchronously, according to a Boolean rule that is applied to the current-state of the entire system. Inferring a Boolean network from a set of experimental data entails two main steps: first, the experimental time-series data are discretized into Boolean trajectories, and then, a Boolean network is learned from these Boolean trajectories. In this paper, we consider three methods for data discretization, including a new one we propose, and three methods for learning Boolean networks, and study the performance of all possible nine combinations on four regulatory systems of varying dynamics complexities. We find that employing the right combination of methods for data discretization and network learning results in Boolean networks that capture the dynamics well and provide predictive power. Our findings are in contrast to a recent survey that placed Boolean networks on the low end of the "faithfulness to biological reality" and "ability to model dynamics" spectra. Further, contrary to the common argument in favor of Boolean networks, we find that a relatively large number of time points in the time-series data is required to learn good Boolean networks for certain data sets. Last but not least, while methods have been proposed for inferring Boolean networks, as discussed above, missing still are publicly available implementations thereof. Here, we make our implementation of the methods available publicly in open source at http://bioinfo.cs.rice.edu/.

  5. Local digital estimators of intrinsic volumes for Boolean models and in the design based setting

    DEFF Research Database (Denmark)

    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...... for the bias obtained for Boolean models are applied to existing algorithms in order to compare their accuracy....

  6. Structure of Solvable Quadratic Lie Algebras

    Institute of Scientific and Technical Information of China (English)

    ZHU Lin-sheng

    2005-01-01

    @@ Killing form plays a key role in the theory of semisimple Lie algebras. It is natural to extend the study to Lie algebras with a nondegenerate symmetric invariant bilinear form. Such a Lie algebra is generally called a quadratic Lie algebra which occur naturally in physics[10,12,13]. Besides semisimple Lie algebras, interesting quadratic Lie algebras include the Kac-Moody algebras and the Extended Affine Lie algebras.

  7. The mathematics of a quantum Hamiltonian computing half adder Boolean logic gate.

    Science.gov (United States)

    Dridi, G; Julien, R; Hliwa, M; Joachim, C

    2015-08-28

    The mathematics behind the quantum Hamiltonian computing (QHC) approach of designing Boolean logic gates with a quantum system are given. Using the quantum eigenvalue repulsion effect, the QHC AND, NAND, OR, NOR, XOR, and NXOR Hamiltonian Boolean matrices are constructed. This is applied to the construction of a QHC half adder Hamiltonian matrix requiring only six quantum states to fullfil a half Boolean logical truth table. The QHC design rules open a nano-architectronic way of constructing Boolean logic gates inside a single molecule or atom by atom at the surface of a passivated semi-conductor.

  8. Algebraic orders on $K_{0}$ and approximately finite operator algebras

    CERN Document Server

    Power, S C

    1993-01-01

    This is a revised and corrected version of a preprint circulated in 1990 in which various non-self-adjoint limit algebras are classified. The principal invariant is the scaled $K_0$ group together with the algebraic order on the scale induced by partial isometries in the algebra.

  9. Approximate Preservers on Banach Algebras and C*-Algebras

    Directory of Open Access Journals (Sweden)

    M. Burgos

    2013-01-01

    Full Text Available The aim of the present paper is to give approximate versions of Hua’s theorem and other related results for Banach algebras and C*-algebras. We also study linear maps approximately preserving the conorm between unital C*-algebras.

  10. The Planar Algebra Associated to a Kac Algebra

    Indian Academy of Sciences (India)

    Vijay Kodiyalam; Zeph Landau; V S Sunder

    2003-02-01

    We obtain (two equivalent) presentations – in terms of generators and relations-of the planar algebra associated with the subfactor corresponding to (an outer action on a factor by) a finite-dimensional Kac algebra. One of the relations shows that the antipode of the Kac algebra agrees with the `rotation on 2-boxes'.

  11. Abstract Algebra for Algebra Teaching: Influencing School Mathematics Instruction

    Science.gov (United States)

    Wasserman, Nicholas H.

    2016-01-01

    This article explores the potential for aspects of abstract algebra to be influential for the teaching of school algebra (and early algebra). Using national standards for analysis, four primary areas common in school mathematics--and their progression across elementary, middle, and secondary mathematics--where teaching may be transformed by…

  12. Derived Algebraic Geometry II: Noncommutative Algebra

    CERN Document Server

    Lurie, Jacob

    2007-01-01

    In this paper, we present an infinity-categorical version of the theory of monoidal categories. We show that the infinity category of spectra admits an essentially unique monoidal structure (such that the tensor product preserves colimits in each variable), and thereby recover the classical smash-product operation on spectra. We develop a general theory of algebras in a monoidal infinity category, which we use to (re)prove some basic results in the theory of associative ring spectra. We also develop an infinity-categorical theory of monads, and prove a version of the Barr-Beck theorem.

  13. Mapping knowledge to boolean dynamic systems in Bateson's epistemology.

    Science.gov (United States)

    Malloy, Thomas E; Jensen, Gary C; Song, Timothy

    2005-01-01

    Gregory Bateson (1972, 1979) established an epistemology that integrates mind and nature as a necessary unity, a unity in which learning and evolution share fundamental principles and in which criteria for mental process are explicitly specified. E42 is a suite of freely available Java applets that constitute an online research lab for creating and interacting with simulations of the Boolean systems developed by Kauffman (1993) in his study of evolution where he proposed that self-organization and natural selection are co-principles "weaving the tapestry of life." This paper maps Boolean systems, developed in the study of evolution, onto Bateson's epistemology in general and onto his criteria of mental process in particular.

  14. High Quality Test Pattern Generation and Boolean Satisfiability

    CERN Document Server

    Eggersglüß, Stephan

    2012-01-01

    This book provides an overview of automatic test pattern generation (ATPG) and introduces novel techniques to complement classical ATPG, based on Boolean Satisfiability (SAT).  A fast and highly fault efficient SAT-based ATPG framework is presented which is also able to generate high-quality delay tests such as robust path delay tests, as well as tests with long propagation paths to detect small delay defects. The aim of the techniques and methodologies presented in this book is to improve SAT-based ATPG, in order to make it applicable in industrial practice. Readers will learn to improve the performance and robustness of the overall test generation process, so that the ATPG algorithm reliably will generate test patterns for most targeted faults in acceptable run time to meet the high fault coverage demands of industry. The techniques and improvements presented in this book provide the following advantages: Provides a comprehensive introduction to test generation and Boolean Satisfiability (SAT); Describes a...

  15. Inference of asynchronous Boolean network from biological pathways.

    Science.gov (United States)

    Das, Haimabati; Layek, Ritwik Kumar

    2015-01-01

    Gene regulation is a complex process with multiple levels of interactions. In order to describe this complex dynamical system with tractable parameterization, the choice of the dynamical system model is of paramount importance. The right abstraction of the modeling scheme can reduce the complexity in the inference and intervention design, both computationally and experimentally. This article proposes an asynchronous Boolean network framework to capture the transcriptional regulation as well as the protein-protein interactions in a genetic regulatory system. The inference of asynchronous Boolean network from biological pathways information and experimental evidence are explained using an algorithm. The suitability of this paradigm for the variability of several reaction rates is also discussed. This methodology and model selection open up new research challenges in understanding gene-protein interactive system in a coherent way and can be beneficial for designing effective therapeutic intervention strategy.

  16. Boolean network representation of contagion dynamics during a financial crisis

    Science.gov (United States)

    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.

  17. The Nonlinearity of Sum and Product for Boolean Functions

    Directory of Open Access Journals (Sweden)

    Huang Jinglian

    2016-01-01

    Full Text Available In this paper, we study the relationship between the nonlinearity of Boolean function and the nonlinearity of the sum and product of Boolean function, while derivative and e-derivative are used to study the problem further. We obtain that the sum of two functions’ nonlinearity is not less than the nonlinearity of the sum of two functions. The relationship between the nonlinearity of function and the nonlinearity of the sum and product of two functions are also obtained. Furthermore, we also get the relationship between the nonlinearity of the product of functions, and the derivative and e-derivative of function. Moreover, we also deduced some important applications on the basis of the above work.

  18. Algorithms for Finding Small Attractors in Boolean Networks

    Directory of Open Access Journals (Sweden)

    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.

  19. Improved Decomposition for a System of Completely Specified Boolean Functions

    Directory of Open Access Journals (Sweden)

    Saeid Taghavi Afshord

    2013-12-01

    Full Text Available Functional decomposition is an important and powerful technique in the logic synthesis. The ternary matrix cover approach is one of the existing methods of this type. This method is also used in decomposition of a system of completely specified Boolean functions. Before constructing the desired superposition, it needs to encode a table. There is a trivial encoding method. But to find a better solution, it is important to use a special approach, because the result of the encoding has a direct influence on the obtained functions. In this paper, an efficient algorithm to encode this table is presented. It uses the approach connected with the assembling Boolean hyper cube method. The proposed algorithm is explained in details with an example. The benefits and impacts of the suggested technique are also discussed.

  20. Canalization and symmetry in Boolean models for genetic regulatory networks

    Energy Technology Data Exchange (ETDEWEB)

    Reichhardt, C J Olson [Theoretical Division and Center for Nonlinear Studies, Los Alamos National Laboratory, Los Alamos, NM 87545 (United States); Bassler, Kevin E [Department of Physics, University of Houston, Houston, TX 77204-5005 (United States)

    2007-04-20

    Canalization of genetic regulatory networks has been argued to be favoured by evolutionary processes due to the stability that it can confer to phenotype expression. We explore whether a significant amount of canalization and partial canalization can arise in purely random networks in the absence of evolutionary pressures. We use a mapping of the Boolean functions in the Kauffman N-K model for genetic regulatory networks onto a k-dimensional Ising hypercube (where k = K) to show that the functions can be divided into different classes strictly due to geometrical constraints. The classes can be counted and their properties determined using results from group theory and isomer chemistry. We demonstrate that partially canalizing functions completely dominate all possible Boolean functions, particularly for higher k. This indicates that partial canalization is extremely common, even in randomly chosen networks, and has implications for how much information can be obtained in experiments on native state genetic regulatory networks.

  1. On K-wise Independent Distributions and Boolean Functions

    CERN Document Server

    Benjamini, Itai; Peled, Ron

    2012-01-01

    We pursue a systematic study of the following problem. Let f:{0,1}^n -> {0,1} be a (usually monotone) Boolean function whose behaviour is well understood when the input bits are identically independently distributed. What can be said about the behaviour of the function when the input bits are not completely independent, but only k-wise independent, i.e. every subset of k bits is independent? more precisely, how high should k be so that any k-wise independent distribution "fools" the function, i.e. causes it to behave nearly the same as when the bits are completely independent? We analyze several well known Boolean functions (including AND, Majority, Tribes and Percolation among others), some of which turn out to have surprising properties. In some of our results we use tools from the theory of the classical moment problem, seemingly for the first time in this subject, to shed light on these questions.

  2. Kramers-Wannier duality applied to the boolean satifiability problem

    Science.gov (United States)

    Mitchell, Joe; Hsu, Benjamin; Galitski, Victor

    2014-03-01

    Kramers-Wannier duality, first considered in 1941, is an exact technique used in statistical mechanics to relate two models together through an order-disorder transformation, and thereby study their structure and critical phenomena. The boolean satisfiability problem is one of the most important problems in computer science, specifically complexity theory; it is the first proven NP-complete problem. Using a mapping to a multi-spin Ising model in the limit of zero temperature, we present an application of Kramers-Wannier duality to this problem. This results in a novel relationship between solving the boolean satisfiability counting problem and a different computational problem: listing the non-negative solutions to a particular system of linear integer equations. This mapping relates the complexity of the two problems. We discuss the generality of Kramers-Wannier duality and its possible application to other computational problems. This research was supported by NSF-CAREER award No. DMR-0847224 and Simons Foundation.

  3. Stability of biological networks as represented in Random Boolean Nets.

    Energy Technology Data Exchange (ETDEWEB)

    Slepoy, Alexander; Thompson, Marshall

    2004-09-01

    We explore stability of Random Boolean Networks as a model of biological interaction networks. We introduce surface-to-volume ratio as a measure of stability of the network. Surface is defined as the set of states within a basin of attraction that maps outside the basin by a bit-flip operation. Volume is defined as the total number of states in the basin. We report development of an object-oriented Boolean network analysis code (Attract) to investigate the structure of stable vs. unstable networks. We find two distinct types of stable networks. The first type is the nearly trivial stable network with a few basins of attraction. The second type contains many basins. We conclude that second type stable networks are extremely rare.

  4. Properties of Boolean networks and methods for their tests

    Science.gov (United States)

    2013-01-01

    Transcriptional regulation networks are often modeled as Boolean networks. We discuss certain properties of Boolean functions (BFs), which are considered as important in such networks, namely, membership to the classes of unate or canalizing functions. Of further interest is the average sensitivity (AS) of functions. In this article, we discuss several algorithms to test the properties of interest. To test canalizing properties of functions, we apply spectral techniques, which can also be used to characterize the AS of functions as well as the influences of variables in unate BFs. Further, we provide and review upper and lower bounds on the AS of unate BFs based on the spectral representation. Finally, we apply these methods to a transcriptional regulation network of Escherichia coli, which controls central parts of the E. coli metabolism. We find that all functions are unate. Also the analysis of the AS of the network reveals an exceptional robustness against transient fluctuations of the binary variables.a PMID:23311536

  5. Effects of a silenced gene in Boolean network models

    Directory of Open Access Journals (Sweden)

    Emir Haliki

    2017-03-01

    Full Text Available Gene regulation and their regulatory networks are one of the most challenging research problems of computational biology and complexity sciences. Gene regulation is formed by indirect interaction between DNA segments which are protein coding genes to configure the expression level of one another. Prevention of expression of any genes in gene regulation at the levels of transcription or translation indicates the gene silencing event. The present study examined what types of results in gene silencing would bring about in the dynamics of Boolean genetic regulatory mechanisms. The analytical study was performed in gene expression variations of Boolean dynamics first, then the related numerical analysis was simulated in real networks in the literature.

  6. Fault Based Techniques for Testing Boolean Expressions: A Survey

    CERN Document Server

    Badhera, Usha; Taruna, S

    2012-01-01

    Boolean expressions are major focus of specifications and they are very much prone to introduction of faults, this survey presents various fault based testing techniques. It identifies that the techniques differ in their fault detection capabilities and generation of test suite. The various techniques like Cause effect graph, meaningful impact strategy, Branch Operator Strategy (BOR), BOR+MI, MUMCUT, Modified Condition/ Decision Coverage (MCDC) has been considered. This survey describes the basic algorithms and fault categories used by these strategies for evaluating their performance. Finally, it contains short summaries of the papers that use Boolean expressions used to specify the requirements for detecting faults. These techniques have been empirically evaluated by various researchers on a simplified safety related real time control system.

  7. Estimation of delays in generalized asynchronous Boolean networks.

    Science.gov (United States)

    Das, Haimabati; Layek, Ritwik Kumar

    2016-10-20

    A new generalized asynchronous Boolean network (GABN) model has been proposed in this paper. This continuous-time discrete-state model captures the biological reality of cellular dynamics without compromising the computational efficiency of the Boolean framework. The GABN synthesis procedure is based on the prior knowledge of the logical structure of the regulatory network, and the experimental transcriptional parameters. The novelty of the proposed methodology lies in considering different delays associated with the activation and deactivation of a particular protein (especially the transcription factors). A few illustrative examples of some well-studied network motifs have been provided to explore the scope of using the GABN model for larger networks. The GABN model of the p53-signaling pathway in response to γ-irradiation has also been simulated in the current paper to provide an indirect validation of the proposed schema.

  8. Autonomous Boolean modelling of developmental gene regulatory networks

    Science.gov (United States)

    Cheng, Xianrui; Sun, Mengyang; Socolar, Joshua E. S.

    2013-01-01

    During early embryonic development, a network of regulatory interactions among genes dynamically determines a pattern of differentiated tissues. We show that important timing information associated with the interactions can be faithfully represented in autonomous Boolean models in which binary variables representing expression levels are updated in continuous time, and that such models can provide a direct insight into features that are difficult to extract from ordinary differential equation (ODE) models. As an application, we model the experimentally well-studied network controlling fly body segmentation. The Boolean model successfully generates the patterns formed in normal and genetically perturbed fly embryos, permits the derivation of constraints on the time delay parameters, clarifies the logic associated with different ODE parameter sets and provides a platform for studying connectivity and robustness in parameter space. By elucidating the role of regulatory time delays in pattern formation, the results suggest new types of experimental measurements in early embryonic development. PMID:23034351

  9. Complexity of Propositional Abduction for Restricted Sets of Boolean Functions

    CERN Document Server

    Creignou, Nadia; Thomas, Michael

    2009-01-01

    Abduction is a fundamental and important form of non-monotonic reasoning. Given a knowledge base explaining how the world behaves it aims at finding an explanation for some observed manifestation. In this paper we focus on propositional abduction, where the knowledge base and the manifestation are represented by propositional formulae. The problem of deciding whether there exists an explanation has been shown to be SigmaP2-complete in general. We consider variants obtained by restricting the allowed connectives in the formulae to certain sets of Boolean functions. We give a complete classification of the complexity for all considerable sets of Boolean functions. In this way, we identify easier cases, namely NP-complete and polynomial cases; and we highlight sources of intractability. Further, we address the problem of counting the explanations and draw a complete picture for the counting complexity.

  10. borealis - A generalized global update algorithm for Boolean optimization problems

    CERN Document Server

    Zhu, Zheng; Katzgraber, Helmut G

    2016-01-01

    Optimization problems with Boolean variables that fall into the nondeterministic polynomial (NP) class are of fundamental importance in computer science, mathematics, physics and industrial applications. Most notably, solving constraint-satisfaction problems, which are related to spin-glass-like Hamiltonians in physics, remains a difficult numerical task. As such, there has been great interest in designing efficient heuristics to solve these computationally difficult problems. Inspired by parallel tempering Monte Carlo in conjunction with the rejection-free isoenergetic cluster algorithm developed for Ising spin glasses, we present a generalized global update optimization heuristic that can be applied to different NP-complete problems with Boolean variables. The global cluster updates allow for a wide-spread sampling of phase space, thus considerably speeding up optimization. By carefully tuning the pseudo-temperature (needed to randomize the configurations) of the problem, we show that the method can efficie...

  11. Resonant algebras and gravity

    CERN Document Server

    Durka, R

    2016-01-01

    We explore the $S$-expansion framework to analyze freedom in closing the multiplication tables for the abelian semigroups. Including possibility of the zero element in the resonant decomposition and relating the Lorentz generator with the semigroup identity element leads to the wide class of the expanded Lie algebras introducing interesting modifications to the gauge gravity theories. Among the results we find not only all the Maxwell algebras of type $\\mathfrak{B}_m$, $\\mathfrak{C}_m$, and recently introduced $\\mathfrak{D}_m$, but we also produce new examples. We discuss some prospects concerning further enlarging the algebras and provide all necessary constituents for constructing the gravity actions based on the obtained results.

  12. Resonant algebras and gravity

    Science.gov (United States)

    Durka, R.

    2017-04-01

    The S-expansion framework is analyzed in the context of a freedom in closing the multiplication tables for the abelian semigroups. Including the possibility of the zero element in the resonant decomposition, and associating the Lorentz generator with the semigroup identity element, leads to a wide class of the expanded Lie algebras introducing interesting modifications to the gauge gravity theories. Among the results, we find all the Maxwell algebras of type {{B}m} , {{C}m} , and the recently introduced {{D}m} . The additional new examples complete the resulting generalization of the bosonic enlargements for an arbitrary number of the Lorentz-like and translational-like generators. Some further prospects concerning enlarging the algebras are discussed, along with providing all the necessary constituents for constructing the gravity actions based on the obtained results.

  13. Basic linear algebra

    CERN Document Server

    Blyth, T S

    2002-01-01

    Basic Linear Algebra is a text for first year students leading from concrete examples to abstract theorems, via tutorial-type exercises. More exercises (of the kind a student may expect in examination papers) are grouped at the end of each section. The book covers the most important basics of any first course on linear algebra, explaining the algebra of matrices with applications to analytic geometry, systems of linear equations, difference equations and complex numbers. Linear equations are treated via Hermite normal forms which provides a successful and concrete explanation of the notion of linear independence. Another important highlight is the connection between linear mappings and matrices leading to the change of basis theorem which opens the door to the notion of similarity. This new and revised edition features additional exercises and coverage of Cramer's rule (omitted from the first edition). However, it is the new, extra chapter on computer assistance that will be of particular interest to readers:...

  14. Adaptive Algebraic Multigrid Methods

    Energy Technology Data Exchange (ETDEWEB)

    Brezina, M; Falgout, R; MacLachlan, S; Manteuffel, T; McCormick, S; Ruge, J

    2004-04-09

    Our ability to simulate physical processes numerically is constrained by our ability to solve the resulting linear systems, prompting substantial research into the development of multiscale iterative methods capable of solving these linear systems with an optimal amount of effort. Overcoming the limitations of geometric multigrid methods to simple geometries and differential equations, algebraic multigrid methods construct the multigrid hierarchy based only on the given matrix. While this allows for efficient black-box solution of the linear systems associated with discretizations of many elliptic differential equations, it also results in a lack of robustness due to assumptions made on the near-null spaces of these matrices. This paper introduces an extension to algebraic multigrid methods that removes the need to make such assumptions by utilizing an adaptive process. The principles which guide the adaptivity are highlighted, as well as their application to algebraic multigrid solution of certain symmetric positive-definite linear systems.

  15. Algebraic number theory

    CERN Document Server

    Jarvis, Frazer

    2014-01-01

    The technical difficulties of algebraic number theory often make this subject appear difficult to beginners. This undergraduate textbook provides a welcome solution to these problems as it provides an approachable and thorough introduction to the topic. Algebraic Number Theory takes the reader from unique factorisation in the integers through to the modern-day number field sieve. The first few chapters consider the importance of arithmetic in fields larger than the rational numbers. Whilst some results generalise well, the unique factorisation of the integers in these more general number fields often fail. Algebraic number theory aims to overcome this problem. Most examples are taken from quadratic fields, for which calculations are easy to perform. The middle section considers more general theory and results for number fields, and the book concludes with some topics which are more likely to be suitable for advanced students, namely, the analytic class number formula and the number field sieve. This is the fi...

  16. Order Units in a *-Algebra

    Indian Academy of Sciences (India)

    Anil K Karn

    2003-02-01

    Order unit property of a positive element in a *-algebra is defined. It is proved that precisely projections satisfy this order theoretic property. This way, unital hereditary *-subalgebras of a *-algebra are characterized.

  17. Linear Mappings of Quaternion Algebra

    OpenAIRE

    Kleyn, Aleks

    2011-01-01

    In the paper I considered linear and antilinear automorphisms of quaternion algebra. I proved the theorem that there is unique expansion of R-linear mapping of quaternion algebra relative to the given set of linear and antilinear automorphisms.

  18. Computer Program For Linear Algebra

    Science.gov (United States)

    Krogh, F. T.; Hanson, R. J.

    1987-01-01

    Collection of routines provided for basic vector operations. Basic Linear Algebra Subprogram (BLAS) library is collection from FORTRAN-callable routines for employing standard techniques to perform basic operations of numerical linear algebra.

  19. Algebra for Gifted Third Graders.

    Science.gov (United States)

    Borenson, Henry

    1987-01-01

    Elementary school children who are exposed to a concrete, hands-on experience in algebraic linear equations will more readily develop a positive mind-set and expectation for success in later formal, algebraic studies. (CB)

  20. J-rings of characteristic two that are boolean

    Directory of Open Access Journals (Sweden)

    D. J. Hansen

    1994-01-01

    Full Text Available This paper is concerned with determining all integers n, with n≥2, such that if R is a ring having the property that xn=x and 2x=0 for each x∈R, then R is boolean. The solution to the above problem extends previous results obtained by Shiue and Chao in [5] and that of MacHale in [4].

  1. On the parity complexity measures of Boolean functions

    OpenAIRE

    Zhang,Zhiqiang; Shi, Yaoyun

    2010-01-01

    The parity decision tree model extends the decision tree model by allowing the computation of a parity function in one step. We prove that the deterministic parity decision tree complexity of any Boolean function is polynomially related to the non-deterministic complexity of the function or its complement. We also show that they are polynomially related to an analogue of the block sensitivity. We further study parity decision trees in their relations with an intermediate variant of the decisi...

  2. Problems in modeling a weighted Boolean retrieval system

    Energy Technology Data Exchange (ETDEWEB)

    Kraft, D.H.; Waller, W.G.

    1979-01-01

    The use of weights to denote a query representation and/or the indexing of a document is analyzed as a generalization of a Boolean retrieval system. Criteria are given for the functions used to evaluate the relevance of the records to a specific query. Various mechanisms for evaluating the relevance of records with regard to a given query are tested and found to be less than satisfactory. A new approach is suggested to avoid some of the perils.

  3. Selection of probability based weighting models for Boolean retrieval system

    Energy Technology Data Exchange (ETDEWEB)

    Ebinuma, Y. (Japan Atomic Energy Research Inst., Tokai, Ibaraki. Tokai Research Establishment)

    1981-09-01

    Automatic weighting models based on probability theory were studied if they can be applied to boolean search logics including logical sum. The INIS detabase was used for searching of one particular search formula. Among sixteen models three with good ranking performance were selected. These three models were further applied to searching of nine search formulas in the same database. It was found that two models among them show slightly better average ranking performance while the other model, the simplest one, seems also practical.

  4. Automorphism groups of pointed Hopf algebras

    Institute of Scientific and Technical Information of China (English)

    YANG Shilin

    2007-01-01

    The group of Hopf algebra automorphisms for a finite-dimensional semisimple cosemisimple Hopf algebra over a field k was considered by Radford and Waterhouse. In this paper, the groups of Hopf algebra automorphisms for two classes of pointed Hopf algebras are determined. Note that the Hopf algebras we consider are not semisimple Hopf algebras.

  5. Elementary algebraic geometry

    CERN Document Server

    Kendig, Keith

    2015-01-01

    Designed to make learning introductory algebraic geometry as easy as possible, this text is intended for advanced undergraduates and graduate students who have taken a one-year course in algebra and are familiar with complex analysis. This newly updated second edition enhances the original treatment's extensive use of concrete examples and exercises with numerous figures that have been specially redrawn in Adobe Illustrator. An introductory chapter that focuses on examples of curves is followed by a more rigorous and careful look at plane curves. Subsequent chapters explore commutative ring th

  6. Algebra task & drill sheets

    CERN Document Server

    Reed, Nat

    2011-01-01

    For grades 3-5, our State Standards-based combined resource meets the algebraic concepts addressed by the NCTM standards and encourages the students to review the concepts in unique ways. The task sheets introduce the mathematical concepts to the students around a central problem taken from real-life experiences, while the drill sheets provide warm-up and timed practice questions for the students to strengthen their procedural proficiency skills. Included are opportunities for problem-solving, patterning, algebraic graphing, equations and determining averages. The combined task & drill sheets

  7. Algebra task & drill sheets

    CERN Document Server

    Reed, Nat

    2011-01-01

    For grades 6-8, our State Standards-based combined resource meets the algebraic concepts addressed by the NCTM standards and encourages the students to review the concepts in unique ways. The task sheets introduce the mathematical concepts to the students around a central problem taken from real-life experiences, while the drill sheets provide warm-up and timed practice questions for the students to strengthen their procedural proficiency skills. Included are opportunities for problem-solving, patterning, algebraic graphing, equations and determining averages. The combined task & drill sheets

  8. Recollements of extension algebras

    Institute of Scientific and Technical Information of China (English)

    CHEN; Qinghua(陈清华); LIN; Yanan(林亚南)

    2003-01-01

    Let A be a finite-dimensional algebra over arbitrary base field k. We prove: if the unbounded derived module category D-(Mod-A) admits symmetric recollement relative to unbounded derived module categories of two finite-dimensional k-algebras B and C:D-(Mod- B) ( ) D-(Mod- A) ( ) D-(Mod- C),then the unbounded derived module category D-(Mod - T(A)) admits symmetric recollement relative to the unbounded derived module categories of T(B) and T(C):D-(Mod - T(B)) ( ) D-(Mod - T(A)) ( ) D-(Mod - T(C)).

  9. Handbook of linear algebra

    CERN Document Server

    Hogben, Leslie

    2013-01-01

    With a substantial amount of new material, the Handbook of Linear Algebra, Second Edition provides comprehensive coverage of linear algebra concepts, applications, and computational software packages in an easy-to-use format. It guides you from the very elementary aspects of the subject to the frontiers of current research. Along with revisions and updates throughout, the second edition of this bestseller includes 20 new chapters.New to the Second EditionSeparate chapters on Schur complements, additional types of canonical forms, tensors, matrix polynomials, matrix equations, special types of

  10. Advanced linear algebra

    CERN Document Server

    Cooperstein, Bruce

    2010-01-01

    Vector SpacesFieldsThe Space FnVector Spaces over an Arbitrary Field Subspaces of Vector SpacesSpan and IndependenceBases and Finite Dimensional Vector SpacesBases and Infinite Dimensional Vector SpacesCoordinate VectorsLinear TransformationsIntroduction to Linear TransformationsThe Range and Kernel of a Linear TransformationThe Correspondence and Isomorphism TheoremsMatrix of a Linear TransformationThe Algebra of L(V, W) and Mmn(F)Invertible Transformations and MatricesPolynomialsThe Algebra of PolynomialsRoots of PolynomialsTheory of a Single Linear OperatorInvariant Subspaces of an Operator

  11. Linear Algebra Thoroughly Explained

    CERN Document Server

    Vujičić, Milan

    2008-01-01

    Linear Algebra Thoroughly Explained provides a comprehensive introduction to the subject suitable for adoption as a self-contained text for courses at undergraduate and postgraduate level. The clear and comprehensive presentation of the basic theory is illustrated throughout with an abundance of worked examples. The book is written for teachers and students of linear algebra at all levels and across mathematics and the applied sciences, particularly physics and engineering. It will also be an invaluable addition to research libraries as a comprehensive resource book for the subject.

  12. Division algebras and supersymmetry

    CERN Document Server

    Baez, John C

    2009-01-01

    Supersymmetry is deeply related to division algebras. Nonabelian Yang--Mills fields minimally coupled to massless spinors are supersymmetric if and only if the dimension of spacetime is 3, 4, 6 or 10. The same is true for the Green--Schwarz superstring. In both cases, supersymmetry relies on the vanishing of a certain trilinear expression involving a spinor field. The reason for this, in turn, is the existence of normed division algebras in dimensions 1, 2, 4 and 8: the real numbers, complex numbers, quaternions and octonions. Here we provide a self-contained account of how this works.

  13. Algebra & trigonometry super review

    CERN Document Server

    2012-01-01

    Get all you need to know with Super Reviews! Each Super Review is packed with in-depth, student-friendly topic reviews that fully explain everything about the subject. The Algebra and Trigonometry Super Review includes sets and set operations, number systems and fundamental algebraic laws and operations, exponents and radicals, polynomials and rational expressions, equations, linear equations and systems of linear equations, inequalities, relations and functions, quadratic equations, equations of higher order, ratios, proportions, and variations. Take the Super Review quizzes to see how much y

  14. Algebraic Topology, Rational Homotopy

    CERN Document Server

    1988-01-01

    This proceedings volume centers on new developments in rational homotopy and on their influence on algebra and algebraic topology. Most of the papers are original research papers dealing with rational homotopy and tame homotopy, cyclic homology, Moore conjectures on the exponents of the homotopy groups of a finite CW-c-complex and homology of loop spaces. Of particular interest for specialists are papers on construction of the minimal model in tame theory and computation of the Lusternik-Schnirelmann category by means articles on Moore conjectures, on tame homotopy and on the properties of Poincaré series of loop spaces.

  15. Partially ordered algebraic systems

    CERN Document Server

    Fuchs, Laszlo

    2011-01-01

    Originally published in an important series of books on pure and applied mathematics, this monograph by a distinguished mathematician explores a high-level area in algebra. It constitutes the first systematic summary of research concerning partially ordered groups, semigroups, rings, and fields. The self-contained treatment features numerous problems, complete proofs, a detailed bibliography, and indexes. It presumes some knowledge of abstract algebra, providing necessary background and references where appropriate. This inexpensive edition of a hard-to-find systematic survey will fill a gap i

  16. Algebraic number theory

    CERN Document Server

    Weiss, Edwin

    1998-01-01

    Careful organization and clear, detailed proofs characterize this methodical, self-contained exposition of basic results of classical algebraic number theory from a relatively modem point of view. This volume presents most of the number-theoretic prerequisites for a study of either class field theory (as formulated by Artin and Tate) or the contemporary treatment of analytical questions (as found, for example, in Tate's thesis).Although concerned exclusively with algebraic number fields, this treatment features axiomatic formulations with a considerable range of applications. Modem abstract te

  17. Helmholtz algebraic solitons

    Energy Technology Data Exchange (ETDEWEB)

    Christian, J M; McDonald, G S [Joule Physics Laboratory, School of Computing, Science and Engineering, Materials and Physics Research Centre, University of Salford, Salford M5 4WT (United Kingdom); Chamorro-Posada, P, E-mail: j.christian@salford.ac.u [Departamento de Teoria de la Senal y Comunicaciones e Ingenieria Telematica, Universidad de Valladolid, ETSI Telecomunicacion, Campus Miguel Delibes s/n, 47011 Valladolid (Spain)

    2010-02-26

    We report, to the best of our knowledge, the first exact analytical algebraic solitons of a generalized cubic-quintic Helmholtz equation. This class of governing equation plays a key role in photonics modelling, allowing a full description of the propagation and interaction of broad scalar beams. New conservation laws are presented, and the recovery of paraxial results is discussed in detail. The stability properties of the new solitons are investigated by combining semi-analytical methods and computer simulations. In particular, new general stability regimes are reported for algebraic bright solitons.

  18. Elementary matrix algebra

    CERN Document Server

    Hohn, Franz E

    2012-01-01

    This complete and coherent exposition, complemented by numerous illustrative examples, offers readers a text that can teach by itself. Fully rigorous in its treatment, it offers a mathematically sound sequencing of topics. The work starts with the most basic laws of matrix algebra and progresses to the sweep-out process for obtaining the complete solution of any given system of linear equations - homogeneous or nonhomogeneous - and the role of matrix algebra in the presentation of useful geometric ideas, techniques, and terminology.Other subjects include the complete treatment of the structur

  19. Endomorphisms of graph algebras

    DEFF Research Database (Denmark)

    Conti, Roberto; Hong, Jeong Hee; Szymanski, Wojciech

    2012-01-01

    We initiate a systematic investigation of endomorphisms of graph C*-algebras C*(E), extending several known results on endomorphisms of the Cuntz algebras O_n. Most but not all of this study is focused on endomorphisms which permute the vertex projections and globally preserve the diagonal MASA D...... that the restriction to the diagonal MASA of an automorphism which globally preserves both D_E and the core AF-subalgebra eventually commutes with the corresponding one-sided shift. Secondly, we exhibit several properties of proper endomorphisms, investigate invertibility of localized endomorphisms both on C...

  20. Algebra & trigonometry I essentials

    CERN Document Server

    REA, Editors of

    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. Algebra & Trigonometry I includes sets and set operations, number systems and fundamental algebraic laws and operations, exponents and radicals, polynomials and rational expressions, eq