WorldWideScience

Sample records for boolean algebra

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

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

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

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

  5. Generalized join-hemimorphisms on Boolean algebras

    OpenAIRE

    Sergio Celani

    2003-01-01

    We introduce the notions of generalized join-hemimorphism and generalized Boolean relation as an extension of the notions of join-hemimorphism and Boolean relation, respectively. We prove a duality between these two notions. We will also define a generalization of the notion of Boolean algebra with operators by considering a finite family of Boolean algebras endowed with a generalized join-hemimorphism. Finally, we define suitable notions of subalgebra, congruences, Boole...

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

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

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

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

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

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

  12. 布尔代数的软商布尔代数%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.%定义了布尔代数的软合同关系、软商代数和软商布尔代数等概念,证明了布尔代数的软合同关系与软理想相互确定,进而由布尔代数的软真理想得到布尔代数的软商布尔代数。最后,证明了布尔代数的软同态具有保软合同性。

  13. On the Prime Whales of a Boolean Algebra

    OpenAIRE

    Holland, Jason

    2013-01-01

    In this note, we introduce objects called prime whales and use them to represent a Boolean algebra as an algebra of sets in a way that is analogous to Stone's Representation Theorem. We also characterize the existence of prime whales in terms of the existence of prime ideals.

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

  15. On atomicity of free algebras in Boolean algebras with operators, and a new result on Pinter's free algebras

    OpenAIRE

    Ahmed, Tarek Sayed

    2013-01-01

    We give some general theorems on free algebras of varieties of Boolean algebras with operators; a hitherto new result is obtained for Pinter's substitution algebras. For n\\geq 3, and m>1, there is a generating set of the free algebra freely generated by m elements, which is not a free set of generators.

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

  17. A complexity theory based on Boolean algebra

    DEFF Research Database (Denmark)

    Skyum, Sven; Valiant, Leslie

    1985-01-01

    A projection of a Boolean function is a function obtained by substituting for each of its variables a variable, the negation of a variable, or a constant. Reducibilities among computational problems under this relation of projection are considered. It is shown that much of what is of everyday rel...

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

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

  20. Reduction of Database Independence to Dividing in Atomless Boolean Algebras

    OpenAIRE

    Hyttinen, Tapani; Paolini, Gianluca

    2014-01-01

    We prove that the form of conditional independence at play in database theory and independence logic is reducible to the first-order dividing calculus in the theory of atomless Boolean algebras. This establishes interesting connections between independence in database theory and stochastic independence. As indeed, in light of the aforementioned reduction and recent work of Ben-Yaacov [4], the former case of independence can be seen as the discrete version of the latter.

  1. Disjunctive normal forms for any class of Boolean algebras with operators

    OpenAIRE

    Khaled, Mohamed

    2015-01-01

    Disjunctive normal forms can provide elegant and constructive proofs of many standard results such as completeness, decidability and so on. They were also used to show non atomicity of some free algebras of specific Boolean algebras with operators. Here, we generalize the normal forms for any class of Boolean algebras with operators.

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

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

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

  5. Boolean Functions, Quantum Gates, Hamilton Operators, Spin Systems and Computer Algebra

    OpenAIRE

    Hardy, Yorick; Steeb, Willi-Hans

    2014-01-01

    We describe the construction of quantum gates (unitary operators) from boolean functions and give a number of applications. Both non-reversible and reversible boolean functions are considered. The construction of the Hamilton operator for a quantum gate is also described with the Hamilton operator expressed as spin system. Computer algebra implementations are provided.

  6. Constructing Rotation Symmetric Boolean Functions with Maximum Algebraic Immunity on an Odd Number of Variables

    Science.gov (United States)

    Peng, Jie; Kan, Haibin

    It is well known that Boolean functions used in stream and block ciphers should have high algebraic immunity to resist algebraic attacks. Up to now, there have been many constructions of Boolean functions achieving the maximum algebraic immunity. In this paper, we present several constructions of rotation symmetric Boolean functions with maximum algebraic immunity on an odd number of variables which are not symmetric, via a study of invertible cyclic matrices over the binary field. In particular, we generalize the existing results and introduce a new method to construct all the rotation symmetric Boolean functions that differ from the majority function on two orbits. Moreover, we prove that their nonlinearities are upper bounded by 2^{n-1}-\\binom{n-1}{\\lfloor\\frac{n}{2}\\rfloor}+2(n-6).

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

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

  9. A Boolean algebra approach to the construction of snarks

    OpenAIRE

    Fiol Mora, Miquel Àngel

    1991-01-01

    This work deals with the construction of snarks, that is, cubic graphs that cannot be 3-edge-colored. A natural generalization of the concept of "color", that describes in a simple way the coloring ("0" or "1") of any set of (semi)edges, is introduced. This approach allows us to apply the Boolean logic theory to find an ample family of snarks, which includes many of the previous known constructions and also some interesting ones. Peer Reviewed

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

  11. Ω-fuzzy subalgebra of Boolean algebra%布尔代数的Ω-模糊子代数

    Institute of Scientific and Technical Information of China (English)

    刘卫锋

    2013-01-01

    Ω-fuzzy subalgebra of Boolean algebra and its properties were discussed in this paper .Ω-fuzzy subalgebra of Boolean algebra was defined and two judging theorems of Ω-fuzzy subalgebra of Boolean algebra were given , and it was stated that intersection-images and inverse-images under Boolean algebra homomorphism of Ω-fuzzy subalgebra of Boolean algebra were respectively Ω-fuzzy subalgebra of Boolean algebra . Then , by defining three operations ⊕ ,ⓧ , over RΩ where RΩexpressed all mappings from set Ωto Boolean algebra R ,a Boolean algebra was obtained ,and fuzzy subalgebra and Ω-fuzzy subalgebra about RΩwere researched .%  研究布尔代数的Ω-模糊子代数及其性质。定义布尔代数的Ω-模糊子代数,给出布尔代数的Ω-模糊子代数的两个简化判定定理,并证明布尔代数的Ω-模糊子代数的交、同态像和同态逆像等也是布尔代数的Ω-模糊子代数。然后,令RΩ表示集合Ω到布尔代数R的所有映射的集合,通过在 RΩ上定义3种运算磑,磗,,得到布尔代数枙RΩ,磑,磗,, I0,I1枛,并研究与其相关的模糊子代数和Ω-模糊子代数。

  12. Boolean Differential Operators

    OpenAIRE

    Catumba, Jorge; Diaz, Rafael

    2012-01-01

    We consider four combinatorial interpretations for the algebra of Boolean differential operators. We show that each interpretation yields an explicit matrix representation for Boolean differential operators.

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

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

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

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

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

  18. Boole代数上的几个新度量结构%Several New Metric Structures on Boolean Algebra

    Institute of Scientific and Technical Information of China (English)

    左卫兵; 娄妍

    2011-01-01

    设B是Boole代数,Ω是B到Boole代数{0,1}的全体格同态,μ是Ω上的概率测度,基于B中元素的尺寸的概念提出了元素之间的几个伪度量,建立了B上的度量结构,研究了其上运算的连续性及相互关系.%Let B be a Boolean algebra and ft the set of all homomorphisms from B into {0,1}, and μ be a probability measure on Ω. Based on the concept of sizes of elements of B several new metrics on the pairs of elements are introduced, and the metric structures on B are established, finally, the propositions of continuity of the operations on B are studied.

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

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

  1. Algebraic Degree of a Class Boolean Function Annihilators%一类布尔函数零化子的代数次数

    Institute of Scientific and Technical Information of China (English)

    祁传达; 俞迎达

    2012-01-01

    The effectiveness of algebraic attacks of stream ciphers depends on the algebraic degrees of annihilators of nonlinear Boolean functions.But it remains a difficult problem to construct annihilators with low degree for a given Boolean function. In this paper, we give a new proof of a result on the existence of the n-k degree annihilators formulated by Zhang Wenying,et al,and correct an error in their original proof.%序列密码代数攻击的成效取决于所使用的非线性布尔函数零化子的代数次数,但如何构造一个给定函数的低次数零化子仍是一个难题.本文对张文英等人提出的关于一类布尔函数存在n-k次零化子的结论给出了新的证明,弥补了原文证明不严密的缺陷.

  2. 基于8种常用蕴涵算子上的模糊布尔代数%Fuzzy Boolean Algebras Based on Eight Familiar Kinds of Implication Operator

    Institute of Scientific and Technical Information of China (English)

    陈华新

    2012-01-01

    Based on the work of "Fuzzy Boolean Algebras Based on Implication Operator", present work gives eight kinds of equivalent forms of fuzzy Boolean algebras based on familiar eight kinds of implication operator by using inequalities characterizatian method. This paper promotes the results of the corresponding fuzzy algebra, and enriches riches theoretical results of fuzzy algebra.%在文献[1]的基础上,利用不等式的刻画方法,给出8种常用的R-蕴涵算子下的R-模糊布尔代数的8种等价形式,推广了现有相应模糊代数的结果,丰富了模糊代数的理论成果.

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

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

  5. 偶数变元代数免疫最优布尔函数的构造方法%Class of constructions of even variables boolean function with optimum algebraic immunity

    Institute of Scientific and Technical Information of China (English)

    陈银冬; 陆佩忠

    2009-01-01

    A second order recursive construction of even variables Boolean function with optimum algebraic immunity was proposed. It could be observed that the constructed Boolean functions have well cryptographic properties, such as good balance, high algebraic degree and high nonlinearity. Further more, it was generalized to a class of constructions for Boolean functions with optimum algebraic immunity.%提出了构造偶数变元代数免疫最优的布尔函数的方法,这是一个二阶的递归构造方法.分析表明,利用该方法构造而得到的布尔函数具有优良的密码学特性,比如具有较好的平衡性,较高的代数次数和非线性度等.最后,还对该构造方法进行了推广,进一步导出了递归构造偶数变元代数免疫最优布尔函数的一类方法.

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

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

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

  9. Boolean Logic Optimization in Majority-Inverter Graphs

    OpenAIRE

    Amarù, Luca; Gaillardon, Pierre-Emmanuel; De Micheli, Giovanni

    2015-01-01

    We present a Boolean logic optimization framework based on Majority-Inverter Graph (MIG). An MIG is a directed acyclic graph consisting of three-input majority nodes and regular/complemented edges. Current MIG optimization is supported by a consistent algebraic framework. However, when algebraic methods cannot improve a result quality, stronger Boolean methods are needed to attain further optimization. For this purpose, we propose MIG Boolean methods exploiting the error masking property of m...

  10. Algebraic Properties of Propositional Calculus

    OpenAIRE

    Schuh, Bernd R.

    2009-01-01

    In this short note we relate some known properties of propositional calculus to purely algebraic considerations of a Boolean algebra. Classes of formulas of propositional calculus are considered as elements of a Boolean algebra. As such they can be represented by uniquely defined elements of this algebra which we call "logical primes". The algebraic notations appear useful because they make it possible to derive well known properties of propositional calculus by simple calculations or to subs...

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

  12. A probabilistic logic system as a Boolean algebra homomorphic with set algebra%概率逻辑系统是与集合代数同态的布尔代数

    Institute of Scientific and Technical Information of China (English)

    刘宏岚; 郝卫东

    2011-01-01

    联结词的本质是命题的运算,只有对所有命题都适用的真值函数才能用于定义联结词.概率逻辑中由于命题的内涵相关性,任何[0,1]上的函数都不能完全适用于任意命题的运算,概率逻辑的联结词不能定义成真值函数.各种算子可以作为一种计算方法使用和研究,但不能代表一个逻辑系统研究系统的性质.概率逻辑系统是概率空间的逻辑表示,是与概率空间中的事件域(集合代数)同态的布尔代数.用事件域上的集合函数精确定义各种联结词,与经典二值逻辑相容,与事实相符,能够在经典逻辑框架内实现概率命题演算.%Connectives are essentially operations on propositions, and only the true value functions applicable to all propositions can be used to define connectives. In probabilistic logic, any function on [0,1 ] is not completely applicable for the operation on all propositions, and the connectives of probabilistic propositional logic cannot be defined as a true value function because of propositional relativity in connotation. Every operator may be discussed and employed as a method of calculation, but not as a logic system. A probabilistic propositional logic system is the logical description of a probabilistic space, and is a Boolean algebra homomorphic with set algebra that is the event domain in the probabilistic space. All connectives which are compatible with those in classical two-valued logic and which accord with fact can be defined exactly by set functions on event domains. The classical formal system of propositional calculus is completely applicable to probabilistic propositional calculus.

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

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

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

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

  17. Boolean Logic with Fault Tolerant Coding

    OpenAIRE

    Alagoz, B. Baykant

    2009-01-01

    Error detectable and error correctable coding in Hamming space was researched to discover possible fault tolerant coding constellations, which can implement Boolean logic with fault tolerant property. Basic logic operators of the Boolean algebra were developed to apply fault tolerant coding in the logic circuits. It was shown that application of three-bit fault tolerant codes have provided the digital system skill of auto-recovery without need for designing additional-fault tolerance mechanisms.

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

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

  20. Some Aspects of Boolean Valued Analysis

    OpenAIRE

    Kusraev, A. G.; Kutateladze, S. S.

    2015-01-01

    This is a survey of some recent applications of Boolean valued analysis to operator theory and harmonic analysis. Under consideration are pseudoembedding operators, the noncommutative Wickstead problem, the Radon-Nikodym Theorem for JB-algebras, and the Bochner Theorem for lattice-valued positive definite mappings on locally compact groups.

  1. Quantum boolean functions

    OpenAIRE

    Montanaro, Ashley; Osborne, Tobias J.

    2008-01-01

    In this paper we introduce the study of quantum boolean functions, which are unitary operators f whose square is the identity: f^2 = I. We describe several generalisations of well-known results in the theory of boolean functions, including quantum property testing; a quantum version of the Goldreich-Levin algorithm for finding the large Fourier coefficients of boolean functions; and two quantum versions of a theorem of Friedgut, Kalai and Naor on the Fourier spectra of boolean functions. In o...

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

  3. Integrating Boolean and Mathematical Solving: Foundations, Basic Algorithms and Requirements

    OpenAIRE

    Audemard, Gilles; Bertoli, Piergiorgio; Cimatti, Alessandro; Kornilowicz, Artur; Sebastiani, Roberto

    2002-01-01

    In the last years we have witnessed an impressive advance in the efficiency of boolean solving techniques, which has brought large previously intractable problems at the reach of state-of-the-art solvers. Unfortunately, simple boolean expressions are not expressive enough for representing many real-world problems, which require handling also integer or real values and operators. On the other hand, mathematical solvers, like computer-algebra systems or constraint solvers, cannot handle efficie...

  4. Semigroups and computer algebra in algebraic structures

    Science.gov (United States)

    Bijev, G.

    2012-11-01

    Some concepts in semigroup theory can be interpreted in several algebraic structures. A generalization fA,B,fA,B(X) = A(X')B of the complement operator (') on Boolean matrices is made, where A and B denote any rectangular Boolean matrices. While (') is an isomorphism between Boolean semilattices, the generalized complement operator is homomorphism in the general case. The map fA,B and its general inverse (fA,B)+ have quite similar properties to those in the linear algebra and are useful for solving linear equations in Boolean matrix algebras. For binary relations on a finite set, necessary and sufficient conditions for the equation αξβ = γ to have a solution ξ are proved. A generalization of Green's equivalence relations in semigroups for rectangular matrices is proposed. Relationships between them and the Moore-Penrose inverses are investigated. It is shown how any generalized Green's H-class could be constructed by given its corresponding linear subspaces and converted into a group isomorphic to a linear group. Some information about using computer algebra methods concerning this paper is given.

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

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

  7. 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 pro...... standard BDD techniques this problem is infeasible. BEDs are useful in applications where the end-result as a reduced ordered BDD is small, for example for tautology checking...

  8. Proposition Algebra with Projective Limits

    CERN Document Server

    Bergstra, J A

    2008-01-01

    Sequential logic deviates from propositional logic by taking into account that atomic propositions yield different Boolean values at different times during the sequential evaluation of a single proposition. Reactive valuations capture this dynamics of a proposition's environment. This logic is phrased as an equationally specified algebra rather than in the form of proof rules. It is strictly more general than Boolean algebra to the extent that the classical connectives fail to be expressively complete in the sequential case. The proposition algebra PRA is developed in a fashion similar to the process algebra ACP and the program algebra PGA via an algebraic specification which has a meaningful initial algebra for which a range of courser congruences are considered important as well. In addition infinite objects (that is propositions, processes and programs respectively) are preferably dealt with by means of an inverse limit construction which allows the transfer of knowledge concerning finite objects to facts ...

  9. Reflexive Operator Algebras on Banach Spaces

    OpenAIRE

    Merlevède, Florence; Peligrad, Costel; Peligrad, Magda

    2012-01-01

    In this paper we study the reflexivity of a unital strongly closed algebra of operators with complemented invariant subspace lattice on a Banach space. We prove that if such an algebra contains a complete Boolean algebra of projections of finite uniform multiplicity and with the direct sum property, then it is reflexive, i.e. it contains every operator that leaves invariant every closed subspace in the invariant subspace lattice of the algebra. In particular, such algebras coincide with their...

  10. 广义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环的部分扩张,如上三角矩阵环.

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

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

  13. Fast Vertical Mining Using Boolean Algebra

    OpenAIRE

    Hosny M. Ibrahim; Marghny, M. H.; Noha M. A. Abdelaziz

    2015-01-01

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

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

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

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

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

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

  19. Boolean Expression Diagrams

    DEFF Research Database (Denmark)

    Andersen, Henrik Reif; Hulgaard, Henrik

    2002-01-01

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

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

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

  2. ON REDUCED SCALAR EQUATIONS FOR SYNCHRONOUS BOOLEAN NETWORKS

    Directory of Open Access Journals (Sweden)

    Ali Muhammad Ali Rushdi

    2013-01-01

    Full Text Available A total description of a synchronous Boolean network is typically achieved by a matrix recurrence relation. A simpler alternative is to use a scalar equation which is a possibly nonlinear equation that involves two or more instances of a single scalar variable and some Boolean operator(s. Further simplification is possible in terms of a linear reduced scalar equation which is the simplest two-term scalar equation that includes no Boolean operators and equates the value of a scalar variable at a latter instance t2 to its value at an earlier instance t1. This equation remains valid when the times t1 and t2 are both augmented by any integral multiple of the underlying time period. In other words, there are infinitely many versions of a reduced scalar equation, any of which is useful for deducing information about the cyclic behavior of the network. However, to obtain correct information about the transient behavior of the network, one must find the true reduced scalar equation for which instances t1 and t2 are minimal. This study investigates the nature, derivation and utilization of reduced scalar equations. It relies on Boolean-algebraic manipulations for the derivation of such equations and suggests that this derivation can be facilitated by seeking certain orthogonality relations among certain successive (albeit not necessarily consecutive instances of the same scalar variable. We demonstrate, contrary to previously published assumptions or assertions, that there is typically no common reduced scalar equation for all the scalar variables. Each variable usually satisfies its own distinct reduced scalar equation. We also demonstrate that the derivation of a reduced scalar equation is achieved not only by proving it but also by disproving an immediately preceding version of it when such a version might exist. We also demonstrate that, despite the useful insight supplied by the reduced scalar equations, they do not provide a total solution like the

  3. Reconstructing an atomic orthomodular lattice from the poset of its Boolean sublattices

    OpenAIRE

    Constantin, Carmen; Doering, Andreas

    2013-01-01

    We show that an atomic orthomodular lattice L can be reconstructed up to isomorphism from the poset B(L) of Boolean subalgebras of L. A motivation comes from quantum theory and the so-called topos approach, where one considers the poset of Boolean sublattices of L=P(H), the projection lattice of the algebra B(H) of bounded operators on Hilbert space.

  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. Computational complexity of Boolean functions

    Science.gov (United States)

    Korshunov, Aleksei D.

    2012-02-01

    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.

  6. Geometric Operators on Boolean Functions

    OpenAIRE

    Frisvad, Jeppe Revall; Falster, Peter

    2007-01-01

    In truth-functional propositional logic, any propositional formula represents a Boolean function (according to some valuation of the formula). We describe operators based on Decartes' concept of constructing coordinate systems, for translation of a propositional formula to the image of a Boolean function. With this image of a Boolean function corresponding to a propositional formula, we prove that the orthogonal projection operator leads to a theorem describing all rules of inference in propo...

  7. Quantum computation using geometric algebra

    Science.gov (United States)

    Matzke, Douglas James

    This dissertation reports that arbitrary Boolean logic equations and operators can be represented in geometric algebra as linear equations composed entirely of orthonormal vectors using only addition and multiplication Geometric algebra is a topologically based algebraic system that naturally incorporates the inner and anticommutative outer products into a real valued geometric product, yet does not rely on complex numbers or matrices. A series of custom tools was designed and built to simplify geometric algebra expressions into a standard sum of products form, and automate the anticommutative geometric product and operations. Using this infrastructure, quantum bits (qubits), quantum registers and EPR-bits (ebits) are expressed symmetrically as geometric algebra expressions. Many known quantum computing gates, measurement operators, and especially the Bell/magic operators are also expressed as geometric products. These results demonstrate that geometric algebra can naturally and faithfully represent the central concepts, objects, and operators necessary for quantum computing, and can facilitate the design and construction of quantum computing tools.

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

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

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

    DEFF Research Database (Denmark)

    Pasalic, Enes

    2006-01-01

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

  11. Symmetry in Boolean Satisfiability

    Directory of Open Access Journals (Sweden)

    Fadi A. Aloul

    2010-06-01

    Full Text Available This paper reviews recent approaches on how to accelerate Boolean Satisfiability (SAT search by exploiting symmetries in the problem space. SAT search algorithms traverse an exponentially large search space looking for an assignment that satisfies a set of constraints. The presence of symmetries in the search space induces equivalence classes on the set of truth assignments. The goal is to use symmetries to avoid traversing all assignments by constraining the search to visit a few representative assignments in each equivalence class. This can lead to a significant reduction in search runtime without affecting the completeness of the search.

  12. Boolean Orthogonalizing Combination Methods

    Directory of Open Access Journals (Sweden)

    Yavuz Can

    2015-05-01

    Full Text Available In this paper a new logical operation method called “ presented. It is used to calculate the difference, but also the complement of a function as well as the EXOR and EXNOR of two minterms respectively two ternary respectively two ternary-vector logical operation method called “orthogonal OR advantages of both methods are their results, which are already available form that has an essential advantage for continuing calculations. Since it applies, an orthogonal disjunctive normal form is equal to orthogonal antivalence normal form, subsequent Boolean differential calculus will be simplified.

  13. Geometric Operators on Boolean Functions

    DEFF Research Database (Denmark)

    Frisvad, Jeppe Revall; Falster, Peter

    In truth-functional propositional logic, any propositional formula represents a Boolean function (according to some valuation of the formula). We describe operators based on Decartes' concept of constructing coordinate systems, for translation of a propositional formula to the image of a Boolean...... function. With this image of a Boolean function corresponding to a propositional formula, we prove that the orthogonal projection operator leads to a theorem describing all rules of inference in propositional reasoning. In other words, we can capture all kinds of inference in propositional logic by means...... of a few geometric operators working on the images of Boolean functions. The operators we describe, arise from the niche area of array-based logic and have previously been tightly bound to an array-based representation of Boolean functions. We redefine the operators in an abstract form to make them...

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

  15. Polynomial threshold functions and Boolean threshold circuits

    DEFF Research Database (Denmark)

    Hansen, Kristoffer Arnsfelt; Podolskii, Vladimir V.

    2013-01-01

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

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

  17. Strengthening Effect Algebras in a Logical Perspective: Heyting-Wajsberg Algebras

    Science.gov (United States)

    Konig, Martinvaldo

    2014-10-01

    Heyting effect algebras are lattice-ordered pseudoboolean effect algebras endowed with a pseudocomplementation that maps on the center (i.e. Boolean elements). They are the algebraic counterpart of an extension of both Łukasiewicz many-valued logic and intuitionistic logic. We show that Heyting effect algebras are termwise equivalent to Heyting-Wajsberg algebras where the two different logical implications are defined as primitive operators. We prove this logic to be decidable, to be strongly complete and to have the deduction-detachment theorem.

  18. Techniques for solving Boolean equation systems

    OpenAIRE

    Keinänen, Misa

    2006-01-01

    Boolean equation systems are ordered sequences of Boolean equations decorated with least and greatest fixpoint operators. Boolean equation systems provide a useful framework for formal verification because various specification and verification problems, for instance, μ-calculus model checking can be represented as the problem of solving Boolean equation systems. The general problem of solving a Boolean equation system is a computationally hard task, and no polynomial time solution technique ...

  19. A Note on the Inversion Complexity of Boolean Functions in Boolean Formulas

    OpenAIRE

    Morizumi, Hiroki

    2008-01-01

    In this note, we consider the minimum number of NOT operators in a Boolean formula representing a Boolean function. In circuit complexity theory, the minimum number of NOT gates in a Boolean circuit computing a Boolean function $f$ is called the inversion complexity of $f$. In 1958, Markov determined the inversion complexity of every Boolean function and particularly proved that $\\lceil \\log_2(n+1) \\rceil$ NOT gates are sufficient to compute any Boolean function on $n$ variables. As far as we...

  20. Dependency in Cooperative Boolean Games

    OpenAIRE

    Sauro, Luigi; van der Torre, Leon; Villata, Serena

    2009-01-01

    Cooperative boolean games are coalitional games with both goals and costs associated to actions, and dependence networks for boolean games are a kind of social networks representing how the actions of other agents have an influence on the achievement of an agent’s goal. In this paper, we introduce two new types of dependence networks, called the abstract dependence network and the refined dependence network. Moreover, we show that the notion of stability is complete with respect to the soluti...

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

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

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

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

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

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

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

  8. Binary higher order neural networks for realizing Boolean functions.

    Science.gov (United States)

    Zhang, Chao; Yang, Jie; Wu, Wei

    2011-05-01

    In order to more efficiently realize Boolean functions by using neural networks, we propose a binary product-unit neural network (BPUNN) and a binary π-ς neural network (BPSNN). The network weights can be determined by one-step training. It is shown that the addition " σ," the multiplication " π," and two kinds of special weighting operations in BPUNN and BPSNN can implement the logical operators " ∨," " ∧," and " ¬" on Boolean algebra 〈Z(2),∨,∧,¬,0,1〉 (Z(2)={0,1}), respectively. The proposed two neural networks enjoy the following advantages over the existing networks: 1) for a complete truth table of N variables with both truth and false assignments, the corresponding Boolean function can be realized by accordingly choosing a BPUNN or a BPSNN such that at most 2(N-1) hidden nodes are needed, while O(2(N)), precisely 2(N) or at most 2(N), hidden nodes are needed by existing networks; 2) a new network BPUPS based on a collaboration of BPUNN and BPSNN can be defined to deal with incomplete truth tables, while the existing networks can only deal with complete truth tables; and 3) the values of the weights are all simply -1 or 1, while the weights of all the existing networks are real numbers. Supporting numerical experiments are provided as well. Finally, we present the risk bounds of BPUNN, BPSNN, and BPUPS, and then analyze their probably approximately correct learnability. PMID:21427020

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

  10. Using computer algebra and SMT solvers in algebraic biology

    Science.gov (United States)

    Pineda Osorio, Mateo

    2014-05-01

    Biologic processes are represented as Boolean networks, in a discrete time. The dynamics within these networks are approached with the help of SMT Solvers and the use of computer algebra. Software such as Maple and Z3 was used in this case. The number of stationary states for each network was calculated. The network studied here corresponds to the immune system under the effects of drastic mood changes. Mood is considered as a Boolean variable that affects the entire dynamics of the immune system, changing the Boolean satisfiability and the number of stationary states of the immune network. Results obtained show Z3's great potential as a SMT Solver. Some of these results were verified in Maple, even though it showed not to be as suitable for the problem approach. The solving code was constructed using Z3-Python and Z3-SMT-LiB. Results obtained are important in biology systems and are expected to help in the design of immune therapies. As a future line of research, more complex Boolean network representations of the immune system as well as the whole psychological apparatus are suggested.

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

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

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

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

  15. Algebraic geometry

    CERN Document Server

    Lefschetz, Solomon

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

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

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

  18. Boolean Reasoning with Graphs of Partitions

    OpenAIRE

    Goossens, Daniel

    2010-01-01

    version longue du papier court "A Dynamic Boolean Knowledge Base" accepté à ICTAI 2010. This paper presents an implemented architecture for easy learning, reorganizing and navigation into a Boolean knowledge base. As the base grows with new definitions and constraints, it is normalized by the closure of a completion operator. This normalization allows arbitrary formats for Boolean expressions. It ensures basic reasoning abilities and spontaneously organizes intermingled taxonomies of conce...

  19. Model Checking of Boolean Process Models

    OpenAIRE

    Schneider, Christoph; Wehler, Joachim

    2011-01-01

    In the field of Business Process Management formal models for the control flow of business processes have been designed since more than 15 years. Which methods are best suited to verify the bulk of these models? The first step is to select a formal language which fixes the semantics of the models. We adopt the language of Boolean systems as reference language for Boolean process models. Boolean systems form a simple subclass of coloured Petri nets. Their characteristics are low tokens to mode...

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

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

  3. Monomial algebras

    CERN Document Server

    Villarreal, Rafael

    2015-01-01

    The book stresses the interplay between several areas of pure and applied mathematics, emphasizing the central role of monomial algebras. It unifies the classical results of commutative algebra with central results and notions from graph theory, combinatorics, linear algebra, integer programming, and combinatorial optimization. The book introduces various methods to study monomial algebras and their presentation ideals, including Stanley-Reisner rings, subrings and blowup algebra-emphasizing square free quadratics, hypergraph clutters, and effective computational methods.

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

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

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

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

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

  9. Efficient Instantiation of Parameterised Boolean Equation Systems to Parity Games

    Directory of Open Access Journals (Sweden)

    Gijs Kant

    2012-10-01

    Full Text Available Parameterised Boolean Equation Systems (PBESs are sequences of Boolean fixed point equations with data variables, used for, e.g., verification of modal mu-calculus formulae for process algebraic specifications with data. Solving a PBES is usually done by instantiation to a Parity Game and then solving the game. Practical game solvers exist, but the instantiation step is the bottleneck. We enhance the instantiation in two steps. First, we transform the PBES to a Parameterised Parity Game (PPG, a PBES with each equation either conjunctive or disjunctive. Then we use LTSmin, that offers transition caching, efficient storage of states and both distributed and symbolic state space generation, for generating the game graph. To that end we define a language module for LTSmin, consisting of an encoding of variables with parameters into state vectors, a grouped transition relation and a dependency matrix to indicate the dependencies between parts of the state vector and transition groups. Benchmarks on some large case studies, show that the method speeds up the instantiation significantly and decreases memory usage drastically.

  10. An Algebra of Synchronous Scheduling Interfaces

    CERN Document Server

    Mendler, Michael

    2011-01-01

    In this paper we propose an algebra of synchronous scheduling interfaces which combines the expressiveness of Boolean algebra for logical and functional behaviour with the min-max-plus arithmetic for quantifying the non-functional aspects of synchronous interfaces. The interface theory arises from a realisability interpretation of intuitionistic modal logic (also known as Curry-Howard-Isomorphism or propositions-as-types principle). The resulting algebra of interface types aims to provide a general setting for specifying type-directed and compositional analyses of worst-case scheduling bounds. It covers synchronous control flow under concurrent, multi-processing or multi-threading execution and permits precise statements about exactness and coverage of the analyses supporting a variety of abstractions. The paper illustrates the expressiveness of the algebra by way of some examples taken from network flow problems, shortest-path, task scheduling and worst-case reaction times in synchronous programming.

  11. An Algebra of Synchronous Scheduling Interfaces

    Directory of Open Access Journals (Sweden)

    Michael Mendler

    2011-01-01

    Full Text Available In this paper we propose an algebra of synchronous scheduling interfaces which combines the expressiveness of Boolean algebra for logical and functional behaviour with the min-max-plus arithmetic for quantifying the non-functional aspects of synchronous interfaces. The interface theory arises from a realisability interpretation of intuitionistic modal logic (also known as Curry-Howard-Isomorphism or propositions-as-types principle. The resulting algebra of interface types aims to provide a general setting for specifying type-directed and compositional analyses of worst-case scheduling bounds. It covers synchronous control flow under concurrent, multi-processing or multi-threading execution and permits precise statements about exactness and coverage of the analyses supporting a variety of abstractions. The paper illustrates the expressiveness of the algebra by way of some examples taken from network flow problems, shortest-path, task scheduling and worst-case reaction times in synchronous programming.

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

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

  14. Supertropical algebra

    OpenAIRE

    Izhakian, Zur; Rowen, Louis

    2008-01-01

    We develop the algebraic polynomial theory for "supertropical algebra," as initiated earlier over the real numbers by the first author. The main innovation there was the introduction of "ghost elements," which also play the key role in our structure theory. Here, we work somewhat more generally over an ordered monoid, and develop a theory which contains the analogs of several basic theorems of classical commutative algebra. This structure enables one to develop a Zariski-type algebraic geomet...

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

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

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

  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. Densities of mixed volumes for Boolean models

    OpenAIRE

    Weil, Wolfgang

    2001-01-01

    In generalization of the well-known formulae for quermass densities of stationary and isotropic Boolean models, we prove corresponding results for densities of mixed volumes in the stationary situation and show how they can be used to determine the intensity of non-isotropic Boolean models Z in d-dimensional space for d = 2, 3, 4. We then consider non-stationary Boolean models and extend results of Fallert on quermass densities to densities of mixed volumes. In particular, we present explicit...

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

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

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

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

  4. Combinatorics of Boolean automata circuits dynamics

    OpenAIRE

    Demongeot, Jacques; Noual, Mathilde; Sené, Sylvain

    2012-01-01

    International audience In line with fields of theoretical computer science and biology that study Boolean automata networks to model regulation networks, we present some results concerning the dynamics of networks whose underlying structures are oriented cycles, that is, Boolean automata circuits. In the context of biological regulation, former studies have highlighted the importance of circuits on the asymptotic dynamical behaviour of the biological networks that contain them. Our work fo...

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

  7. 高阶布尔网络的结构%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代数形式的关系.

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

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

  10. The algebraic structure of the Onsager algebra

    OpenAIRE

    DATE, ETSURO; Roan, Shi-shyr

    2000-01-01

    We study the Lie algebra structure of the Onsager algebra from the ideal theoretic point of view. A structure theorem of ideals in the Onsager algebra is obtained with the connection to the finite-dimensional representations. We also discuss the solvable algebra aspect of the Onsager algebra through the formal Lie algebra theory.

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

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

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

  14. A finite alternation result for reversible boolean circuits

    OpenAIRE

    Selinger, Peter

    2016-01-01

    We say that a reversible boolean function on n bits has alternation depth d if it can be written as the sequential composition of d reversible boolean functions, each of which acts only on the top n-1 bits or on the bottom n-1 bits. We show that every reversible boolean function of n >= 4 bits has alternation depth 9.

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

  16. Algebraic models of deviant modal operators based on de Morgan and Kleene lattices

    OpenAIRE

    Cattaneo, G.; Ciucci, DE; Dubois, D.

    2011-01-01

    An algebraic model of a kind of modal extension of de Morgan logic is described under the name MDS5 algebra. The main properties of this algebra can be summarized as follows: (1) it is based on a de Morgan lattice, rather than a Boolean algebra; (2) a modal necessity operator that satisfies the axioms N, K, T, and 5 (and as a consequence also B and 4) of modal logic is introduced; it allows one to introduce a modal possibility by the usual combination of necessity operation and...

  17. Hom-Akivis algebras

    OpenAIRE

    Issa, A. Nourou

    2010-01-01

    Hom-Akivis algebras are introduced. The commutator-Hom-associator algebra of a non-Hom-associative algebra (i.e. a Hom-nonassociative 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. It is pointed out that a Hom-Akivis algebra associated to a Hom-alternative algebra is a Hom-M...

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

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

  20. Zonotopal algebra

    OpenAIRE

    Holtz, Olga; Ron, Amos

    2007-01-01

    A wealth of geometric and combinatorial properties of a given linear endomorphism $X$ of $\\R^N$ is captured in the study of its associated zonotope $Z(X)$, and, by duality, its associated hyperplane arrangement ${\\cal H}(X)$. This well-known line of study is particularly interesting in case $n\\eqbd\\rank X \\ll N$. We enhance this study to an algebraic level, and associate $X$ with three algebraic structures, referred herein as {\\it external, central, and internal.} Each algebraic structure is ...

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

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

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

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

  5. Algorithms for Boolean Function Query Properties

    OpenAIRE

    Aaronson, Scott

    2001-01-01

    We present new algorithms to compute fundamental properties of a Boolean function given in truth-table form. Specifically, we give an O(N^2.322 log N) algorithm for block sensitivity, an O(N^1.585 log N) algorithm for `tree decomposition,' and an O(N) algorithm for `quasisymmetry.' These algorithms are based on new insights into the structure of Boolean functions that may be of independent interest. We also give a subexponential-time algorithm for the space-bounded quantum query complexity of...

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

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

  8. Which multiplier algebras are $W^*$-algebras?

    OpenAIRE

    Akemann, Charles A.; Amini, Massoud; Asadi, Mohammad B.

    2013-01-01

    We consider the question of when the multiplier algebra $M(\\mathcal{A})$ of a $C^*$-algebra $\\mathcal{A}$ is a $ W^*$-algebra, and show that it holds for a stable $C^*$-algebra exactly when it is a $C^*$-algebra of compact operators. This implies that if for every Hilbert $C^*$-module $E$ over a $C^*$-algebra $\\mathcal{A}$, the algebra $B(E)$ of adjointable operators on $E$ is a $ W^*$-algebra, then $\\mathcal{A}$ is a $C^*$-algebra of compact operators. Also we show that a unital $C^*$-algebr...

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

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

  11. 布尔函数与形态算子关系的研究%On the Relationship between Boolean Function and Morphology Operator

    Institute of Scientific and Technical Information of China (English)

    段汕; 罗敬; 徐文; 贺兴

    2013-01-01

      以布尔代数理论和欧式空间中二值形态变换理论为基础,通过布尔函数引入一个结构化映射,对二值形态变换的基本运算(腐蚀、膨胀)进行了描述,探讨了布尔函数与形态变换的关系,以期为二值形态变换的扩展提供新的途径。%This paper presents binary morphological transformation ( corrosion and expansion) on the basis of the Boolean algebra theory and the theory of binary morphological transformation in Euclidean space, and introduces a structural mapping resting on Boolean function, then researches the relationship between Boolean function and morphological transformation, which will provide a new way for extending morphological transformation.

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

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

  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. Word Hopf algebras

    OpenAIRE

    Hazewinkel, Michiel

    2004-01-01

    Two important generalizations of the Hopf algebra of symmetric functions are the Hopf algebra of noncommutative symmetric functions and its graded dual the Hopf algebra of quasisymmetric functions. A common generalization of the latter is the selfdual Hopf algebra of permutations (MPR Hopf algebra). This latter Hopf algebra can be seen as a Hopf algebra of endomorphisms of a Hopf algebra. That turns out to be a fruitful way of looking at things and gives rise to wide ranging further generaliz...

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

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

  18. GOLDMAN ALGEBRA, OPERS AND THE SWAPPING ALGEBRA

    OpenAIRE

    Labourie, François

    2012-01-01

    We define a Poisson Algebra called the {\\em swapping algebra} using the intersection of curves in the disk. We interpret a subalgebra of the fraction algebra of the swapping algebra -- called the {\\em algebra of multifractions} -- as an algebra of functions on the space of cross ratios and thus as an algebra of functions on the Hitchin component as well as on the space of $\\mathsf{SL}_n(\\mathbb R)$-opers with trivial holonomy. We relate this Poisson algebra to the Atiyah--Bott--Goldman symple...

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

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

  1. Abstract algebra

    CERN Document Server

    Deskins, W E

    1996-01-01

    This excellent textbook provides undergraduates with an accessible introduction to the basic concepts of abstract algebra and to the analysis of abstract algebraic systems. These systems, which consist of sets of elements, operations, and relations among the elements, and prescriptive axioms, are abstractions and generalizations of various models which evolved from efforts to explain or discuss physical phenomena.In Chapter 1, the author discusses the essential ingredients of a mathematical system, and in the next four chapters covers the basic number systems, decompositions of integers, diop

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

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

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

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

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

  7. Efficient Analog Circuits for Boolean Satisfiability

    OpenAIRE

    Yin, Xunzhao; Sedighi, Behnam; Varga, Melinda; Ercsey-Ravasz, Maria; Toroczkai, Zoltan; Hu, Xiaobo Sharon

    2016-01-01

    Efficient solutions to NP-complete problems would significantly benefit both science and industry. However, such problems are intractable on digital computers based on the von Neumann architecture, thus creating the need for alternative solutions to tackle such problems. Recently, a deterministic, continuous-time dynamical system (CTDS) was proposed (Nature Physics, 7(12), 966 (2011)) to solve a representative NP-complete problem, Boolean Satisfiability (SAT). This solver shows polynomial ana...

  8. ON REDUCED SCALAR EQUATIONS FOR SYNCHRONOUS BOOLEAN NETWORKS

    OpenAIRE

    Ali Muhammad Ali Rushdi; Adnan Ahmad Alsogati

    2013-01-01

    A total description of a synchronous Boolean network is typically achieved by a matrix recurrence relation. A simpler alternative is to use a scalar equation which is a possibly nonlinear equation that involves two or more instances of a single scalar variable and some Boolean operator(s). Further simplification is possible in terms of a linear reduced scalar equation which is the simplest two-term scalar equation that includes no Boolean operators and equates the value of a scalar variable a...

  9. Using Boolean Constraint Propagation for Sub-clause Deduction

    OpenAIRE

    Darras, Sylvain; Dequen, Gilles; Devendeville, Laure; Mazure, Bertrand; Ostrowski, Richard; Sais, Lahkdar

    2005-01-01

    Boolean Constraint Propagation (BCP) is recognized as one of the most use- ful technique for efficient satisfiability checking. In this paper a new extension of the scope of boolean constraint propagation is proposed. It makes an original use of BCP to achieve further reduction of boolean formulas. Considering the impli- cation graph generated by the constraint propagation process as a resolution tree, sub-clauses from the original formula can be deduced. Then, we show how such extension can ...

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

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

  12. Clifford algebra, geometric algebra, and applications

    CERN Document Server

    Lundholm, Douglas

    2009-01-01

    These are lecture notes for a course on the theory of Clifford algebras, with special emphasis on their wide range of applications in mathematics and physics. Clifford algebra is introduced both through a conventional tensor algebra construction (then called geometric algebra) with geometric applications in mind, as well as in an algebraically more general form which is well suited for combinatorics, and for defining and understanding the numerous products and operations of the algebra. The various applications presented include vector space and projective geometry, orthogonal maps and spinors, normed division algebras, as well as simplicial complexes and graph theory.

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

  14. The Onsager Algebra

    OpenAIRE

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

  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. Exotic Elliptic Algebras

    OpenAIRE

    Chirvasitu, Alex; Smith, S. Paul

    2015-01-01

    This paper examines a general method for producing twists of a comodule algebra by tensoring it with a torsor then taking co-invariants. We examine the properties that pass from the original algebra to the twisted algebra and vice versa. We then examine the special case where the algebra is a 4-dimensional Sklyanin algebra viewed as a comodule algebra over the Hopf algebra of functions on the non-cyclic group of order 4 with the torsor being the 2x2 matrix algebra. The twisted algebra is an "...

  17. Fibered F-Algebra

    OpenAIRE

    Kleyn, Aleks

    2007-01-01

    The concept of F-algebra and its representation can be extended to an arbitrary bundle. We define operations of fibered F-algebra in fiber. The paper presents the representation theory of of fibered F-algebra as well as a comparison of representation of F-algebra and of representation of fibered F-algebra.

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

  19. 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)…

  20. Towards Truly Boolean Arrays in Data-Parallel Array Processing

    NARCIS (Netherlands)

    C. Grelck; H. Luyat

    2013-01-01

    We investigate several dense bit-wise implementations of Boolean arrays in the context of the functional data-parallel array programming language SAC. A particular problem arises in compiler or directive based parallelisation as the scheduling of loops over Boolean arrays is unaware of the restricte

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

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

  3. Categorical Formulation of Finite-Dimensional Quantum Algebras

    Science.gov (United States)

    Vicary, Jamie

    2011-06-01

    We describe how †-Frobenius monoids give the correct categorical description of certain kinds of finite-dimensional `quantum algebras'. We develop the concept of an involution monoid, and use it to construct a correspondence between finite-dimensional C*-algebras and certain types of †-Frobenius monoids in the category of Hilbert spaces. Using this technology, we recast the spectral theorems for commutative C*-algebras and for normal operators into an explicitly categorical language, and we examine the case that the results of measurements do not form finite sets, but rather objects in a finite Boolean topos. We describe the relevance of these results for topological quantum field theory.

  4. Solvable quadratic Lie algebras

    Institute of Scientific and Technical Information of China (English)

    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.

  5. Graded cluster algebras

    OpenAIRE

    Grabowski, Jan

    2015-01-01

    In the cluster algebra literature, the notion of a graded cluster algebra has been implicit since the origin of the subject. In this work, we wish to bring this aspect of cluster algebra theory to the foreground and promote its study. We transfer a definition of Gekhtman, Shapiro and Vainshtein to the algebraic setting, yielding the notion of a multi-graded cluster algebra. We then study gradings for finite type cluster algebras without coefficients, giving a full classification. Translating ...

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

  7. On vertex Leibniz algebras

    OpenAIRE

    Li, Haisheng; Tan, Shaobin; Wang, Qing

    2012-01-01

    In this paper, we study a notion of what we call vertex Leibniz algebra. This notion naturally extends that of vertex algebra without vacuum, which was previously introduced by Huang and Lepowsky. We show that every vertex algebra without vacuum can be naturally extended to a vertex algebra. On the other hand, we show that a vertex Leibniz algebra can be embedded into a vertex algebra if and only if it admits a faithful module. To each vertex Leibniz algebra we associate a vertex algebra with...

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

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

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

  13. The Yoneda algebra of a K2 algebra need not be another K2 algebra

    OpenAIRE

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

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

  14. Ordered Boolean List (OBL): reducing the footprint for evaluating Boolean expressions.

    Science.gov (United States)

    Rossignac, Jaroslaw Jarek

    2011-09-01

    An Expanded Boolean Expression (EBE) does not contain any XOR or EQUAL operators. The occurrence of each variable is a different literal. We provide a linear time algorithm that converts an EBE of n literals into a logically equivalent Ordered Boolean List (OBL) and show how to use the OBL to evaluate the EBE in n steps and O(log log n) space, if the values of the literals are each read once in the order prescribed by the OBL. (An evaluation workspace of 5 bits suffices for all EBEs of up to six billion literals.) The primary application is the SIMD architecture, where the same EBE is evaluated in parallel for different input vectors when rendering solid models on the GPU directly from their Constructive Solid Geometry (CSG) representation. We compare OBL to the Reduced Ordered Binary Decision Diagram (ROBDD) and suggest possible applications of OBL to logic verification and to circuit design. PMID:21737862

  15. Enveloping algebras of some quantum Lie algebras

    OpenAIRE

    Pourkia, Arash

    2014-01-01

    We define a family of Hopf algebra objects, $H$, in the braided category of $\\mathbb{Z}_n$-modules (known as anyonic vector spaces), for which the property $\\psi^2_{H\\otimes H}=id_{H\\otimes H}$ holds. We will show that these anyonic Hopf algebras are, in fact, the enveloping (Hopf) algebras of particular quantum Lie algebras, also with the property $\\psi^2=id$. Then we compute the braided periodic Hopf cyclic cohomology of these Hopf algebras. For that, we will show the following fact: analog...

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

  17. Novikov-Jordan algebras

    OpenAIRE

    Dzhumadil'daev, A. S.

    2002-01-01

    Algebras with identity $(a\\star b)\\star (c\\star d) -(a\\star d)\\star(c\\star b)$ $=(a,b,c)\\star d-(a,d,c)\\star b$ are studied. Novikov algebras under Jordan multiplication and Leibniz dual algebras satisfy this identity. If algebra with such identity has unit, then it is associative and commutative.

  18. Historical Topics in Algebra.

    Science.gov (United States)

    National Council of Teachers of Mathematics, Inc., Reston, VA.

    This is a reprint of the historical capsules dealing with algebra from the 31st Yearbook of NCTM,"Historical Topics for the Mathematics Classroom." Included are such themes as the change from a geometric to an algebraic solution of problems, the development of algebraic symbolism, the algebraic contributions of different countries, the origin and…

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

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

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

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

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

  4. Supercriticality for Annealed Approximations of Boolean Networks

    CERN Document Server

    Mountford, Thomas

    2010-01-01

    We consider a model proposed by Derrida and Pomeau (1986) and recently studied by Chatterjee and Durrett (2009); it is defined as an approximation to S. Kauffman's boolean networks (1969). The model starts with the choice of a random directed graph on $n$ vertices; each node has $r$ input nodes pointing at it. A discrete time threshold contact process is then considered on this graph: at each instant, each site has probability $q$ of choosing to receive input; if it does, and if at least one of its inputs were occupied by a $1$ at the previous instant, then it is labeled with a $1$; in all other cases, it is labeled with a $0$. $r$ and $q$ are kept fixed and $n$ is taken to infinity. Improving a result of Chatterjee and Durrett, we show that if $qr > 1$, then the time of persistence of the dynamics is exponential in $n$.

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

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

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

  8. Multiparameter Twisted Weyl Algebras

    OpenAIRE

    Futorny, Vyacheslav; Hartwig, Jonas T.

    2011-01-01

    We introduce a new family of twisted generalized Weyl algebras, called multiparameter twisted Weyl algebras, for which we parametrize all simple quotients of a certain kind. Both Jordan's simple localization of the multiparameter quantized Weyl algebra and Hayashi's q-analog of the Weyl algebra are special cases of this construction. We classify all simple weight modules over any multiparameter twisted Weyl algebra. Extending results by Benkart and Ondrus, we also describe all Whittaker pairs...

  9. 基于布尔语义的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ÎΔ

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

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

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

  13. Approximate Counting for Complex-Weighted Boolean Constraint Satisfaction Problems

    CERN Document Server

    Yamakami, Tomoyuki

    2010-01-01

    Constraint satisfaction problems (or CSPs) have been extensively studied in AI, database theory, graph theory, etc. From an approximation viewpoint, it has been important to approximate the total number of assignments that satisfy all given Boolean constraints. There is a trichotomy theorem for such approximate counting for (non-weighted) Boolean CSPs; namely, all such counting problems are neatly classified into three categories under polynomial-time approximation-preserving reductions [Dyer, Goldberg, and Jerrum, 2010]. We extend this result to approximate counting for complex-weighted Boolean CSPs, provided that all arity-1 constraints are freely available to use. This makes a significant progress in the quest for the approximation classification of all counting Boolean CSPs in the most general form. To deal with complex weights, we employ proof techniques along the line of solving Holant problems [Valiant, 2002, 2008]. Our result also gives an approximation version of the dichotomy theorem of the complexi...

  14. Automatic Ranked Output from Boolean Searches in SIRE

    Science.gov (United States)

    Noreault, Terry; And Others

    1977-01-01

    This study examined the effectiveness using an automatic algorithm to rank the results of Boolean searches of an inverted file design document retrieval system. Relevant documents were ranked significantly higher than nonrelevant documents on output lists. (Author/KP)

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

  16. Maps from the enveloping algebra of the positive Witt algebra to regular algebras

    OpenAIRE

    Sierra, Susan J.; Walton, Chelsea

    2015-01-01

    We construct homomorphisms from the universal enveloping algebra of the positive (part of the) Witt algebra to several different Artin-Schelter regular algebras, and determine their kernels and images. As a result, we produce elementary proofs that the universal enveloping algebras of the Virasoro algebra, the Witt algebra, and the positive Witt algebra are neither left nor right noetherian.

  17. On the number of attractors of Boolean automata circuits

    OpenAIRE

    Demongeot, Jacques; Noual, Mathilde; Sené, Sylvain

    2009-01-01

    In line with fields of theoretical computer science and biology that study Boolean automata networks often seen as models of regulation networks, we present some results concerning the dynamics of networks whose underlying interaction graphs are circuits, that is Boolean automata circuits. In the context of biological regulation, former studies have highlighted the importance of circuits on the asymptotic dynamical behaviour of the biological networks that contain them. Our work focuses on th...

  18. Enhancing Boolean networks with fuzzy operators and edge tuning

    OpenAIRE

    Poret, Arnaud; Monteiro Sousa, Claudio; Boissel, Jean-Pierre

    2014-01-01

    Quantitative modeling in systems biology can be difficult due to the scarcity of quantitative details about biological phenomenons, especially at the subcellular scale. An alternative to escape this difficulty is qualitative modeling since it requires few to no quantitative information. Among the qualitative modeling approaches, the Boolean network formalism is one of the most popular. However, Boolean models allow variables to be valued at only true or false, which can appear too simplistic ...

  19. IMS Algorithm for Learning Representations in Boolean Neural Networks

    OpenAIRE

    Biswas, Nripendra N; Murthy, TVMK; Chandrasekhar, M.

    1991-01-01

    A new algorithm for learning representations in Boolean neural networks, where the inputs and outputs are binary bits, is presented. The algorithm has become feasible because of a newly discovered theorem which states that any non-linearly separable Boolean function can be expressed as a convergent series of linearly separable functions connected by the logical OR (+) and the logical INHIBIT (-) operators. The formation of the series is carried out by many important properties exhibited by th...

  20. Inadmissible Class of Boolean Functions under Stuck-at Faults

    OpenAIRE

    Das, Debesh K.; Chowdhury, Debabani; Bhattacharya, Bhargab B; Sasao, Tsutomu

    2013-01-01

    Many underlying structural and functional factors that determine the fault behavior of a combinational network, are not yet fully understood. In this paper, we show that there exists a large class of Boolean functions, called root functions, which can never appear as faulty response in irredundant two-level circuits even when any arbitrary multiple stuck-at faults are injected. Conversely, we show that any other Boolean function can appear as a faulty response from an irredundant realization ...

  1. Boolean Equi-propagation for Optimized SAT Encoding

    CERN Document Server

    Metodi, Amit; Lagoon, Vitaly; Stuckey, Peter J

    2011-01-01

    We present an approach to propagation based solving, Boolean equi-propagation, where constraints are modelled as propagators of information about equalities between Boolean literals. Propagation based solving applies this information as a form of partial evaluation resulting in optimized SAT encodings. We demonstrate for a variety of benchmarks that our approach results in smaller CNF encodings and leads to speed-ups in solving times.

  2. Algebraic and relational models for a system based on a poset of two elements

    OpenAIRE

    Iturrioz, Luisa

    2014-01-01

    The aim of this paper is to present a very simple set of conditions, necessary for the management of knowledge of a poset $T$ of two agents, which are partially ordered by the capabilities available in the system. We build up a formal system and we elaborate suitable semantic models in order to derive information from the poset. The system is related to three-valued Heyting algebras with Boolean operators.

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

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

  5. Representations of twisted current algebras

    OpenAIRE

    Lau, Michael

    2013-01-01

    We use evaluation representations to give a complete classification of the finite-dimensional simple modules of twisted current algebras. This generalizes and unifies recent work on multiloop algebras, current algebras, equivariant map algebras, and twisted forms.

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

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

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

  9. Lie Algebra of Noncommutative Inhomogeneous Hopf Algebra

    OpenAIRE

    Lagraa, M.; Touhami, N.

    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.

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

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

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

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

  15. Group identities on the units of algebraic algebras with applications to restricted enveloping algebras

    OpenAIRE

    Jespers, Eric; Riley, David; Siciliano, Salvatore

    2007-01-01

    An algebra is called a GI-algebra if its group of units satisfies a group identity. We provide positive support for the following two open problems. 1. Does every algebraic GI-algebra satisfy a polynomial identity? 2. Is every algebraically generated GI-algebra locally finite?

  16. Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages

    CERN Document Server

    Glasser, Christian; Selivanov, Victor

    2008-01-01

    The purpose of this paper is to provide efficient algorithms that decide membership for classes of several Boolean hierarchies for which efficiency (or even decidability) were previously not known. We develop new forbidden-chain characterizations for the single levels of these hierarchies and obtain the following results: - The classes of the Boolean hierarchy over level $\\Sigma_1$ of the dot-depth hierarchy are decidable in $NL$ (previously only the decidability was known). The same remains true if predicates mod $d$ for fixed $d$ are allowed. - If modular predicates for arbitrary $d$ are allowed, then the classes of the Boolean hierarchy over level $\\Sigma_1$ are decidable. - For the restricted case of a two-letter alphabet, the classes of the Boolean hierarchy over level $\\Sigma_2$ of the Straubing-Th\\'erien hierarchy are decidable in $NL$. This is the first decidability result for this hierarchy. - The membership problems for all mentioned Boolean-hierarchy classes are logspace many-one hard for $NL$. - T...

  17. Second moment method for a family of boolean CSP

    CERN Document Server

    Boufkhad, Yacine

    2011-01-01

    The estimation of phase transitions in random boolean Constraint Satisfaction Problems (CSP) is based on two fundamental tools: the first and second moment methods. While the first moment method on the number of solutions permits to compute upper bounds on any boolean CSP, the second moment method used for computing lower bounds proves to be more tricky and in most cases gives only the trivial lower bound 0. In this paper, we define a subclass of boolean CSP covering the monotone versions of many known NP-Complete boolean CSPs. We give a method for computing non trivial lower bounds for any member of this subclass. This is achieved thanks to an application of the second moment method to some selected solutions called characteristic solutions that depend on the boolean CSP considered. We apply, as an example, this method to establish that the threshold r_{k} of monotone 1-in-k-SAT is \\log k/k\\leq r_{k}\\leq\\log^{2}k/k

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

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

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

  1. A Note on Z* algebras

    OpenAIRE

    Taghavi, Ali

    2013-01-01

    We study some properies of $Z^{*}$ algebras, thos C^* algebra which all positive elements are zero divisors. We show by means of an example that an extension of a Z* algebra by a Z* algebra is not necessarily Z* algebra. However we prove that an extension of a non Z* algebra by a non Z* algebra is again a Z^* algebra. As an application of our methods, we prove that evey compact subset of the positive cones of a C* algebra has an upper bound in the algebra.

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

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

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

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

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

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

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

  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. Optimal Computation of Symmetric Boolean Functions in Collocated Networks

    CERN Document Server

    Kowshik, Hemant

    2011-01-01

    We consider collocated wireless sensor networks, where each node has a Boolean measurement and the goal is to compute a given Boolean function of these measurements. We first consider the worst case setting and study optimal block computation strategies for computing symmetric Boolean functions. We study three classes of functions: threshold functions, delta functions and interval functions. We provide exactly optimal strategies for the first two classes, and a scaling law order-optimal strategy with optimal preconstant for interval functions. We also extend the results to the case of integer measurements and certain integer-valued functions. We use lower bounds from communication complexity theory, and provide an achievable scheme using information theoretic tools. Next, we consider the case where nodes measurements are random and drawn from independent Bernoulli distributions. We address the problem of optimal function computation so as to minimize the expected total number of bits that are transmitted. In ...

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

  12. On Derivations Of Genetic Algebras

    International Nuclear Information System (INIS)

    A genetic algebra is a (possibly non-associative) algebra used to model inheritance in genetics. In application of genetics this algebra often has a basis corresponding to genetically different gametes, and the structure constant of the algebra encode the probabilities of producing offspring of various types. In this paper, we find the connection between the genetic algebras and evolution algebras. Moreover, we prove the existence of nontrivial derivations of genetic algebras in dimension two

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

  14. Experimental Comparison of Schemes for Interpreting Boolean Queries

    OpenAIRE

    Lee, Whay C.; Edward A Fox

    1988-01-01

    The standard interpretation of the logical operators in a Boolean retrieval system is in general too strict. A standard Boolean query rarely comes close to retrieving all and only those documents which are relevant to the user. An AND query is often too narrow and an OR query is often too broad. The choice of the AND results in retrieving on the left end of a typical average recall-precision graph, while the choice of the OR results in retrieving on the right end, implying a tradeoff between ...

  15. Some Properties of Inclusions of Multisets and Contractive Boolean Operators

    OpenAIRE

    Hyvernat, Pierre

    2011-01-01

    10 pages, including appendix Consider the following curious puzzle: call an n-tuple X=(X_1, ..., X_n) of sets smaller than another n-tuple Y if it has fewer //unordered sections//. We show that equivalence classes for this preorder are very easy to describe and characterize the preorder in terms of the simpler pointwise inclusion and the existence of a special increasing boolean operator f:B^n -> B^n. We also show that contrary to increasing boolean operators, the relevant operators are no...

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

  17. A Boolean Approach to Airline Business Model Innovation

    DEFF Research Database (Denmark)

    Hvass, Kristian Anders

    Research in business model innovation has identified its significance in creating a sustainable competitive advantage for a firm, yet there are few empirical studies identifying which combination of business model activities lead to success and therefore deserve innovative attention. This study...... analyzes the business models of North America low-cost carriers from 2001 to 2010 using a Boolean minimization algorithm to identify which combinations of business model activities lead to operational profitability. The research aim is threefold: complement airline literature in the realm of business model...... innovation, introduce Boolean minimization methods to the field, and propose alternative business model activities to North American carriers striving for positive operating results....

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

  19. Stable endomorphism algebras of modules over special biserial algebras

    OpenAIRE

    Schröer, Jan; Zimmermann, Alexander

    2002-01-01

    We prove that the stable endomorphism algebra of a module without self-extensions over a special biserial algebra is a gentle algebra. In particular, it is again special biserial. As a consequence, any algebra which is derived equivalent to a gentle algebra is gentle.

  20. $L_{\\infty}$ algebra structures of Lie algebra deformations

    OpenAIRE

    Gao, Jining

    2004-01-01

    In this paper,we will show how to kill the obstructions to Lie algebra deformations via a method which essentially embeds a Lie algebra into Strong homotopy Lie algebra or $L_{\\infty}$ algebra. All such obstructions have been transfered to the revelvant $L_{\\infty}$ algebras which contain only three terms

  1. Omni-Lie Color Algebras and Lie Color 2-Algebras

    OpenAIRE

    Zhang, Tao

    2013-01-01

    Omni-Lie color algebras over an abelian group with a bicharacter are studied. The notions of 2-term color $L_{\\infty}$-algebras and Lie color 2-algebras are introduced. It is proved that there is a one-to-one correspondence between Lie color 2-algebras and 2-term color $L_{\\infty}$-algebras.

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

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

    Institute of Scientific and Technical Information of China (English)

    潘芳芳; 王顺钦

    2008-01-01

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

  4. 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′闭,则δ是连续的和内的.

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

  6. Generalized Flip-Flop Input Equations Based on a Four-Valued Boolean Algebra

    Science.gov (United States)

    Tucker, Jerry H.; Tapia, Moiez A.

    1996-01-01

    A procedure is developed for obtaining generalized flip-flop input equations, and a concise method is presented for representing these equations. The procedure is based on solving a four-valued characteristic equation of the flip-flop, and can encompass flip-flops that are too complex to approach intuitively. The technique is presented using Karnaugh maps, but could easily be implemented in software.

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

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

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

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

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

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

  13. A quantum field algebra

    OpenAIRE

    Brouder, Christian

    2002-01-01

    The Laplace Hopf algebra created by Rota and coll. is generalized to provide an algebraic tool for combinatorial problems of quantum field theory. This framework encompasses commutation relations, normal products, time-ordered products and renormalisation. It considers the operator product and the time-ordered product as deformations of the normal product. In particular, it gives an algebraic meaning to Wick's theorem and it extends the concept of Laplace pairing to prove that the renormalise...

  14. Algebraic nonlinear collective motion

    OpenAIRE

    Troupe, J.; Rosensteel, G.

    1999-01-01

    Finite-dimensional Lie algebras of vector fields determine geometrical collective models in quantum and classical physics. Every set of vector fields on Euclidean space that generates the Lie algebra sl(3, R) and contains the angular momentum algebra so(3) is determined. The subset of divergence-free sl(3, R) vector fields is proven to be indexed by a real number $\\Lambda$. The $\\Lambda=0$ solution is the linear representation that corresponds to the Riemann ellipsoidal model. The nonlinear g...

  15. Geometric Algebras and Extensors

    OpenAIRE

    Fernandez, V. V.; Moya, A. M.; Rodrigues Jr., W. A.

    2007-01-01

    This is the first paper in a series (of four) designed to show how to use geometric algebras of multivectors and extensors to a novel presentation of some topics of differential geometry which are important for a deeper understanding of geometrical theories of the gravitational field. In this first paper we introduce the key algebraic tools for the development of our program, namely the euclidean geometrical algebra of multivectors Cl(V,G_{E}) and the theory of its deformations leading to met...

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

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

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

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

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

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

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

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

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

  5. Graphical interpretation of Boolean operators for protein NMR assignments

    NARCIS (Netherlands)

    Verdegem, Dries; Dijkstra, Klaas; Hanoulle, Xavier; Lippens, Guy

    2008-01-01

    We have developed a graphics based algorithm for semi-automated protein NMR assignments. Using the basic sequential triple resonance assignment strategy, the method is inspired by the Boolean operators as it applies "AND"-, "OR"- and "NOT"-like operations on planes pulled out of the classical three-

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

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

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

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

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

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

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

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

  14. Universal Algebras of Hurwitz Numbers

    OpenAIRE

    A. Mironov; Morozov, A; Natanzon, S.

    2009-01-01

    Infinite-dimensional universal Cardy-Frobenius algebra is constructed, which unifies all particular algebras of closed and open Hurwitz numbers and is closely related to the algebra of differential operators, familiar from the theory of Generalized Kontsevich Model.

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

  16. A novel Lie algebra of the genetic code over the Galois field of four DNA bases.

    Science.gov (United States)

    Sánchez, Robersy; Grau, Ricardo; Morgado, Eberto

    2006-07-01

    Starting from the four DNA bases order in the Boolean lattice, a novel Lie Algebra of the genetic code is proposed. Here, the main partitions of the genetic code table were obtained as equivalent classes of quotient spaces of the genetic code vector space over the Galois field of the four DNA bases. The new algebraic structure shows strong connections among algebraic relationships, codon assignments and physicochemical properties of amino acids. Moreover, a distance defined between codons expresses a physicochemical meaning. It was also noticed that the distance between wild type and mutant codons tends to be small in mutational variants of four genes: human phenylalanine hydroxylase, human beta-globin, HIV-1 protease and HIV-1 reverse transcriptase. These results strongly suggest that deterministic rules in genetic code origin must be involved. PMID:16780898

  17. (Quasi-)Poisson enveloping algebras

    OpenAIRE

    Yang, Yan-Hong; Yuan YAO; Ye, Yu

    2010-01-01

    We introduce the quasi-Poisson enveloping algebra and Poisson enveloping algebra for a non-commutative Poisson algebra. We prove that for a non-commutative Poisson algebra, the category of quasi-Poisson modules is equivalent to the category of left modules over its quasi-Poisson enveloping algebra, and the category of Poisson modules is equivalent to the category of left modules over its Poisson enveloping algebra.

  18. On algebraic volume density property

    OpenAIRE

    Kaliman, Shulim; Kutzschebauch, Frank

    2012-01-01

    A smooth affine algebraic variety $X$ equipped with an algebraic volume form $\\omega$ has the algebraic volume density property (AVDP) if the Lie algebra generated by completely integrable algebraic vector fields of $\\omega$-divergence zero coincides with the space of all algebraic vector fields of $\\omega$-divergence zero. We develop an effective criterion of verifying whether a given $X$ has AVDP. As an application of this method we establish AVDP for any homogeneous space $X=G/R$ that admi...

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

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

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

    Science.gov (United States)

    Varga, Melinda; Sumi, Robert; Ercsey-Ravasz, Maria; Toroczkai, Zoltan

    Transient chaos is a phenomenon characterizing the dynamics of phase space trajectories evolving towards an attractor in physical systems. We show that transient chaos also appears in the dynamics of certain algorithms searching for solutions of constraint satisfaction problems (e.g., Sudoku). We present a study of the emergence of hardness in Boolean satisfiability (k-SAT) using an analog deterministic algorithm. Problem hardness is defined through the escape rate κ, an invariant measure of transient chaos, and it expresses the rate at which the trajectory approaches a solution. We show that the hardness 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 αc in the random 3-SAT ensemble where dynamical trajectories become transiently chaotic, however, such 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. We demonstrate that the transition is generated by the appearance of non-solution basins in the solution space as the density of constraints is increased.

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

  4. On Hadamard algebras

    Directory of Open Access Journals (Sweden)

    Carlos C. Peña

    2000-05-01

    Full Text Available Topological algebras of sequences of complex numbers are introduced, endowed with a Hadamard product type. The complex homomorphisms on these algebras are characterized, and units, prime cyclic ideals, prime closed ideals, and prime minimal ideals, discussed. Existence of closed and maximal ideals are investigated, and it is shown that the Jacobson and nilradicals are both trivial.

  5. Computer algebra in gravity

    CERN Document Server

    Heinicke, C; Heinicke, Christian; Hehl, Friedrich W.

    2001-01-01

    We survey the application of computer algebra in the context of gravitational theories. After some general remarks, we show of how to check the second Bianchi-identity by means of the Reduce package Excalc. Subsequently we list some computer algebra systems and packages relevant to applications in gravitational physics. We conclude by presenting a couple of typical examples.

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

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

  8. Deformation of central charges, vertex operator algebras whose Griess algebras are Jordan algebras

    OpenAIRE

    Ashihara, Takahiro; Miyamoto, Masahiko

    2008-01-01

    If a vertex operator algebra $V=\\oplus_{n=0}^{\\infty}V_n$ satisfies $\\dim V_0=1, V_1=0$, then $V_2$ has a commutative (nonassociative) algebra structure called Griess algebra. One of the typical examples of commutative (nonassociative) algebras is a Jordan algebra. For example, the set $Sym_d(\\C)$ of symmetric matrices of degree $d$ becomes a Jordan algebra. On the other hand, in the theory of vertex operator algebras, central charges influence the properties of vertex operator algebras. In t...

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

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

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

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

  13. Super Linear Algebra

    CERN Document Server

    Kandasamy, W B Vasantha

    2008-01-01

    In this book, the authors introduce the notion of Super linear algebra and super vector spaces using the definition of super matrices defined by Horst (1963). This book expects the readers to be well-versed in linear algebra. Many theorems on super linear algebra and its properties are proved. Some theorems are left as exercises for the reader. These new class of super linear algebras which can be thought of as a set of linear algebras, following a stipulated condition, will find applications in several fields using computers. The authors feel that such a paradigm shift is essential in this computerized world. Some other structures ought to replace linear algebras which are over a century old. Super linear algebras that use super matrices can store data not only in a block but in multiple blocks so it is certainly more powerful than the usual matrices. This book has 3 chapters. Chapter one introduces the notion of super vector spaces and enumerates a number of properties. Chapter two defines the notion of sup...

  14. 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. PMID:27464825

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

  16. Minimization of Boolean complexity in human concept learning.

    Science.gov (United States)

    Feldman, J

    2000-10-01

    One of the unsolved problems in the field of human concept learning concerns the factors that determine the subjective difficulty of concepts: why are some concepts psychologically simple and easy to learn, while others seem difficult, complex or incoherent? This question was much studied in the 1960s but was never answered, and more recent characterizations of concepts as prototypes rather than logical rules leave it unsolved. Here I investigate this question in the domain of Boolean concepts (categories defined by logical rules). A series of experiments measured the subjective difficulty of a wide range of logical varieties of concepts (41 mathematically distinct types in six families--a far wider range than has been tested previously). The data reveal a surprisingly simple empirical 'law': the subjective difficulty of a concept is directly proportional to its Boolean complexity (the length of the shortest logically equivalent propositional formula)--that is, to its logical incompressibility. PMID:11034211

  17. Tracking perturbations in Boolean networks with spectral methods.

    Science.gov (United States)

    Kesseli, Juha; Rämö, Pauli; Yli-Harja, Olli

    2005-08-01

    In this paper we present a method for predicting the spread of perturbations in Boolean networks. The method is applicable to networks that have no regular topology. The prediction of perturbations can be performed easily by using a presented result which enables the efficient computation of the required iterative formulas. This result is based on abstract Fourier transform of the functions in the network. In this paper the method is applied to show the spread of perturbations in networks containing a distribution of functions found from biological data. The advances in the study of the spread of perturbations can directly be applied to enable ways of quantifying chaos in Boolean networks. Derrida plots over an arbitrary number of time steps can be computed and thus distributions of functions compared with each other with respect to the amount of order they create in random networks. PMID:16196674

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

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

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

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

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

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

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

  5. Equational axioms of test algebra

    NARCIS (Netherlands)

    Hollenberg, M.

    2008-01-01

    We present a complete axiomatization of test algebra ([24,18,29]), the two-sorted algebraic variant of Propositional Dynamic Logic (PDL,[21,7]). The axiomatization consists of adding a finite number of equations to any axiomatization of Kleene algebra ([15,26,17,4]) and algebraic translations of the

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

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

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

    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.

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

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

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

  12. On Griess Algebras

    OpenAIRE

    Michael Roitman

    2003-01-01

    In this paper we prove that for any commutative (but in general non-associative) algebra $A$ with an invariant symmetric non-degenerate bilinear form there is a graded vertex algebra $V = V_0 \\oplus V_2 \\oplus V_3\\oplus ...$, such that $\\dim V_0 = 1$ and $V_2$ contains $A$. We can choose $V$ so that if $A$ has a unit $e$, then $2e$ is the Virasoro element of $V$, and if $G$ is a finite group of automorphisms of $A$, then $G$ acts on $V$ as well. In addition, the algebra $V$ can be chosen with...

  13. Worst-Case Groundness Analysis Using Definite Boolean Functions

    OpenAIRE

    Genaim, Samir; Codish, Michael; Howe, Jacob M.

    2004-01-01

    This note illustrates theoretical worst-case scenarios for groundness analyses obtained through abstract interpretation over the abstract domains of definite (Def) and positive (Pos) Boolean functions. For Def, an example is given for which any Def-based abstract interpretation for groundness analysis follows a chain which is exponential in the number of argument positions as well as in the number of clauses but sub-exponential in the size of the program. For Pos, we strengthen a previous res...

  14. Mapping Complex Networks: Exploring Boolean Modeling of Signal Transduction Pathways

    OpenAIRE

    Bhardwaj, Gaurav; Wells, Christine P.; Albert, Reka; van Rossum, Damian B.; Patterson, Randen L

    2009-01-01

    In this study, we explored the utility of a descriptive and predictive bionetwork model for phospholipase C-coupled calcium signaling pathways, built with non-kinetic experimental information. Boolean models generated from these data yield oscillatory activity patterns for both the endoplasmic reticulum resident inositol-1,4,5-trisphosphate receptor (IP3R) and the plasma-membrane resident canonical transient receptor potential channel 3 (TRPC3). These results are specific as randomization of ...

  15. Boolean Functions, Projection Operators and Quantum Error Correcting Codes

    OpenAIRE

    Aggarwal, Vaneet; Calderbank, A. Robert

    2006-01-01

    This paper describes a fundamental correspondence between Boolean functions and projection operators in Hilbert space. The correspondence is widely applicable, and it is used in this paper to provide a common mathematical framework for the design of both additive and non-additive quantum error correcting codes. The new framework leads to the construction of a variety of codes including an infinite class of codes that extend the original ((5,6,2)) code found by Rains [21]. It also extends to o...

  16. Matroids, hereditary collections and simplicial complexes having boolean representations

    OpenAIRE

    Rhodes, John; Silva, Pedro V.

    2012-01-01

    Inspired by the work of Izakhian and Rhodes, a theory of representation of hereditary collections by boolean matrices is developed. This corresponds to representation by finite $\\vee$-generated lattices. The lattice of flats, defined for hereditary collections, lattices and matrices, plays a central role in the theory. The representations constitute a lattice and the minimal and strictly join irreducible elements are studied, as well as various closure operators.

  17. Soft Rough Approximation Operators on a Complete Atomic Boolean Lattice

    OpenAIRE

    Heba I. Mustafa

    2013-01-01

    The concept of soft sets based on complete atomic Boolean lattice, which can be seen as a generalization of soft sets, is introduced. Some operations on these soft sets are discussed, and new types of soft sets such as full, keeping infimum, and keeping supremum are defined and supported by some illustrative examples. Two pairs of new soft rough approximation operators are proposed and the relationship among soft set is investigated, and their related properties are given. We show that Järvin...

  18. Yes/No/Maybe: A Boolean attempt at feedback

    OpenAIRE

    12130478 - Louw, Henk; 10095519 - Van Rooy, Albertus Jacobus

    2010-01-01

    This paper describes an experiment in which Boolean feedback (a kind of checklist) was used to provide feedback on the paragraph structures of first year students in an Academic Literacy course. We begin by introducing the major problems with feedback on L2 writing and establishing why a focus on paragraph structures in particular is of importance. The experiment conducted was a two-draft assignment in which three different kinds of feedback (technique A: handwritten comments, B: consciousnes...

  19. A Boolean Approach to Airline Business Model Innovation

    OpenAIRE

    Hvass, Kristian

    2012-01-01

    Research in business model innovation has identified its significance in creating a sustainable competitive advantage for a firm, yet there are few empirical studies identifying which combination of business model activities lead to success and therefore deserve innovative attention. This study analyzes the business models of North America low-cost carriers from 2001 to 2010 using a Boolean minimization algorithm to identify which combinations of business model activities le...

  20. Boolean logic device done with DFB laser diode

    OpenAIRE

    Hurtado Villavieja, Antonio; González Marcos, Ana; Martín Pereda, José Antonio

    2004-01-01

    We present simulation results on how power output-input characteristic Instability in Distributed FeedBack -DFB semiconductor laser diode SLA can be employed to implemented Boolean logic device. Two configurations of DFB Laser diode under external optical injection, either in the transmission or in the reflective mode of operation, is used to implement different Optical Logic Cells (OLCs), called the Q- and the P-Device OLCs. The external optical injection correspond to two inputs data plus a...

  1. Controllability and observability of Boolean networks arising from biology.

    Science.gov (United States)

    Li, Rui; Yang, Meng; Chu, Tianguang

    2015-02-01

    Boolean networks are currently receiving considerable attention as a computational scheme for system level analysis and modeling of biological systems. Studying control-related problems in Boolean networks may reveal new insights into the intrinsic control in complex biological systems and enable us to develop strategies for manipulating biological systems using exogenous inputs. This paper considers controllability and observability of Boolean biological networks. We propose a new approach, which draws from the rich theory of symbolic computation, to solve the problems. Consequently, simple necessary and sufficient conditions for reachability, controllability, and observability are obtained, and algorithmic tests for controllability and observability which are based on the Gröbner basis method are presented. As practical applications, we apply the proposed approach to several different biological systems, namely, the mammalian cell-cycle network, the T-cell activation network, the large granular lymphocyte survival signaling network, and the Drosophila segment polarity network, gaining novel insights into the control and/or monitoring of the specific biological systems.

  2. Approximating Attractors of Boolean Networks by Iterative CTL Model Checking.

    Science.gov (United States)

    Klarner, Hannes; Siebert, Heike

    2015-01-01

    This paper introduces the notion of approximating asynchronous attractors of Boolean networks by minimal trap spaces. We define three criteria for determining the quality of an approximation: "faithfulness" which requires that the oscillating variables of all attractors in a trap space correspond to their dimensions, "univocality" which requires that there is a unique attractor in each trap space, and "completeness" which requires that there are no attractors outside of a given set of trap spaces. Each is a reachability property for which we give equivalent model checking queries. Whereas faithfulness and univocality can be decided by model checking the corresponding subnetworks, the naive query for completeness must be evaluated on the full state space. Our main result is an alternative approach which is based on the iterative refinement of an initially poor approximation. The algorithm detects so-called autonomous sets in the interaction graph, variables that contain all their regulators, and considers their intersection and extension in order to perform model checking on the smallest possible state spaces. A benchmark, in which we apply the algorithm to 18 published Boolean networks, is given. In each case, the minimal trap spaces are faithful, univocal, and complete, which suggests that they are in general good approximations for the asymptotics of Boolean networks.

  3. Global Avalanche Characteristics of Boolean Functions by Concatenation

    Institute of Scientific and Technical Information of China (English)

    Mingsheng Ren

    2016-01-01

    In order to measure the correlation propeties of two Boolean functions, the global avalanche characteristics of Boolean functions constructed by concatenation are discussed, i.e., f1‖f2 and f1‖f2‖f3‖f4. Firstly, for the function f = f1‖f2 , the cross⁃correlation function of f1 , f2 in the special condition are studied. In this case, f, f1 , f2 must be in desired form. By computing their sum⁃of⁃squares indicators, the cross⁃correlation function between f1 , f2 is obtained. Secondly, for the function g = f1‖f2‖f3‖f4 , by analyzing the relation among their auto⁃correlation functions, their sum⁃of⁃squares indicators are investigated. Based on them, the sum⁃of⁃squares indicators of functions obtained by Canteaut et al. are investigated. The results show that the correlation property of g is good when the correlation properties of Boolean functions f1 , f2 , f3 , f4 are good.

  4. Boolean Models of Biological Processes Explain Cascade-Like Behavior.

    Science.gov (United States)

    Chen, Hao; Wang, Guanyu; Simha, Rahul; Du, Chenghang; Zeng, Chen

    2016-01-01

    Biological networks play a key role in determining biological function and therefore, an understanding of their structure and dynamics is of central interest in systems biology. In Boolean models of such networks, the status of each molecule is either "on" or "off" and along with the molecules interact with each other, their individual status changes from "on" to "off" or vice-versa and the system of molecules in the network collectively go through a sequence of changes in state. This sequence of changes is termed a biological process. In this paper, we examine the common perception that events in biomolecular networks occur sequentially, in a cascade-like manner, and ask whether this is likely to be an inherent property. In further investigations of the budding and fission yeast cell-cycle, we identify two generic dynamical rules. A Boolean system that complies with these rules will automatically have a certain robustness. By considering the biological requirements in robustness and designability, we show that those Boolean dynamical systems, compared to an arbitrary dynamical system, statistically present the characteristics of cascadeness and sequentiality, as observed in the budding and fission yeast cell- cycle. These results suggest that cascade-like behavior might be an intrinsic property of biological processes.

  5. MILES FORMULAE FOR BOOLEAN MODELS OBSERVED ON LATTICES

    Directory of Open Access Journals (Sweden)

    Joachim Ohser

    2011-05-01

    Full Text Available The densities of the intrinsic volumes – in 3D the volume density, surface density, the density of the integral of the mean curvature and the density of the Euler number – are a very useful collection of geometric characteristics of random sets. Combining integral and digital geometry we develop a method for efficient and simultaneous calculation of the intrinsic volumes of random sets observed in binary images in arbitrary dimensions. We consider isotropic and reflection invariant Boolean models sampled on homogeneous lattices and compute the expectations of the estimators of the intrinsic volumes. It turns out that the estimator for the surface density is proved to be asymptotically unbiased and thusmultigrid convergent for Boolean models with convex grains. The asymptotic bias of the estimators for the densities of the integral of the mean curvature and of the Euler number is assessed for Boolean models of balls of random diameters. Miles formulae with corresponding correction terms are derived for the 3D case.

  6. Boolean Models of Biological Processes Explain Cascade-Like Behavior.

    Science.gov (United States)

    Chen, Hao; Wang, Guanyu; Simha, Rahul; Du, Chenghang; Zeng, Chen

    2016-01-01

    Biological networks play a key role in determining biological function and therefore, an understanding of their structure and dynamics is of central interest in systems biology. In Boolean models of such networks, the status of each molecule is either "on" or "off" and along with the molecules interact with each other, their individual status changes from "on" to "off" or vice-versa and the system of molecules in the network collectively go through a sequence of changes in state. This sequence of changes is termed a biological process. In this paper, we examine the common perception that events in biomolecular networks occur sequentially, in a cascade-like manner, and ask whether this is likely to be an inherent property. In further investigations of the budding and fission yeast cell-cycle, we identify two generic dynamical rules. A Boolean system that complies with these rules will automatically have a certain robustness. By considering the biological requirements in robustness and designability, we show that those Boolean dynamical systems, compared to an arbitrary dynamical system, statistically present the characteristics of cascadeness and sequentiality, as observed in the budding and fission yeast cell- cycle. These results suggest that cascade-like behavior might be an intrinsic property of biological processes. PMID:26821940

  7. Controllability and observability of Boolean networks arising from biology

    Science.gov (United States)

    Li, Rui; Yang, Meng; Chu, Tianguang

    2015-02-01

    Boolean networks are currently receiving considerable attention as a computational scheme for system level analysis and modeling of biological systems. Studying control-related problems in Boolean networks may reveal new insights into the intrinsic control in complex biological systems and enable us to develop strategies for manipulating biological systems using exogenous inputs. This paper considers controllability and observability of Boolean biological networks. We propose a new approach, which draws from the rich theory of symbolic computation, to solve the problems. Consequently, simple necessary and sufficient conditions for reachability, controllability, and observability are obtained, and algorithmic tests for controllability and observability which are based on the Gröbner basis method are presented. As practical applications, we apply the proposed approach to several different biological systems, namely, the mammalian cell-cycle network, the T-cell activation network, the large granular lymphocyte survival signaling network, and the Drosophila segment polarity network, gaining novel insights into the control and/or monitoring of the specific biological systems.

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

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

  10. Meadow enriched ACP process algebras

    OpenAIRE

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

    2009-01-01

    We introduce the notion of an ACP process algebra. The models of the axiom system ACP are the origin of this notion. ACP process algebras have to do with processes in which no data are involved. We also introduce the notion of a meadow enriched ACP process algebra, which is a simple generalization of the notion of an ACP process algebra to processes in which data are involved. In meadow enriched ACP process algebras, the mathematical structure for data is a meadow.

  11. Hom-power associative algebras

    OpenAIRE

    Yau, Donald

    2010-01-01

    A generalization of power associative algebra, called Hom-power associative algebra, is studied. The main result says that a multiplicative Hom-algebra is Hom-power associative if and only if it satisfies two identities of degrees three and four. It generalizes Albert's result that power associativity is equivalent to third and fourth power associativity. In particular, multiplicative right Hom-alternative algebras and non-commutative Hom-Jordan algebras are Hom-power associative.

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

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

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

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

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

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

  18. Geometric Algebra for Physicists

    Science.gov (United States)

    Doran, Chris; Lasenby, Anthony

    2007-11-01

    Preface; Notation; 1. Introduction; 2. Geometric algebra in two and three dimensions; 3. Classical mechanics; 4. Foundations of geometric algebra; 5. Relativity and spacetime; 6. Geometric calculus; 7. Classical electrodynamics; 8. Quantum theory and spinors; 9. Multiparticle states and quantum entanglement; 10. Geometry; 11. Further topics in calculus and group theory; 12. Lagrangian and Hamiltonian techniques; 13. Symmetry and gauge theory; 14. Gravitation; Bibliography; Index.

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

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

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

  2. Hopf Algebra of Sashes

    OpenAIRE

    Law, Shirley

    2014-01-01

    International audience A general lattice theoretic construction of Reading constructs Hopf subalgebras of the Malvenuto-Reutenauer Hopf algebra (MR) of permutations. The products and coproducts of these Hopf subalgebras are defined extrinsically in terms of the embedding in MR. The goal of this paper is to find an intrinsic combinatorial description of a particular one of these Hopf subalgebras. This Hopf algebra has a natural basis given by permutations that we call Pell permutations. The...

  3. Holomorphically Equivalent Algebraic Embeddings

    OpenAIRE

    Feller, Peter; Stampfli, Immanuel

    2014-01-01

    We prove that two algebraic embeddings of a smooth variety $X$ in $\\mathbb{C}^m$ are the same up to a holomorphic coordinate change, provided that $2 \\dim X + 1$ is smaller than or equal to $m$. This improves an algebraic result of Nori and Srinivas. For the proof we extend a technique of Kaliman using generic linear projections of $\\mathbb{C}^m$.

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

  5. Differential Hopf algebra structures on the universal enveloping algebra ofa 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.

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

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

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

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

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

  11. Three New Construction Methods of the Highly Nonlinear Balanced Boolean Function

    Institute of Scientific and Technical Information of China (English)

    TANXinglie; SHEKun; JIQingbing; ZHOUMingtian; SHENChangxiang

    2003-01-01

    Nonlinearity is a nonlinear criterion of Boolean function. In this paper, some useful definitions and theorems are introduced, and then three new ways to construct the highly nonlinear balanced boolean function are given by ways of concatenating, dividing, modifying and alternating, which are proven to be very effective.

  12. Comparing Boolean and Probabilistic Information Retrieval Systems Across Queries and Disciplines.

    Science.gov (United States)

    Losee, Robert M.

    1997-01-01

    Suggests a method that allows searchers to analytically compare the Boolean and probabilistic information retrieval approaches. Sample performance figures are provided for queries using the Boolean strategy, and for probabilistic systems. The variation of performance across sublanguages and queries is examined, as well as the performance of models…

  13. Boolean Operators and the Naive End-User: Moving to AND.

    Science.gov (United States)

    Proctor, Edward

    2002-01-01

    Discusses the confusion among end users in using Boolean operators when searching electronic resources. Highlights include search engines; site-specific search engines; the counterintuitive nature of Boolean logic; hidden defaults; the problem of conceptualization; reprogramming defaults; and a lack of user education. (LRW)

  14. Freestyle Vs. Boolean: A Comparison of Partial and Exact Match Retrieval Systems.

    Science.gov (United States)

    Paris, Lee Anne H.; Tibbo, Helen R.

    1998-01-01

    Compares results of traditional Boolean searching with those of Freestyle, LEXIS/NEXIS's natural language application. Study found that though the Boolean searches had better results more often, neither method demonstrated superior performance for every query, suggesting that different queries demand different techniques. Concludes that further…

  15. Boolean Classes and Qualitative Inquiry. WCER Working Paper No. 2006-3

    Science.gov (United States)

    Nathan, Mitchell J.; Jackson, Kristi

    2006-01-01

    The prominent role of Boolean classes in qualitative data analysis software is viewed by some as an encroachment of logical positivism on qualitative research methodology. The authors articulate an embodiment perspective, in which Boolean classes are viewed as conceptual metaphors for apprehending and manipulating data, concepts, and categories in…

  16. A Graphical Filter/Flow Representation of Boolean Queries: A Prototype Implementation and Evaluation.

    Science.gov (United States)

    Young, Degi; Shneiderman, Ben

    1993-01-01

    Literature showing the disadvantages of Boolean logic in online searching is reviewed, and research comparing the Filter/Flow visual interface (i.e., a graphical representation of Boolean operators) with a text-only interface is described. A significant difference in the total number of correct queries is reported that favored Filter/Flow. (16…

  17. A Theoretical Framework for Defining Similarity Measures for Boolean Search Request Formulations, Including Some Experimental Results.

    Science.gov (United States)

    Radecki, Tadeusz

    1985-01-01

    Reports research results into a methodology for determining similarity between queries characterized by Boolean search request formulations and discusses similarity measures for Boolean combinations of index terms. Rationale behind these measures is outlined, and conditions ensuring their equivalence are identified. Results of an experiment…

  18. Additive functions in boolean models of gene regulatory network modules.

    Science.gov (United States)

    Darabos, Christian; Di Cunto, Ferdinando; Tomassini, Marco; Moore, Jason H; Provero, Paolo; Giacobini, Mario

    2011-01-01

    Gene-on-gene regulations are key components of every living organism. Dynamical abstract models of genetic regulatory networks help explain the genome's evolvability and robustness. These properties can be attributed to the structural topology of the graph formed by genes, as vertices, and regulatory interactions, as edges. Moreover, the actual gene interaction of each gene is believed to play a key role in the stability of the structure. With advances in biology, some effort was deployed to develop update functions in boolean models that include recent knowledge. We combine real-life gene interaction networks with novel update functions in a boolean model. We use two sub-networks of biological organisms, the yeast cell-cycle and the mouse embryonic stem cell, as topological support for our system. On these structures, we substitute the original random update functions by a novel threshold-based dynamic function in which the promoting and repressing effect of each interaction is considered. We use a third real-life regulatory network, along with its inferred boolean update functions to validate the proposed update function. Results of this validation hint to increased biological plausibility of the threshold-based function. To investigate the dynamical behavior of this new model, we visualized the phase transition between order and chaos into the critical regime using Derrida plots. We complement the qualitative nature of Derrida plots with an alternative measure, the criticality distance, that also allows to discriminate between regimes in a quantitative way. Simulation on both real-life genetic regulatory networks show that there exists a set of parameters that allows the systems to operate in the critical region. This new model includes experimentally derived biological information and recent discoveries, which makes it potentially useful to guide experimental research. The update function confers additional realism to the model, while reducing the complexity

  19. Evolution and Controllability of Cancer Networks: A Boolean Perspective.

    Science.gov (United States)

    Srihari, Sriganesh; Raman, Venkatesh; Leong, Hon Wai; Ragan, Mark A

    2014-01-01

    Cancer forms a robust system capable of maintaining stable functioning (cell sustenance and proliferation) despite perturbations. Cancer progresses as stages over time typically with increasing aggressiveness and worsening prognosis. Characterizing these stages and identifying the genes driving transitions between them is critical to understand cancer progression and to develop effective anti-cancer therapies. In this work, we propose a novel model for the `cancer system' as a Boolean state space in which a Boolean network, built from protein-interaction and gene-expression data from different stages of cancer, transits between Boolean satisfiability states by "editing" interactions and "flipping" genes. Edits reflect rewiring of the PPI network while flipping of genes reflect activation or silencing of genes between stages. We formulate a minimization problem min flip to identify these genes driving the transitions. The application of our model (called BoolSpace) on three case studies-pancreatic and breast tumours in human and post spinal-cord injury (SCI) in rats-reveals valuable insights into the phenomenon of cancer progression: (i) interactions involved in core cell-cycle and DNA-damage repair pathways are significantly rewired in tumours, indicating significant impact to key genome-stabilizing mechanisms; (ii) several of the genes flipped are serine/threonine kinases which act as biological switches, reflecting cellular switching mechanisms between stages; and (iii) different sets of genes are flipped during the initial and final stages indicating a pattern to tumour progression. Based on these results, we hypothesize that robustness of cancer partly stems from "passing of the baton" between genes at different stages-genes from different biological processes and/or cellular components are involved in different stages of tumour progression thereby allowing tumour cells to evade targeted therapy, and therefore an effective therapy should target a "cover set" of

  20. The value of less connected agents in Boolean networks

    Science.gov (United States)

    Epstein, Daniel; Bazzan, Ana L. C.

    2013-11-01

    In multiagent systems, agents often face binary decisions where one seeks to take either the minority or the majority side. Examples are minority and congestion games in general, i.e., situations that require coordination among the agents in order to depict efficient decisions. In minority games such as the El Farol Bar Problem, previous works have shown that agents may reach appropriate levels of coordination, mostly by looking at the history of past decisions. Not many works consider any kind of structure of the social network, i.e., how agents are connected. Moreover, when structure is indeed considered, it assumes some kind of random network with a given, fixed connectivity degree. The present paper departs from the conventional approach in some ways. First, it considers more realistic network topologies, based on preferential attachments. This is especially useful in social networks. Second, the formalism of random Boolean networks is used to help agents to make decisions given their attachments (for example acquaintances). This is coupled with a reinforcement learning mechanism that allows agents to select strategies that are locally and globally efficient. Third, we use agent-based modeling and simulation, a microscopic approach, which allows us to draw conclusions about individuals and/or classes of individuals. Finally, for the sake of illustration we use two different scenarios, namely the El Farol Bar Problem and a binary route choice scenario. With this approach we target systems that adapt dynamically to changes in the environment, including other adaptive decision-makers. Our results using preferential attachments and random Boolean networks are threefold. First we show that an efficient equilibrium can be achieved, provided agents do experimentation. Second, microscopic analysis show that influential agents tend to consider few inputs in their Boolean functions. Third, we have also conducted measurements related to network clustering and centrality

  1. Boolean approaches to graph embeddings related to VLSI

    Institute of Scientific and Technical Information of China (English)

    LIU; Yanpei(

    2001-01-01

    [1]Hu, T. C., Kuh, S. E., Theory and concepts of circuit layout, in VLSI Circuit Layout: Theory and Design, New York:IEEE Press, 1985, 3-18.[2]Liu Yanpei, Embeddability in Graphs, Boston-Beijing: Kluwer Science, 1995.[3]Liu Yanpei, Some combinatorial optimization problems arising from VLSI circuit design, Applied Math. -JCU, 1993, 38:218-235.[4]Liu Yanpei, Marchioro, P. , Petreschi, R., At most single bend embeddings of cubic graphs, Applied Math. -CJU, 1994,39: 127-142.[5]Liu Yanpei, Marchioro, P. , Petreschi, R. et al. , Theoretical results on at most 1-bend embeddability of graphs, Acta Math.Appl. Sinica, 1992, 8: 188-192.[6]Liu Yanpei, Morgana, A., Simeone, B., General theoretical results on rectilinear embeddability of graphs, Acta Math. Ap- pl. Simca, 1991, 7: 187-192.[7]Calamoneri, T., Petreschi, R., Liu Yanpei, Optimally Extending Bistandard Graphs on the Orthogonal Grid, ASCM2000 Symposium, Tailand, Dec.17-21, 2000.[8]Liu Yanpei, Morgana, A., Simeone, B., A graph partition problem, Acta Math. Appl. Sinica, 1996, 12: 393-400.[9]Liu Yanpei, Morgana, A. , Simeone, B. , A linear algorithm for 2-bend embeddings of planar graphs in the two dimensional grid, Discrete Appl. Math., 1998, 81: 69-91.[10]Liu Yanpei, Boolean approach to planar embeddings of a graph, Acta Math. Sinica, New Series, 1989, 5: 64-79.[11]Hammer, P. L., Liu Yanpei, Simeone, B., Boolean approaches to combinatorial optimization, J. Math. Res. Expos.,1990, 10: 300-312, 455-468, 619-628.[12]Liu Yanpei, Boolean planarity characterization of graphs, Acta Math. Sinica, New Series, 1988, 4: 316-329.[13]Liu Yanpei, Boolean characterizations of planarity and planar embeddings of graphs, Ann. O. R., 1990, 24: 165-174.

  2. Soft Rough Approximation Operators on a Complete Atomic Boolean Lattice

    Directory of Open Access Journals (Sweden)

    Heba I. Mustafa

    2013-01-01

    Full Text Available The concept of soft sets based on complete atomic Boolean lattice, which can be seen as a generalization of soft sets, is introduced. Some operations on these soft sets are discussed, and new types of soft sets such as full, keeping infimum, and keeping supremum are defined and supported by some illustrative examples. Two pairs of new soft rough approximation operators are proposed and the relationship among soft set is investigated, and their related properties are given. We show that Järvinen's approximations can be viewed as a special case of our approximation. If , then our soft approximations coincide with crisp soft rough approximations (Feng et al. 2011.

  3. Boolean Variables in Economic Models Solved by Linear Programming

    Directory of Open Access Journals (Sweden)

    Lixandroiu D.

    2014-12-01

    Full Text Available The article analyses the use of logical variables in economic models solved by linear programming. Focus is given to the presentation of the way logical constraints are obtained and of the definition rules based on predicate logic. Emphasis is also put on the possibility to use logical variables in constructing a linear objective function on intervals. Such functions are encountered when costs or unitary receipts are different on disjunct intervals of production volumes achieved or sold. Other uses of Boolean variables are connected to constraint systems with conditions and the case of a variable which takes values from a finite set of integers.

  4. Self-organized networks of competing boolean agents

    Science.gov (United States)

    Paczuski; Bassler; Corral

    2000-04-01

    A model of Boolean agents competing in a market is presented where each agent bases his action on information obtained from a small group of other agents. The agents play a competitive game that rewards those in the minority. After a long time interval, the poorest player's strategy is changed randomly, and the process is repeated. Eventually the network evolves to a stationary but intermittent state where random mutation of the worst strategy can change the behavior of the entire network, often causing a switch in the dynamics between attractors of vastly different lengths. PMID:11019043

  5. Symmetric Groups and Quotient Complexity of Boolean Operations

    OpenAIRE

    Bell, Jason; Brzozowski, Janusz; Moreira, Nelma; Reis, Rogério

    2013-01-01

    The quotient complexity of a regular language L is the number of left quotients of L, which is the same as the state complexity of L. Suppose that L and L' are binary regular languages with quotient complexities m and n, and that the transition semigroups of the minimal deterministic automata accepting L and L' are the symmetric groups S_m and S_n of degrees m and n, respectively. Denote by o any binary boolean operation that is not a constant and not a function of one argument only. For m,n ...

  6. From Exact Learning to Computing Boolean Functions and Back Again

    CERN Document Server

    Goschin, Sergiu

    2012-01-01

    The goal of the paper is to relate complexity measures associated with the evaluation of Boolean functions (certificate complexity, decision tree complexity) and learning dimensions used to characterize exact learning (teaching dimension, extended teaching dimension). The high level motivation is to discover non-trivial relations between exact learning of an unknown concept and testing whether an unknown concept is part of a concept class or not. Concretely, the goal is to provide lower and upper bounds of complexity measures for one problem type in terms of the other.

  7. Graphical interpretation of Boolean operators for protein NMR assignments.

    Science.gov (United States)

    Verdegem, Dries; Dijkstra, Klaas; Hanoulle, Xavier; Lippens, Guy

    2008-09-01

    We have developed a graphics based algorithm for semi-automated protein NMR assignments. Using the basic sequential triple resonance assignment strategy, the method is inspired by the Boolean operators as it applies "AND"-, "OR"- and "NOT"-like operations on planes pulled out of the classical three-dimensional spectra to obtain its functionality. The method's strength lies in the continuous graphical presentation of the spectra, allowing both a semi-automatic peaklist construction and sequential assignment. We demonstrate here its general use for the case of a folded protein with a well-dispersed spectrum, but equally for a natively unfolded protein where spectral resolution is minimal. PMID:18762868

  8. Bebop to the Boolean boogie an unconventional guide to electronics

    CERN Document Server

    Maxfield, Clive

    2003-01-01

    From reviews of the first edition:""If you want to be reminded of the joy of electronics, take a look at Clive (Max) Maxfield's book Bebop to the Boolean Boogie.""--Computer Design ""Lives up to its title as a useful and entertaining technical guide....well-suited for students, technical writers, technicians, and sales and marketing people.""--Electronic Design""Writing a book like this one takes audacity! ... Maxfield writes lucidly on a variety of complex topics without 'writing down' to his audience."" --EDN""A highly readable, well-illustrated guided tour

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

  10. Rings of quotients of incidence algebras and path algebras

    DEFF Research Database (Denmark)

    Esparza, Eduardo Ortega

    2006-01-01

    We compute the maximal right/left/symmetric rings of quotients of finite dimensional incidence and graph algebras. We show that these rings of quotients are Morita equivalent to incidence algebras and path algebras respectively, with respect to simpler, well determined partially ordered sets...

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

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

  13. On the construction of cryptographically strong Boolean functions with desirable trade-off

    Institute of Scientific and Technical Information of China (English)

    REN Kui; PARK Jaemin; KIM Kwangjo

    2005-01-01

    This paper proposes a practical algorithm for systematically generating strong Boolean functions (f:GF(2)n→GF(2))with cryptographic meaning. This algorithm takes bent function as input and directly outputs the resulted Boolean function in terms of truth table sequence. This algorithm was used to develop two classes of balanced Boolean functions, one of which has very good cryptographic properties: nl(f)=22k-1-2k+2k-2 (n=2k), with the sum-of-squares avalanche characteristic off satisfying σf=24k+23k+2+23k+23k-2 and the absolute avalanche characteristic of △f satisfying △f=2k+1. This is the best result up to now compared to existing ones. Instead of bent sequences, starting from random Boolean functions was also tested in the algorithm. Experimental results showed that starting from bent sequences is highly superior to starting from random Boolean functions.

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

  15. Algebraic quantum field theory

    International Nuclear Information System (INIS)

    The basic assumption that the complete information relevant for a relativistic, local quantum theory is contained in the net structure of the local observables of this theory results first of all in a concise formulation of the algebraic structure of the superselection theory and an intrinsic formulation of charge composition, charge conjugation and the statistics of an algebraic quantum field theory. In a next step, the locality of massive particles together with their spectral properties are wed for the formulation of a selection criterion which opens the access to the massive, non-abelian quantum gauge theories. The role of the electric charge as a superselection rule results in the introduction of charge classes which in term lead to a set of quantum states with optimum localization properties. Finally, the asymptotic observables of quantum electrodynamics are investigated within the framework of algebraic quantum field theory. (author)

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

  17. On Griess Algebras

    Directory of Open Access Journals (Sweden)

    Michael Roitman

    2008-08-01

    Full Text Available In this paper we prove that for any commutative (but in general non-associative algebra A with an invariant symmetric non-degenerate bilinear form there is a graded vertex algebra V = V_0 oplus V2 oplus V3 oplus ..., such that dim V_0 = 1 and V_2 contains A. We can choose V so that if A has a unit e, then 2e is the Virasoro element of V, and if G is a finite group of automorphisms of A, then G acts on V as well. In addition, the algebra V can be chosen with a non-degenerate invariant bilinear form, in which case it is simple.

  18. On Griess Algebras

    Science.gov (United States)

    Roitman, Michael

    2008-08-01

    In this paper we prove that for any commutative (but in general non-associative) algebra A with an invariant symmetric non-degenerate bilinear form there is a graded vertex algebra V = V0 Å V2 Å V3 Å ¼, such that dim V0 = 1 and V2 contains A. We can choose V so that if A has a unit e, then 2e is the Virasoro element of V, and if G is a finite group of automorphisms of A, then G acts on V as well. In addition, the algebra V can be chosen with a non-degenerate invariant bilinear form, in which case it is simple.

  19. Controllability and observability of Boolean control networks%布尔控制网络的能控性与能观性

    Institute of Scientific and Technical Information of China (English)

    李志强; 宋金利

    2013-01-01

    Using the semi-tensor product,we convert the Boolean control network to its algebraic form.From the structure matrix of Boolean control network,the controllability and observability of the Boolean control network are discussed.A novel necessary and sufficient condition for controllability,which improves the recent results,is given.The new controllability condition eliminates the redundant computation of controllability matrix.The highest power of matrix is reduced from 2m+n to 2 n.Also,a sufficient condition for observability is obtained,which can be computed easily.A numerical example is presented to show the applicability of our controllability and observability condition.%利用矩阵的半张量积,布尔控制网络被转化为离散时间系统.本文从离散时间系统的结构矩阵出发,讨论了逻辑控制系统的能控能观性条件,得到了一个新的能控性条件.新的条件简化了原有能控性矩阵的计算复杂性,矩阵的最高阶数由原来的2m+n降到了2n.另外,还得到了检验布尔控制网络能观性的条件.与原有条件相比,新的条件更容易计算检验.最后,给出一个实例,检验给出的能控能观性判断条件的正确性.

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

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

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

  3. Principles of algebraic geometry

    CERN Document Server

    Griffiths, Phillip A

    1994-01-01

    A comprehensive, self-contained treatment presenting general results of the theory. Establishes a geometric intuition and a working facility with specific geometric practices. Emphasizes applications through the study of interesting examples and the development of computational tools. Coverage ranges from analytic to geometric. Treats basic techniques and results of complex manifold theory, focusing on results applicable to projective varieties, and includes discussion of the theory of Riemann surfaces and algebraic curves, algebraic surfaces and the quadric line complex as well as special top

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

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

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

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

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

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

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

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

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

  13. Lie 2-algebra models

    International Nuclear Information System (INIS)

    In this paper, we begin the study of zero-dimensional field theories with fields taking values in a semistrict Lie 2-algebra. These theories contain the IKKT matrix model and various M-brane related models as special cases. They feature solutions that can be interpreted as quantized 2-plectic manifolds. In particular, we find solutions corresponding to quantizations of ℝ3, S3 and a five-dimensional Hpp-wave. Moreover, by expanding a certain class of Lie 2-algebra models around the solution corresponding to quantized ℝ3, we obtain higher BF-theory on this quantized space

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

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

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

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

  19. Derivations of generalized Weyl algebras

    Institute of Scientific and Technical Information of China (English)

    SU; Yucai(苏育才)

    2003-01-01

    A class of the associative and Lie algebras A[D] = A × F[D] of Weyl type are studied, where Ais a commutative associative algebra with an identity element over a field F of characteristic zero, and F[D] isthe polynomial algebra of a finite dimensional commutative subalgebra of locally finite derivations of A suchthat A is D-simple. The derivations of these associative and Lie algebras are precisely determined.

  20. The theory of algebraic numbers

    CERN Document Server

    Pollard, Harry

    1998-01-01

    An excellent introduction to the basics of algebraic number theory, this concise, well-written volume examines Gaussian primes; polynomials over a field; algebraic number fields; and algebraic integers and integral bases. After establishing a firm introductory foundation, the text explores the uses of arithmetic in algebraic number fields; the fundamental theorem of ideal theory and its consequences; ideal classes and class numbers; and the Fermat conjecture. 1975 edition. References. List of Symbols. Index.

  1. Optimal Algorithm for Algebraic Factoring

    Institute of Scientific and Technical Information of China (English)

    支丽红

    1997-01-01

    This paper presents on optimized method for factoring multivariate polynomials over algebraic extension fields defined by an irreducible ascending set. The basic idea is to convert multivariate polynomials to univariate polynomials and algebraic extension fields to algebraic number fields by suitable integer substituteions.Then factorize the univariate polynomials over the algebraic number fields.Finally,construct mulativariate factors of the original polynomial by Hensel lemma and TRUEFACTOR test.Some examples with timing are included.

  2. Meadow enriched ACP process algebras

    NARCIS (Netherlands)

    J.A. Bergstra; C.A. Middelburg

    2009-01-01

    We introduce the notion of an ACP process algebra. The models of the axiom system ACP are the origin of this notion. ACP process algebras have to do with processes in which no data are involved. We also introduce the notion of a meadow enriched ACP process algebra, which is a simple generalization o

  3. Some Hopf algebras of trees

    NARCIS (Netherlands)

    Laan, P. van der

    2001-01-01

    In the literature several Hopf algebras that can be described in terms of trees have been studied. This paper tries to answer the question whether one can understand some of these Hopf algebras in terms of a single mathematical construction. The starting point is the Hopf algebra of rooted trees as

  4. Computer Algebra in Particle Physics

    OpenAIRE

    Weinzierl, Stefan

    2002-01-01

    These lectures given to graduate students in theoretical particle physics, provide an introduction to the ``inner workings'' of computer algebra systems. Computer algebra has become an indispensable tool for precision calculations in particle physics. A good knowledge of the basics of computer algebra systems allows one to exploit these systems more efficiently.

  5. An Algebra of Reversible Computation

    OpenAIRE

    Wang, Yong

    2014-01-01

    We design an axiomatization for reversible computation called reversible ACP (RACP). It has four extendible modules, basic reversible processes algebra (BRPA), algebra of reversible communicating processes (ARCP), recursion and abstraction. Just like process algebra ACP in classical computing, RACP can be treated as an axiomatization foundation for reversible computation.

  6. The Maximal Graded Left Quotient Algebra of a Graded Algebra

    Institute of Scientific and Technical Information of China (English)

    Gonzalo ARANDA PINO; Mercedes SILES MOLINA

    2006-01-01

    We construct the maximal graded left quotient algebra of every graded algebra A without homogeneous total right zero divisors as the direct limit of graded homomorphisms (of left A-modules)from graded dense left ideals of A into a graded left quotient algebra of A. In the case of a superalgebra,and with some extra hypothesis, we prove that the component in the neutral element of the group of the maximal graded left quotient algebra coincides with the maximal left quotient algebra of the component in the neutral element of the group of the superalgebra.

  7. Boolean difference equations. I - Formulation and dynamic behavior

    Science.gov (United States)

    Dee, D.; Ghil, M.

    1984-01-01

    In many biological and physical systems, feedback mechanisms depend on a set of thresholds associated with the state variables. Each feedback has a characteristic time scale. It is suggested that delay-difference equations for Boolean-valued variables are an appropriate mathematical framework for such situations: the feedback thresholds result in the discrete, on-off character of the variables, and the interaction time scales of the feedbacks are expressed as delays. The initial-value problem for Boolean delay equations (B-Delta-Es) is formulated, and shown to have unique solutions for all times. Examples of periodic and aperiodic solutions are given. Aperiodic solutions have increasing complexity which depends on time t roughly as t to the l-1 power, l being the number of delays. Stability of solutions is defined, and some examples of stability analysis are given; additional stability questions are raised. The present formulation of (B-Delta-Es) is compared with related work and generalizations are suggested.

  8. Direct relations between morphology and transport in Boolean models.

    Science.gov (United States)

    Scholz, Christian; Wirner, Frank; Klatt, Michael A; Hirneise, Daniel; Schröder-Turk, Gerd E; Mecke, Klaus; Bechinger, Clemens

    2015-10-01

    We study the relation of permeability and morphology for porous structures composed of randomly placed overlapping circular or elliptical grains, so-called Boolean models. Microfluidic experiments and lattice Boltzmann simulations allow us to evaluate a power-law relation between the Euler characteristic of the conducting phase and its permeability. Moreover, this relation is so far only directly applicable to structures composed of overlapping grains where the grain density is known a priori. We develop a generalization to arbitrary structures modeled by Boolean models and characterized by Minkowski functionals. This generalization works well for the permeability of the void phase in systems with overlapping grains, but systematic deviations are found if the grain phase is transporting the fluid. In the latter case our analysis reveals a significant dependence on the spatial discretization of the porous structure, in particular the occurrence of single isolated pixels. To link the results to percolation theory we performed Monte Carlo simulations of the Euler characteristic of the open cluster, which reveals different regimes of applicability for our permeability-morphology relations close to and far away from the percolation threshold.

  9. Chemical Visualization of Boolean Functions: A Simple Chemical Computer

    Science.gov (United States)

    Blittersdorf, R.; Müller, J.; Schneider, F. W.

    1995-08-01

    We present a chemical realization of the Boolean functions AND, OR, NAND, and NOR with a neutralization reaction carried out in three coupled continuous flow stirred tank reactors (CSTR). Two of these CSTR's are used as input reactors, the third reactor marks the output. The chemical reaction is the neutralization of hydrochloric acid (HCl) with sodium hydroxide (NaOH) in the presence of phenolphtalein as an indicator, which is red in alkaline solutions and colorless in acidic solutions representing the two binary states 1 and 0, respectively. The time required for a "chemical computation" is determined by the flow rate of reactant solutions into the reactors since the neutralization reaction itself is very fast. While the acid flow to all reactors is equal and constant, the flow rate of NaOH solution controls the states of the input reactors. The connectivities between the input and output reactors determine the flow rate of NaOH solution into the output reactor, according to the chosen Boolean function. Thus the state of the output reactor depends on the states of the input reactors.

  10. Evolution of a designless nanoparticle network into reconfigurable Boolean logic

    Science.gov (United States)

    Bose, S. K.; Lawrence, C. P.; Liu, Z.; Makarenko, K. S.; van Damme, R. M. J.; Broersma, H. J.; van der Wiel, W. G.

    2015-12-01

    Natural computers exploit the emergent properties and massive parallelism of interconnected networks of locally active components. Evolution has resulted in systems that compute quickly and that use energy efficiently, utilizing whatever physical properties are exploitable. Man-made computers, on the other hand, are based on circuits of functional units that follow given design rules. Hence, potentially exploitable physical processes, such as capacitive crosstalk, to solve a problem are left out. Until now, designless nanoscale networks of inanimate matter that exhibit robust computational functionality had not been realized. Here we artificially evolve the electrical properties of a disordered nanomaterials system (by optimizing the values of control voltages using a genetic algorithm) to perform computational tasks reconfigurably. We exploit the rich behaviour that emerges from interconnected metal nanoparticles, which act as strongly nonlinear single-electron transistors, and find that this nanoscale architecture can be configured in situ into any Boolean logic gate. This universal, reconfigurable gate would require about ten transistors in a conventional circuit. Our system meets the criteria for the physical realization of (cellular) neural networks: universality (arbitrary Boolean functions), compactness, robustness and evolvability, which implies scalability to perform more advanced tasks. Our evolutionary approach works around device-to-device variations and the accompanying uncertainties in performance. Moreover, it bears a great potential for more energy-efficient computation, and for solving problems that are very hard to tackle in conventional architectures.

  11. Harmonic Analysis of Boolean Networks: Determinative Power and Perturbations

    CERN Document Server

    Heckel, Reinhard; Bossert, Martin

    2011-01-01

    Consider a large Boolean network with a feed forward structure. Given a probability distribution for the inputs, can one find-possibly small-collections of input nodes that determine the states of most other nodes in the network? To identify these nodes, a notion that quantifies the determinative power of an input over states in the network is needed. We argue that the mutual information (MI) between a subset of the inputs X = {X_1, ..., X_n} of node i and the function f_i(X)$ associated with node i quantifies the determinative power of this subset of inputs over node i. To study the relation of determinative power to sensitivity to perturbations, we relate the MI to measures of perturbations, such as the influence of a variable, in terms of inequalities. The result shows that, maybe surprisingly, an input that has large influence does not necessarily have large determinative power. The main tool for the analysis is Fourier analysis of Boolean functions. Whether a function is sensitive to perturbations or not...

  12. Direct relations between morphology and transport in Boolean models

    Science.gov (United States)

    Scholz, Christian; Wirner, Frank; Klatt, Michael A.; Hirneise, Daniel; Schröder-Turk, Gerd E.; Mecke, Klaus; Bechinger, Clemens

    2015-10-01

    We study the relation of permeability and morphology for porous structures composed of randomly placed overlapping circular or elliptical grains, so-called Boolean models. Microfluidic experiments and lattice Boltzmann simulations allow us to evaluate a power-law relation between the Euler characteristic of the conducting phase and its permeability. Moreover, this relation is so far only directly applicable to structures composed of overlapping grains where the grain density is known a priori. We develop a generalization to arbitrary structures modeled by Boolean models and characterized by Minkowski functionals. This generalization works well for the permeability of the void phase in systems with overlapping grains, but systematic deviations are found if the grain phase is transporting the fluid. In the latter case our analysis reveals a significant dependence on the spatial discretization of the porous structure, in particular the occurrence of single isolated pixels. To link the results to percolation theory we performed Monte Carlo simulations of the Euler characteristic of the open cluster, which reveals different regimes of applicability for our permeability-morphology relations close to and far away from the percolation threshold.

  13. Evolution of a designless nanoparticle network into reconfigurable Boolean logic.

    Science.gov (United States)

    Bose, S K; Lawrence, C P; Liu, Z; Makarenko, K S; van Damme, R M J; Broersma, H J; van der Wiel, W G

    2015-12-01

    Natural computers exploit the emergent properties and massive parallelism of interconnected networks of locally active components. Evolution has resulted in systems that compute quickly and that use energy efficiently, utilizing whatever physical properties are exploitable. Man-made computers, on the other hand, are based on circuits of functional units that follow given design rules. Hence, potentially exploitable physical processes, such as capacitive crosstalk, to solve a problem are left out. Until now, designless nanoscale networks of inanimate matter that exhibit robust computational functionality had not been realized. Here we artificially evolve the electrical properties of a disordered nanomaterials system (by optimizing the values of control voltages using a genetic algorithm) to perform computational tasks reconfigurably. We exploit the rich behaviour that emerges from interconnected metal nanoparticles, which act as strongly nonlinear single-electron transistors, and find that this nanoscale architecture can be configured in situ into any Boolean logic gate. This universal, reconfigurable gate would require about ten transistors in a conventional circuit. Our system meets the criteria for the physical realization of (cellular) neural networks: universality (arbitrary Boolean functions), compactness, robustness and evolvability, which implies scalability to perform more advanced tasks. Our evolutionary approach works around device-to-device variations and the accompanying uncertainties in performance. Moreover, it bears a great potential for more energy-efficient computation, and for solving problems that are very hard to tackle in conventional architectures. PMID:26389658

  14. Certain associative algebras similar to $U(sl_{2})$ and Zhu's algebra $A(V_{L})$

    OpenAIRE

    Dong, Chongying; Li, Haisheng; Mason, Geoffrey

    1996-01-01

    It is proved that Zhu's algebra for vertex operator algebra associated to a positive-definite even lattice of rank one is a finite-dimensional semiprimitive quotient algebra of certain associative algebra introduced by Smith. Zhu's algebra for vertex operator algebra associated to any positive-definite even lattice is also calculated and is related to a generalization of Smith's algebra.

  15. Observable Algebra in Field Algebra of G-spin Models

    Institute of Scientific and Technical Information of China (English)

    蒋立宁

    2003-01-01

    Field algebra of G-spin models can provide the simplest examples of lattice field theory exhibiting quantum symmetry. Let D(G) be the double algebra of a finite group G and D(H), a sub-algebra of D(G) determined by subgroup H of G. This paper gives concrete generators and the structure of the observable algebra AH, which is a D(H)-invariant sub-algebra in the field algebra of G-spin models F, and shows that AH is a C*-algebra. The correspondence between H and AH is strictly monotonic. Finally, a duality between D(H) and AH is given via an irreducible vacuum C*-representation of F.

  16. Commutative algebra with a view toward algebraic geometry

    CERN Document Server

    Eisenbud, David

    1995-01-01

    Commutative Algebra is best understood with knowledge of the geometric ideas that have played a great role in its formation, in short, with a view towards algebraic geometry. The author presents a comprehensive view of commutative algebra, from basics, such as localization and primary decomposition, through dimension theory, differentials, homological methods, free resolutions and duality, emphasizing the origins of the ideas and their connections with other parts of mathematics. Many exercises illustrate and sharpen the theory and extended exercises give the reader an active part in complementing the material presented in the text. One novel feature is a chapter devoted to a quick but thorough treatment of Grobner basis theory and the constructive methods in commutative algebra and algebraic geometry that flow from it. Applications of the theory and even suggestions for computer algebra projects are included. This book will appeal to readers from beginners to advanced students of commutative algebra or algeb...

  17. The Power of Algebra.

    Science.gov (United States)

    Boiteau, Denise; Stansfield, David

    This document describes mathematical programs on the basic concepts of algebra produced by Louisiana Public Broadcasting. Programs included are: (1) "Inverse Operations"; (2) "The Order of Operations"; (3) "Basic Properties" (addition and multiplication of numbers and variables); (4) "The Positive and Negative Numbers"; and (5) "Using Positive…

  18. Finitary Algebraic Superspace

    CERN Document Server

    Zapatrin, R R

    1998-01-01

    An algebraic scheme is suggested in which discretized spacetime turns out to be a quantum observable. As an example, a toy model producing spacetimes of four points with different topologies is presented. The possibility of incorporating this scheme into the framework of non-commutative differential geometry is discussed.

  19. Questions on Algebraic Varieties

    CERN Document Server

    Marchionna, E

    2011-01-01

    P. Dolbeault: Residus et courants.- D. Mumford: Varieties defined by quadratic equations.- A. Neron: Hauteurs et theorie des intersections.- A. Seidenberg: Report on analytic product.- C.S. Seshadri: Moduli of p-vector bundles over an algebraic curve.- O. Zariski: Contributions to the problem of equi-singularity.

  20. Algebraic topology and concurrency

    DEFF Research Database (Denmark)

    Fajstrup, Lisbeth; Raussen, Martin; Goubault, Eric

    2006-01-01

    We show in this article that some concepts from homotopy theory, in algebraic topology,are relevant for studying concurrent programs. We exhibit a natural semantics of semaphore programs, based on partially ordered topological spaces, which are studied up to “elastic deformation” or homotopy, giv...

  1. Operation of Algebraic Fractions

    Institute of Scientific and Technical Information of China (English)

    2008-01-01

    <正>The first step in factorizing algebraic expressions is to take out the common factors of all the terms of the expression.For example,2x~2+14x+24=2(x~2+7x+12)=2(x+3)(x+4) The three identities are also useful in factorizing some quadratic expressions:

  2. Simple algebras of Weyl type

    Institute of Scientific and Technical Information of China (English)

    SU; Yucai(

    2001-01-01

    [1] Kawamoto, N., Generalizations of Witt algebras over a field of characteristic zero, Hiroshima Math. J., 1986, 16: 417.[2] Osborn, J. M., New simple infinite-dimensional Lie algebras of characteristic 0, J. Alg., 1996, 185: 820.[3] Dokovic, D. Z., Zhao, K., Derivations, isomorphisms, and second cohomology of generalized Witt algebras, Trans. of Amer. Math. Soc., 1998, 350(2): 643.[4] Dokovic, D. Z., Zhao, K., Generalized Cartan type W Lie algebras in characteristic zero, J. Alg., 1997, 195: 170.[5] Osborn, J. M., Zhao, K., Generalized Poisson bracket and Lie algebras of type H in characteristic 0, Math. Z., 1999, 230: 107.[6] Osborn, J. M., Zhao, K., Generalized Cartan type K Lie algebras in characteristic 0, Comm. Alg., 1997, 25: 3325.[7] Zhao, K., Isomorphisms between generalized Cartan type W Lie algebras in characteristic zero, Canadian J. Math., 1998, 50: 210.[8] Passman, D. P., Simple Lie algebras of Witt type, J. Algebra, 1998, 206: 682.[9] Jordan, D. A., On the simplicity of Lie algebras of derivations of commutative algebras, J. Alg., 2000, 206: 682.[10] Xu, X., New generalized simple Lie algebras of Cartan type over a field with characteristic 0, J. Alg., 2000, 244: 23.[11] Su, Y., Xu, X., Zhang, H., Derivation-simple algebras and the structures of Lie algebras of generalized Witt type, J. Alg., 2000, 233: 642.[12] Dixmer, J., Enveloping Algebras, Amsterdam: North Holland, 1977.

  3. CSR expansions of matrix powers in max algebra

    CERN Document Server

    Sergeev, Sergei

    2009-01-01

    We study the behavior of max-algebraic powers of a reducible nonnegative n by n matrix A. We show that for t>3n^2, the powers A^t can be expanded in max-algebraic powers of the form CS^tR, where C and R are extracted from columns and rows of certain Kleene stars and S is diadonally similar to a Boolean matrix. We study the properties of individual terms and show that all terms, for a given t>3n^2, can be found in O(n^4 log n) operations. We show that the powers have a well-defined ultimate behavior, where certain terms are totally or partially suppressed, thus leading to ultimate CS^tR terms and the corresponding ultimate expansion. We apply this expansion to the question whether {A^ty, t>0} is ultimately linear periodic for each starting vector y, showing that this question can be also answered in O(n^4 log n) time. We give examples illustrating our main results.

  4. On ultraproducts of operator algebras

    Institute of Scientific and Technical Information of China (English)

    LI Weihua

    2005-01-01

    Some basic questions on ultraproducts of C*-algebras and yon Neumann algebras, including the relation to K-theory of C*-algebras are considered. More specifically,we prove that under certain conditions, the K-groups of ultraproduct of C*-algebras are isomorphic to the ultraproduct of respective K-groups of C*-algebras. We also show that the ultraproducts of factors of type Ⅱ1 are prime, i.e. not isomorphic to any non-trivial tensor product.

  5. Quantum algebra of $N$ superspace

    CERN Document Server

    Hatcher, N; Stephany, J

    2006-01-01

    We identify the quantum algebra of position and momentum operators for a quantum system in superspace bearing an irreducible representation of the super Poinca\\'e algebra. This algebra is noncommutative for the position operators. We use the properties of superprojectors in D=4 $N$ superspace to construct explicit position and momentum operators satisfying the algebra. They act on wave functions corresponding to different supermultiplets classified by its superspin. We show that the quantum algebra associated to the massive superparticle is a particular case described by a supermultiplet of superspin 0. This result generalizes the construction for D=4, N=1 reported recently.

  6. Algebraic Approach to Algorithmic Logic

    Directory of Open Access Journals (Sweden)

    Bancerek Grzegorz

    2014-09-01

    Full Text Available We introduce algorithmic logic - an algebraic approach according to [25]. It is done in three stages: propositional calculus, quantifier calculus with equality, and finally proper algorithmic logic. For each stage appropriate signature and theory are defined. Propositional calculus and quantifier calculus with equality are explored according to [24]. A language is introduced with language signature including free variables, substitution, and equality. Algorithmic logic requires a bialgebra structure which is an extension of language signature and program algebra. While-if algebra of generator set and algebraic signature is bialgebra with appropriate properties and is used as basic type of algebraic logic.

  7. Notes on Piecewise-Koszul Algebras

    Institute of Scientific and Technical Information of China (English)

    Jia Feng L(U); Xiao Lan YU

    2011-01-01

    The relationships between piecewise-Koszul algebras and other "Koszul-type" algebras are discussed.. The Yoneda-Ext algebra and the dual algebra of a piecewise-Koszul algebra are studied, and a sufficient condition for the dual algebra A to be piecewise-Koszul is given. Finally, by studying the trivial extension algebras of the path algebras of Dynkin quivers in bipartite orientation, we give explicit constructions for piecewise-Koszul algebras with arbitrary "period" and piecewise-Koszul algebras with arbitrary "jump-degree".

  8. The Green formula and heredity of algebras

    Institute of Scientific and Technical Information of China (English)

    2005-01-01

    [1]Green, J. A., Hall algebras, hereditary algebras and quantum groups, Invent. Math. 1995, 120: 361-377.[2]Ringel, C. M., Green's theorem on Hall algebras, in Representations of Algebras and Related Topics, CMS Conference Proceedings 19, Providence, 1996, 185-245.[3]Xiao J., Drinfeld double and Ringel-Green theory of Hall Algebras, J. Algebra, 1997, 190: 100-144.[4]Sevenhant, B., Van den Bergh, M., A relation between a conjecture of Kac and the structure of the Hall algebra,J. Pure Appl. Algebra, 2001, 160: 319-332.[5]Deng B., Xiao, J., On double Ringel-Hall algebras, J. Algebra, 2002, 251: 110-149.

  9. Operator algebras and topology

    International Nuclear Information System (INIS)

    These notes, based on three lectures on operator algebras and topology at the 'School on High Dimensional Manifold Theory' at the ICTP in Trieste, introduce a new set of tools to high dimensional manifold theory, namely techniques coming from the theory of operator algebras, in particular C*-algebras. These are extensively studied in their own right. We will focus on the basic definitions and properties, and on their relevance to the geometry and topology of manifolds. A central pillar of work in the theory of C*-algebras is the Baum-Connes conjecture. This is an isomorphism conjecture, as discussed in the talks of Luck, but with a certain special flavor. Nevertheless, it has important direct applications to the topology of manifolds, it implies e.g. the Novikov conjecture. In the first chapter, the Baum-Connes conjecture will be explained and put into our context. Another application of the Baum-Connes conjecture is to the positive scalar curvature question. This will be discussed by Stephan Stolz. It implies the so-called 'stable Gromov-Lawson-Rosenberg conjecture'. The unstable version of this conjecture said that, given a closed spin manifold M, a certain obstruction, living in a certain (topological) K-theory group, vanishes if and only M admits a Riemannian metric with positive scalar curvature. It turns out that this is wrong, and counterexamples will be presented in the second chapter. The third chapter introduces another set of invariants, also using operator algebra techniques, namely L2-cohomology, L2-Betti numbers and other L2-invariants. These invariants, their basic properties, and the central questions about them, are introduced in the third chapter. (author)

  10. $A\\mathcal{T}$-Algebras and Extensions of $AT$-Algebras

    Indian Academy of Sciences (India)

    Hongliang Yao

    2010-04-01

    Lin and Su classified $A\\mathcal{T}$-algebras of real rank zero. This class includes all $A\\mathbb{T}$-algebras of real rank zero as well as many *-algebras which are not stably finite. An $A\\mathcal{T}$-algebra often becomes an extension of an $A\\mathbb{T}$-algebra by an -algebra. In this paper, we show that there is an essential extension of an $A\\mathbb{T}$-algebra by an -algebra which is not an $A\\mathcal{T}$-algebra. We describe a characterization of an extension of an $A\\mathbb{T}$-algebra by an -algebra if is an $A\\mathcal{T}$-algebra.

  11. On the robustness of NK-Kauffman networks against changes in their connections and Boolean functions

    Science.gov (United States)

    Zertuche, Federico

    2009-04-01

    NK-Kauffman networks LKN are a subset of the Boolean functions on N Boolean variables to themselves, ΛN={ξ :Z2N→Z2N}. To each NK-Kauffman network it is possible to assign a unique Boolean function on N variables through the function Ψ :LKN→ΛN. The probability PK that Ψ(f )=Ψ(f'), when f' is obtained through f by a change in one of its K-Boolean functions (bK:Z2K→Z2), and/or connections, is calculated. The leading term of the asymptotic expansion of PK, for N ≫1, turns out to depend on the probability to extract the tautology and contradiction Boolean functions, and in the average value of the distribution of probability of the Boolean functions, the other terms decay as O(1/N). In order to accomplish this, a classification of the Boolean functions in terms of what I have called their irreducible degree of connectivity is established. The mathematical findings are discussed in the biological context, where Ψ is used to model the genotype-phenotype map.

  12. Algebraic connectivity and graph robustness.

    Energy Technology Data Exchange (ETDEWEB)

    Feddema, John Todd; Byrne, Raymond Harry; Abdallah, Chaouki T. (University of New Mexico)

    2009-07-01

    Recent papers have used Fiedler's definition of algebraic connectivity to show that network robustness, as measured by node-connectivity and edge-connectivity, can be increased by increasing the algebraic connectivity of the network. By the definition of algebraic connectivity, the second smallest eigenvalue of the graph Laplacian is a lower bound on the node-connectivity. In this paper we show that for circular random lattice graphs and mesh graphs algebraic connectivity is a conservative lower bound, and that increases in algebraic connectivity actually correspond to a decrease in node-connectivity. This means that the networks are actually less robust with respect to node-connectivity as the algebraic connectivity increases. However, an increase in algebraic connectivity seems to correlate well with a decrease in the characteristic path length of these networks - which would result in quicker communication through the network. Applications of these results are then discussed for perimeter security.

  13. Abstract algebra structure and application

    CERN Document Server

    Finston, David R

    2014-01-01

    This text seeks to generate interest in abstract algebra by introducing each new structure and topic via a real-world application. The down-to-earth presentation is accessible to a readership with no prior knowledge of abstract algebra. Students are led to algebraic concepts and questions in a natural way through their everyday experiences. Applications include: Identification numbers and modular arithmetic (linear) error-correcting codes, including cyclic codes ruler and compass constructions cryptography symmetry of patterns in the real plane Abstract Algebra: Structure and Application is suitable as a text for a first course on abstract algebra whose main purpose is to generate interest in the subject, or as a supplementary text for more advanced courses. The material paves the way to subsequent courses that further develop the theory of abstract algebra and will appeal to students of mathematics, mathematics education, computer science, and engineering interested in applications of algebraic concepts.

  14. On Dunkl angular momenta algebra

    Science.gov (United States)

    Feigin, Misha; Hakobyan, Tigran

    2015-11-01

    We consider the quantum angular momentum generators, deformed by means of the Dunkl operators. Together with the reflection operators they generate a subalgebra in the rational Cherednik algebra associated with a finite real reflection group. We find all the defining relations of the algebra, which appear to be quadratic, and we show that the algebra is of Poincaré-Birkhoff-Witt (PBW) type. We show that this algebra contains the angular part of the Calogero-Moser Hamiltonian and that together with constants it generates the centre of the algebra. We also consider the gl( N ) version of the subalge-bra of the rational Cherednik algebra and show that it is a non-homogeneous quadratic algebra of PBW type as well. In this case the central generator can be identified with the usual Calogero-Moser Hamiltonian associated with the Coxeter group in the harmonic confinement.

  15. Free Malcev algebra of rank three

    OpenAIRE

    Kornev, Alexandr

    2011-01-01

    We find a basis of the free Malcev algebra on three free generators over a field of characteristic zero. The specialty and semiprimity of this algebra are proved. In addition, we prove the decomposability of this algebra into subdirect sum of the free Lie algebra rank three and the free algebra of rank three of variety of Malcev algebras generated by a simple seven-dimensional Malcev algebra.

  16. Feedback control design for the complete synchronisation of two coupled Boolean networks

    Science.gov (United States)

    Li, Fangfei

    2016-09-01

    In the literatures, to design state feedback controllers to make the response Boolean network synchronise with the drive Boolean network is rarely considered. Motivated by this, feedback control design for the complete synchronisation of two coupled Boolean networks is investigated in this paper. A necessary condition for the existence of a state feedback controller achieving the complete synchronisation is established first. Then, based on the necessary condition, the feedback control law is proposed. Finally, an example is worked out to illustrate the proposed design procedure.

  17. Characterizing short-term stability for Boolean networks over any distribution of transfer functions

    Science.gov (United States)

    Seshadhri, C.; Smith, Andrew M.; Vorobeychik, Yevgeniy; Mayo, Jackson R.; Armstrong, Robert C.

    2016-07-01

    We present a characterization of short-term stability of Kauffman's N K (random) Boolean networks under arbitrary distributions of transfer functions. Given such a Boolean network where each transfer function is drawn from the same distribution, we present a formula that determines whether short-term chaos (damage spreading) will happen. Our main technical tool which enables the formal proof of this formula is the Fourier analysis of Boolean functions, which describes such functions as multilinear polynomials over the inputs. Numerical simulations on mixtures of threshold functions and nested canalyzing functions demonstrate the formula's correctness.

  18. Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators

    OpenAIRE

    Drucker, Andrew

    2012-01-01

    We study the circuit complexity of Boolean operators, i.e., collections of Boolean functions defined over a common input. Our focus is the well-studied model in which arbitrary Boolean functions are allowed as gates, and in which a circuit's complexity is measured by its depth and number of wires. We show sharp limitations of several existing lower-bound methods for this model. First, we study an information-theoretic lower-bound method due to Cherukhin, that yields bounds of form $\\Omega_d(n...

  19. Vertex Algebras, Kac-Moody Algebras, and the Monster

    Science.gov (United States)

    Borcherds, Richard E.

    1986-05-01

    It is known that the adjoint representation of any Kac-Moody algebra A can be identified with a subquotient of a certain Fock space representation constructed from the root lattice of A. I define a product on the whole of the Fock space that restricts to the Lie algebra product on this subquotient. This product (together with a infinite number of other products) is constructed using a generalization of vertex operators. I also construct an integral form for the universal enveloping algebra of any Kac-Moody algebra that can be used to define Kac-Moody groups over finite fields, some new irreducible integrable representations, and a sort of affinization of any Kac-Moody algebra. The ``Moonshine'' representation of the Monster constructed by Frenkel and others also has products like the ones constructed for Kac-Moody algebras, one of which extends the Griess product on the 196884-dimensional piece to the whole representation.

  20. Testing algebraic geometric codes

    Institute of Scientific and Technical Information of China (English)

    2009-01-01

    Property testing was initially studied from various motivations in 1990’s. A code C  GF (r)n is locally testable if there is a randomized algorithm which can distinguish with high possibility the codewords from a vector essentially far from the code by only accessing a very small (typically constant) number of the vector’s coordinates. The problem of testing codes was firstly studied by Blum, Luby and Rubinfeld and closely related to probabilistically checkable proofs (PCPs). How to characterize locally testable codes is a complex and challenge problem. The local tests have been studied for Reed-Solomon (RS), Reed-Muller (RM), cyclic, dual of BCH and the trace subcode of algebraicgeometric codes. In this paper we give testers for algebraic geometric codes with linear parameters (as functions of dimensions). We also give a moderate condition under which the family of algebraic geometric codes cannot be locally testable.

  1. Combinatorics and commutative algebra

    CERN Document Server

    Stanley, Richard P

    1996-01-01

    Some remarkable connections between commutative algebra and combinatorics have been discovered in recent years. This book provides an overview of two of the main topics in this area. The first concerns the solutions of linear equations in nonnegative integers. Applications are given to the enumeration of integer stochastic matrices (or magic squares), the volume of polytopes, combinatorial reciprocity theorems, and related results. The second topic deals with the face ring of a simplicial complex, and includes a proof of the Upper Bound Conjecture for Spheres. An introductory chapter giving background information in algebra, combinatorics and topology broadens access to this material for non-specialists. New to this edition is a chapter surveying more recent work related to face rings, focusing on applications to f-vectors. Included in this chapter is an outline of the proof of McMullen's g-conjecture for simplicial polytopes based on toric varieties, as well as a discussion of the face rings of such special ...

  2. Real algebraic geometry

    CERN Document Server

    Bochnak, Jacek; Roy, Marie-Françoise

    1998-01-01

    This book is a systematic treatment of real algebraic geometry, a subject that has strong interrelation with other areas of mathematics: singularity theory, differential topology, quadratic forms, commutative algebra, model theory, complexity theory etc. The careful and clearly written account covers both basic concepts and up-to-date research topics. It may be used as text for a graduate course. The present edition is a substantially revised and expanded English version of the book "Géometrie algébrique réelle" originally published in French, in 1987, as Volume 12 of ERGEBNISSE. Since the publication of the French version the theory has made advances in several directions. Many of these are included in this English version. Thus the English book may be regarded as a completely new treatment of the subject.

  3. Topological convolution algebras

    CERN Document Server

    Alpay, Daniel

    2012-01-01

    In this paper we introduce a new family of topological convolution algebras of the form $\\bigcup_{p\\in\\mathbb N} L_2(S,\\mu_p)$, where $S$ is a Borel semi-group in a locally compact group $G$, which carries an inequality of the type $\\|f*g\\|_p\\le A_{p,q}\\|f\\|_q\\|g\\|_p$ for $p > q+d$ where $d$ pre-assigned, and $A_{p,q}$ is a constant. We give a sufficient condition on the measures $\\mu_p$ for such an inequality to hold. We study the functional calculus and the spectrum of the elements of these algebras, and present two examples, one in the setting of non commutative stochastic distributions, and the other related to Dirichlet series.

  4. Operator product expansion algebra

    Energy Technology Data Exchange (ETDEWEB)

    Holland, Jan [CPHT, Ecole Polytechnique, Paris-Palaiseau (France)

    2014-07-01

    The Operator Product Expansion (OPE) is a theoretical tool for studying the short distance behaviour of products of local quantum fields. Over the past 40 years, the OPE has not only found widespread computational application in high-energy physics, but, on a more conceptual level, it also encodes fundamental information on algebraic structures underlying quantum field theories. I review new insights into the status and properties of the OPE within Euclidean perturbation theory, addressing in particular the topics of convergence and ''factorisation'' of the expansion. Further, I present a formula for the ''deformation'' of the OPE algebra caused by a quartic interaction. This formula can be used to set up a novel iterative scheme for the perturbative computation of OPE coefficients, based solely on the zeroth order coefficients (and renormalisation conditions) as initial input.

  5. Testing algebraic geometric codes

    Institute of Scientific and Technical Information of China (English)

    CHEN Hao

    2009-01-01

    Property testing was initially studied from various motivations in 1990's.A code C (∩)GF(r)n is locally testable if there is a randomized algorithm which can distinguish with high possibility the codewords from a vector essentially far from the code by only accessing a very small (typically constant) number of the vector's coordinates.The problem of testing codes was firstly studied by Blum,Luby and Rubinfeld and closely related to probabilistically checkable proofs (PCPs).How to characterize locally testable codes is a complex and challenge problem.The local tests have been studied for Reed-Solomon (RS),Reed-Muller (RM),cyclic,dual of BCH and the trace subcode of algebraicgeometric codes.In this paper we give testers for algebraic geometric codes with linear parameters (as functions of dimensions).We also give a moderate condition under which the family of algebraic geometric codes cannot be locally testable.

  6. ZKBoo: Faster Zero-Knowledge for Boolean Circuits

    DEFF Research Database (Denmark)

    Giacomelli, Irene; Orlandi, Claudio; Madsen, Jesper

    2016-01-01

    In this paper we describe ZKBoo, a proposal for practically efficient zero-knowledge arguments especially tailored for Boolean circuits and report on a proof-of- concept implementation. As an highlight, we can generate (resp. verify) a non-interactive proof for the SHA-1 circuit in approximately 13......ms (resp. 5ms), with a proof size of 444KB. Our techniques are based on the “MPC-in-the-head” approach to zero-knowledge of Ishai et al. (IKOS), which has been successfully used to achieve significant asymp- totic improvements. Our contributions include: ◦ A thorough analysis of the different...... such that y = φ (x)” (where φ is a circuit and y a public value); ◦ A case study, where we provide explicit protocols, implementations and benchmarking of zero-knowledge protocols for the SHA-1 and SHA-256 circuits....

  7. Sampled-Data State Feedback Stabilization of Boolean Control Networks.

    Science.gov (United States)

    Liu, Yang; Cao, Jinde; Sun, Liangjie; Lu, Jianquan

    2016-04-01

    In this letter, we investigate the sampled-data state feedback control (SDSFC) problem of Boolean control networks (BCNs). Some necessary and sufficient conditions are obtained for the global stabilization of BCNs by SDSFC. Different from conventional state feedback controls, new phenomena observed the study of SDSFC. Based on the controllability matrix, we derive some necessary and sufficient conditions under which the trajectories of BCNs can be stabilized to a fixed point by piecewise constant control (PCC). It is proved that the global stabilization of BCNs under SDSFC is equivalent to that by PCC. Moreover, algorithms are given to construct the sampled-data state feedback controllers. Numerical examples are given to illustrate the efficiency of the obtained results.

  8. Complete Boolean Satisfiability Solving Algorithms Based on Local Search

    Institute of Scientific and Technical Information of China (English)

    Wen-Sheng Guo; Guo-Wu Yang; William N.N.Hung; Xiaoyu Song

    2013-01-01

    Boolean satisfiability (SAT) is a well-known problem in computer science,artificial intelligence,and operations research.This paper focuses on the satisfiability problem of Model RB structure that is similar to graph coloring problems and others.We propose a translation method and three effective complete SAT solving algorithms based on the characterization of Model RB structure.We translate clauses into a graph with exclusive sets and relative sets.In order to reduce search depth,we determine search order using vertex weights and clique in the graph.The results show that our algorithms are much more effective than the best SAT solvers in numerous Model RB benchmarks,especially in those large benchmark instances.

  9. An optimal control approach to probabilistic Boolean networks

    Science.gov (United States)

    Liu, Qiuli

    2012-12-01

    External control of some genes in a genetic regulatory network is useful for avoiding undesirable states associated with some diseases. For this purpose, a number of stochastic optimal control approaches have been proposed. Probabilistic Boolean networks (PBNs) as powerful tools for modeling gene regulatory systems have attracted considerable attention in systems biology. In this paper, we deal with a problem of optimal intervention in a PBN with the help of the theory of discrete time Markov decision process. Specifically, we first formulate a control model for a PBN as a first passage model for discrete time Markov decision processes and then find, using a value iteration algorithm, optimal effective treatments with the minimal expected first passage time over the space of all possible treatments. In order to demonstrate the feasibility of our approach, an example is also displayed.

  10. Optimization, Randomized Approximability, and Boolean Constraint Satisfaction Problems

    CERN Document Server

    Yamakami, Tomoyuki

    2011-01-01

    We give a unified treatment to optimization problems that can be expressed in the form of nonnegative-real-weighted Boolean constraint satisfaction problems. Creignou, Khanna, Sudan, Trevisan, and Williamson studied the complexity of approximating their optimal solutions whose optimality is measured by the sums of outcomes of constraints. To explore a wider range of optimization constraint satisfaction problems, following an early work of Marchetti-Spaccamela and Romano, we study the case where the optimality is measured by products of constraints' outcomes. We completely classify those problems into three categories: PO problems, NPO-hard problems, and intermediate problems that lie between the former two categories. To prove this trichotomy theorem, we analyze characteristics of nonnegative-real-weighted constraints using a variant of the notion of T-constructibility developed earlier for complex-weighted counting constraint satisfaction problems.

  11. The Properties of 2-Summable Boolean Function and 3-Summable Boolean Function%可求和布尔函数的性质

    Institute of Scientific and Technical Information of China (English)

    曾利全; 许道云

    2016-01-01

    可求和布尔函数是临界布尔函数判定理论中比较重要的内容之一。该类函数有一个参数k , k表示布尔函数存在k个成真点X1,X2,…Xk和k个成假点Y1,Y2,…Yk ,并且它们的和相等。本文主要研究了n元2-可求和布尔函数和n元3-可求和布尔函数的基本性质。%One of the most important theorem in recognition of threshold function is the k- asummable Boolean function for all k≥2, where k is the number of true point of the Boolean function, say X1,X2,…Xk , and the number of false point of the Boolean function, say, Y1,Y2,…Yk ,such that∑ki=1Xi =∑ki=1Yi . It is shown that the basic properties of 2-summable Boolean function and 3-summable Boolean function.

  12. Algebra of Majorana doubling.

    Science.gov (United States)

    Lee, Jaehoon; Wilczek, Frank

    2013-11-27

    Motivated by the problem of identifying Majorana mode operators at junctions, we analyze a basic algebraic structure leading to a doubled spectrum. For general (nonlinear) interactions the emergent mode creation operator is highly nonlinear in the original effective mode operators, and therefore also in the underlying electron creation and destruction operators. This phenomenon could open up new possibilities for controlled dynamical manipulation of the modes. We briefly compare and contrast related issues in the Pfaffian quantum Hall state.

  13. The Algebra Artist

    Science.gov (United States)

    Beigie, Darin

    2014-01-01

    Most people who are attracted to STEM-related fields are drawn not by a desire to take mathematics tests but to create things. The opportunity to create an algebra drawing gives students a sense of ownership and adventure that taps into the same sort of energy that leads a young person to get lost in reading a good book, building with Legos®,…

  14. Light Cone Current Algebra

    OpenAIRE

    Fritzsch, H.; Gell-Mann, M.

    2003-01-01

    This talk follows by a few months a talk by the same authors on nearly the same subject at the Coral Gables Conference. The ideas presented here are basically the same, but with some amplification, some change of viewpoint, and a number of new questions for the future. For our own convenience, we have transcribed the Coral Gables paper, but with an added ninth section, entitled "Problems of light cone current algebra", dealing with our present views and emphasizing research topics that requir...

  15. Clifford Algebras and Spinors

    International Nuclear Information System (INIS)

    Expository notes on Clifford algebras and spinors with a detailed discussion of Majorana, Weyl, and Dirac spinors. The paper is meant as a review of background material, needed, in particular, in now fashionable theoretical speculations on neutrino masses. It has a more mathematical flavour than the over twenty-six-year-old Introduction to Majorana masses [M84] and includes historical notes and biographical data on past participants in the story. (author)

  16. Algebra & trigonometry II 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 II includes logarithms, sequences and series, permutations, combinations and probability, vectors, matrices, determinants and systems of equations, mathematica

  17. Redesigning linear algebra algorithms

    Energy Technology Data Exchange (ETDEWEB)

    Dongarra, J.J.

    1983-01-01

    Many of the standard algorithms in linear algebra as implemented in FORTRAN do not achieve maximum performance on today's large-scale vector computers. The author examines the problem and constructs alternative formulations of algorithms that do not lose the clarity of the original algorithm or sacrifice the FORTRAN portable environment, but do gain the performance attainable on these supercomputers. The resulting implementation not only performs well on vector computers but also increases performance on conventional sequential computers. 13 references.

  18. Redesigning linear algebra algorithms

    Energy Technology Data Exchange (ETDEWEB)

    Dongarra, J.J.

    1983-01-01

    Many of the standard algorithms in linear algebra as implemented in FORTRAN do not achieve maximum performance on today's large-scale vector computers. In this paper we examine the problem and construct alternative formulations of algorithms that do not lose the clarity of the original algorithm or sacrifice the Fortran portable environment, but do gain the performance attainable on these supercomputers. The resulting implementation not only performs well on vector computers but also increases performance on conventional sequential computers.

  19. Fundamentals of linear algebra

    CERN Document Server

    Dash, Rajani Ballav

    2008-01-01

    FUNDAMENTALS OF LINEAR ALGEBRA is a comprehensive Text Book, which can be used by students and teachers of All Indian Universities. The Text has easy, understandable form and covers all topics of UGC Curriculum. There are lots of worked out examples which helps the students in solving the problems without anybody's help. The Problem sets have been designed keeping in view of the questions asked in different examinations.

  20. Semisimple Metacyclic Group Algebras

    Indian Academy of Sciences (India)

    Gurmeet K Bakshi; Shalini Gupta; Inder Bir S Passi

    2011-11-01

    Given a group of order $p_1p_2$, where $p_1,p_2$ are primes, and $\\mathbb{F}_q$, a finite field of order coprime to $p_1p_2$, the object of this paper is to compute a complete set of primitive central idempotents of the semisimple group algebra $\\mathbb{F}_q[G]$. As a consequence, we obtain the structure of $\\mathbb{F}_q[G]$ and its group of automorphisms.