RAO Yanyi, ZHANG Xianda. The Characterizations of Hyper-Star Graphs Induced by Linearly Separable Boolean Functions[J]. Chinese Journal of Electronics, 2018, 27(1): 19-25. doi: 10.1049/cje.2017.08.015
Citation: RAO Yanyi, ZHANG Xianda. The Characterizations of Hyper-Star Graphs Induced by Linearly Separable Boolean Functions[J]. Chinese Journal of Electronics, 2018, 27(1): 19-25. doi: 10.1049/cje.2017.08.015

The Characterizations of Hyper-Star Graphs Induced by Linearly Separable Boolean Functions

doi: 10.1049/cje.2017.08.015
  • Received Date: 2016-03-14
  • Rev Recd Date: 2016-06-02
  • Publish Date: 2018-01-10
  • A hyper-star is a graph consisting of the union of some hypercubes with at least one common vertex. The graph induced by a linearly separable Boolean function is a hyper-star. We obtain some properties of hyper-stars and give a decomposition algorithm of a hyperstar. We give a determination condition for a hyper-star. The determination condition yields an algorithm of constructing all hyper-stars of n vertices in time O(n3).
  • loading
  • S.T. Hu, Mathematical Theory of Switching Circuits and Automata, University of California Press, Berkeley, USA, 1968.
    S. Muroga, Logic Design and Switching Theory, WileyInterscience, New York, USA, 1979.
    M. Anthony, "Discrete mathematics of neural networks:Selected topics", SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, USA, 2001.
    M. Anthony, Y. Crama and P. Hammer, "Neural networks and Boolean functions", Boolean Models and Methods in Mathematics, Computer Science and Engineering, Cambridge University Press, New York, USA, pp.577-595, 2010.
    M.O. Ball and J.S. Provan, Disjoint Products and Efficient Computation of Reliability, Operations Research, pp.703-715, 1988.
    K.G. Ramamurthy, Coherent Structure and Simple Games, Kluwer Academic Publishers, Dordrecht, Netherland, 1990.
    P.D. Straffin, Game Theory and Strategy, The Mathematical Association of America, Washington D.C., USA, 1993.
    T.M. Cover, "Geometric and statistical properties of systems of linear inequalities with applications in pattern recognition", IEEE Transactions on Electronic Computers, Vol.EC-14, No.3, pp.326-334, 2006.
    Y. Crama and P. Hammer, Boolean Functions, Cambridge University Press, New York, USA, 2011.
    N. Gruzling, "A linear separability of the vertices of an ndimensional hypercube", Master Thesis, University of British Columbia, Canada, 2006.
    S. Muroga, I. Toda and M. Kondo, "Majority decision functions of up to six variables", Mathematics of Computation, Vol.16, No.80, pp.459-472, 1962.
    S. Muroga, T. Tsuboi and C.R. Baugh, "Enumeration of threshold functions of eight variables", IEEE Transactions on Computers, Vol.19, No.9, pp.818-825, 1970.
    P.C. Ojha, "Enumeration of threshold functions from the lattice of hyperplane intersections", IEEE Transactions on Neural Networks, Vol.11, No.4, pp.839-850, 2000.
    Yu. A. Zuev, "Asymptotics of the logarithm of the number of threshold functions of the algebra of logic", Soviet Mathematics Doklady, Vol.39, No.3, pp.512-513, 1989.
    S. Muroga, S. Takasu and I. Toda, "Theory of majority decision elements", Journal of the Franklin Institute, Vol.271, pp.376-418, 1961.
    M.C. Paull and E.J. McCluskey, "Boolean functions realizable with a single threshold device", Proc. of IRE, pp.1335-1337, 1960.
    R.O. Winder, "Single stage threshold logic", Proc. of IEEE Symposium on Switching Circuit Theory and Logical Design, pp.321-332, 1961.
    C.K. Chow, "Boolean functions realizable with single threshold devices", Proc. of IRE, Vol.49, pp.370-371, 1961.
    C.C. Elgot, "Truth functions realizable by single threshold organs", Proc. of IEEE Symposium on Switching Circuit Theory and Logical Design, pp.225-245, 1961.
    R.O. Winder, "Threshold logic", Ph.D.Thesis, Princeton University, USA, 1962.
    U.N. Peled and B. Simeone, "Polynomial-time algorithms for regular set-covering and threshold synthesis", Discrete Applied Mathematics, Vol.12, pp.309-323, 1985.
    K. Matulef, R. O'Donnell, R. Rubinfeld, et al., "Testing halfspaces", Proc. of 20th Annual Symposium on Discrete Algorithms, Vol.39, pp.2004-2047, 2009.
    T. Gowda, S. Vrudhula, N. Kulkarni, et al., "Identification of threshold functions and synthesis of threshold networks", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol.30, No.5, pp.665-677, 2011.
    R.O. Winder, "Enumeration of seven-argument threshold functions", IEEE Transactions on Electronic Computers, Vol.ec-14, No.3, pp.315-325, 1965.
    V.V. Podolskii, "Perceptrons of large weight", Problems of Information Transmission, Vol.45, No.1, pp.46-53, 2009.
    V.V. Podolskii, "Lower bound on weights of large degree threshold functions", Logical Methods in Computer Science, Vol.9, No.2, pp.1-17, 2013.
    M. Anthony, "Partitioning points by parallel planes", Discrete Mathematics, Vol.282, No.2, pp.17-21, 2004.
    S. Ghilezan, J. Pantovic and J. Zunić, "Separating points by parallel hyperplanes-characterization problem", IEEE Transactions on Neural Networks, Vol.18, No.5, pp.1356-1363, 2007.
    K.S. Kobylkin, "Lower bounds for the number of hyperplanes separating two finite sets of points", Proceedings of the Steklov Institute of Mathematics, Vol.289, No.S1, pp.126-138, 2015.
    L. Franco, "Generalization ability of Boolean functions implemented in feedforward neural networks", Neurocomputing, Vol.70, No.1-3, pp.351-361, 2006.
    L. Franco and M. Anthony, "The influence of oppositely classified examples on the generalization complexity of Boolean functions", IEEE Transactions on Neural Networks, Vol.17, No.3, pp.578-590, 2006.
    Z. Chao, Y. Jie and W. Wei, "Binary higher order neural networks for realizing Boolean functions", IEEE Transactions on Neural Networks, Vol.22, No.5, pp.701-713, 2011.
    L. Zhang and K. Zhang, "Controllability and observability of Boolean control networks with time-variant delays in states", IEEE Transactions on Neural Networks and Learning Systems, Vol.24, No.9, pp.1478-1484, 2013.
    H. Zhang, H. Tian, Z. Wang, et al., "Synchronization analysis and design of coupled Boolean networks Based on periodic switching sequences", IEEE Transactions on Neural Networks and Learning Systems, Vol.27, No.12, pp.2754-2759, 2016.
    D. Cheng, H. Qi and Z. Li, "Model construction of Boolean network via observed data", IEEE Transactions on Neural Networks and Learning Systems, Vol.22, No.4, pp.525-536, 2011.
    S. Muroga, Threshold Logic and Its Applications, WileyInterscience, New York, USA, 1971.
    Y. Rao and X. Zhang, "Characterization of linearly separable Boolean functions:A graph-theoretic perspective", IEEE Transactions on Neural Networks and Learning Systems, Vol.28, No.7, pp.1542-1549, 2017.
    B.D. Mckay, "Nauty user's guide (version 1.5)", Technical Report TR-CS-90-02, Computer Science Department, Australian National University, Canberra, Australia, 1990.
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (131) PDF downloads(214) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return