Pao-Ta Yu and Rong-Chung Chen
Institute of Computer Science and Information Engineering
National Chung Cheng University
Chiayi, Taiwan 62107, R.O.C.
Stack neural networks (SNNs) are based on positive Boolean functions (PBFs) as their nonlinear threshold operators, which are conventionally represented by positive Boolean expressions with a large number of minterms or maxterms in their representations on average. Therefore, a new representation to represent the PBF is needed such that the computational capability of stack neural networks can be improved based on this new representation or data structure.
In this paper, a fundamental class of PBFs, called associative positive Boolean functions (APBFs), is proposed as a basic set of PBFs such that we can represent PBFs via an appropriate combination from this basic set. This fundamental class is the largest subclass of PBFs which can be represented by the maximum stacking vector representation. This new representation only requires O(n) memory space to store its data structure, where n is the number of input Boolean variables. Therefore, this new representation provides an efficient approach to storing PBFs in an associative memory style. Furthermore, the retrieval operation of stack neural networks based on this new data structure is developed in a very simple and efficient manner. Finally, some significant operations generated from this new representation are proposed to extend the operating capability of APBFs.
Keywords: stack neural networks, positive Boolean function, threshold decompostion, stacking property, MSV, APBF, meet, join
Received July 28, 1995; revised May 10, 1996.
Communicated by Wen-Hsiang Tsai.
*This work was partially supported by National Science Council of R.O.C. under grant NSC 881-0408-E-194-503.