Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-09T03:59:06.889Z Has data issue: false hasContentIssue false
  • English
  • Français

The Decomposition Tree for analyses of Boolean functions

Published online by Cambridge University Press:  01 April 2008

MAIK FRIEDEL ,
SWETLANA NIKOLAJEWA  and
THOMAS WILHELM
MAIK FRIEDEL
Affiliation:
Biocomputing Group, Fritz Lipmann Institute (FLI), Beutenbergstr. 11, D-07745 Jena, Germany Email: maikfr@fli-leibniz.de
SWETLANA NIKOLAJEWA
Affiliation:
Department of Bioinformatics, Friedrich Schiller University Jena, Ernst-Abbe-Platz 2, D-07743 Jena, Germany
THOMAS WILHELM
Affiliation:
Theoretical Systems Biology, Institute of Food Research, Norwich Research Park, Norwich NR4 7UH, United Kingdom Email: Thomas.Wilhelm@bbsrc.ac.uk
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We present a new data structure, called a Decomposition Tree (DT), for analysing Boolean functions, and demonstrate a variety of applications. In each node of the DT, appropriate bit-string decomposition fragments are combined by a logical operator. The DT has 2k nodes in the worst case, which implies exponential complexity for problems where the whole tree has to be considered. However, it is important to note that many problems are simpler. We show that these can be handled in an efficient way using the DT. Nevertheless, many problems are of exponential complexity and cannot be made any simpler: for example, the calculation of prime implicants. Using our general DT structure, we present a new worst case algorithm to compute all prime implicants. This algorithm has a lower time complexity than the well-known Quine–McCluskey algorithm and is the fastest corresponding worst case algorithm so far.

Information

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 18 , Issue 2 , April 2008 , pp. 411 - 426
Copyright
Copyright © Cambridge University Press 2008

References

Andersen, H. R. (1997) An introduction to binary decision diagrams, Course Notes available at http://www.itu.dk/~hra/notes-index.html.Google Scholar
Benini, L. and de Micheli, G. (1997) A Survey of Boolean Matching Techniques for Library Binding. ACM Transactions on Design Automation of Electronic Systems 2 (9)193–226.CrossRefGoogle Scholar
Bollig, B. and Wegener, I. (1996) Improving the variable ordering of OBDDs is NP-complete. IEEE Trans. Comp. 45 993–1002.Google Scholar
Boyar, J., Peralta, R. and Pochuev, D. (2000) On the muliplicative complexity of Boolean functions over the basis (∧,⊕,1). Theoretical Computer Science 235 43–57.Google Scholar
Bryant, R. E. (1992) Symbolic Boolean manipulation with ordered binary decision diagrams, School of Computer Science, Carnegie Mellon, Pittsburgh.Google Scholar
Brayton, R., Hachtel, G., McMullen, C. and Sangiovanni-Vincentelli, A. (1984) Logic Minimization Algorithms for VLSI Synthesis, Kluwer.Google Scholar
Brayton, R. (1992) Symbolic Boolean manipulation with ordered binary-decision diagrams. ACM Computing surveys 24 (3)293–318.Google Scholar
Bshouty, N. and Tamon, C. (1996) On the Fourier spectrum of monotone functions. J. ACM 43 (4)747–770.Google Scholar
Chung, K. S. and Liu, C. L. (1998) Local transformation techniques for multi-level logic circuits utilizing circuit symmetries for power reduction. Proceedings of International Symposium on Low Power Electronics and Design 215–220.Google Scholar
Clote, P. and Kranakis, E. (2002) Boolean Functions and Computation Models, Springer Verlag.Google Scholar
Coudert, O. (1994) Two-level logic minimization: an overview. Integration 17 (2)97–140.CrossRefGoogle Scholar
Crama, Y. and Hammer, P. L. (2006) Boolean Functions – Theory Algorithms and Applications. In preparation. Available at http://www.rogp.hec.ulg.ac.be/Crama/.Google Scholar
Dutuit, Y. and Rauzy, A. (1997) Exact and truncated computations of prime implicants of coherent and non-coherent fault trees within Aralia. Reliab. Eng. Syst. Safety 58 127–144.Google Scholar
Forbus, K. and de Kleer, J. (1992) Building problem solvers, MIT Press.Google Scholar
Hirose, S. and Ikeda, K. (1994) Nonlinearity criteria of Boolean functions. KUIS Technical Report KUIS-94-0002, Kyoto University, Japan.Google Scholar
Jeong, S. W., Kim, T. S. and Somenzi, F. (1993) An efficient method for optimal BDD ordering computation. In: Proc. International Conference on VLSI and CAD, Taejon, Korea.Google Scholar
Kauffman, S. (2000) Investigation, Oxford University Press.Google Scholar
De Kleer, J., Mackworth, A. and Reiter, R. (1993) Characterizing diagnoses and systems. Artificial Intelligence 59 63–67.Google Scholar
Klüver, J. and Schmidt, J. (1999) Topology Metric and Dynamics of Social Systems. Journal of Artificial Societies and Social Simulation 2.Google Scholar
Makino, K. and Ibaraki, T. (1997) The maximum latency and identification of positive Boolean functions. SIAM J. Comput. 26 (5)1363–1383.Google Scholar
McCluskey, E. J. (1956) Minimization of Boolean functions. Bell System Technical Journal 35 1417–1444.Google Scholar
McGeer, P. C., Sanghavi, J. V., Brayton, R. K. and Sangiovanni-Vincentelli, A. L. (1993) Espresso-Signature: A New Exact Minimizer for Logic Functions. Design Automation Conference 618–624.Google Scholar
Mohnke, J. and Malik, S. (1993) Permutation and phase independent Boolean comparison. Integration 16 102–129.CrossRefGoogle Scholar
Nikolajewa, S., Friedel, M. and Wilhelm, T. (2007) Boolean Networks with biologically relevant rules show ordered behavior. BioSystems 90 (1)40–47.Google Scholar
Quine, J. O. W. (1952) The Problem of Simplifying Truth Functions. American Math. Monthly 59 521–531.Google Scholar
Preneel, B., Govaerts, R. and Vandewalle, J. (1991) Cryptographic properties of quadratic Boolean functions. In : Abstracts of the 1st International Conference on Finite Fields and Applications.Google Scholar
Reiter, R. and De Kleer, J. (1987) Foundations of Assumption-based Truth Maintenance Systems: Preliminary Report. AAAI-87, Seattle, Washington 183–189.Google Scholar
Rudell, R. (1985) Espresso software program, Computer Science Dept., University of California, Berkeley.Google Scholar
Szallasi, Z. and Liang, S. (1998) Modeling the Normal and Neoplastic Cell Cycle With Realistic Boolean Genetic Networks: Their Application for Understanding Carcinogenesis and Assessing Therapeutic Strategies. In: Pacific Symp. on Biocomputing 3 66–76.Google Scholar
Shmulevich, I., Lähdesmäki, H. and Egiazarian, K. (2004) Spectral Methods for Testing Membership in Certain Post Classes and the Class of Forcing Functions. IEEE Signal Processing Letters 11 (2)289–292.Google Scholar
Strzemecki, T. (1992) Polynomial-time algorithms for generation of prime implicants. Journal of Complexity 8 37–63.Google Scholar
Wang, Y., McCrosky, C. and Song, X. (2001) Single-faced Boolean Functions and their Minimization. Computer Journal 44 (4)280–291.Google Scholar
Wegener, I. (2000) Branching Programs and Binary Decision Diagrams – Theory and Application, SIAM Monographs on Discrete Mathematics and Applications.Google Scholar
Wegener, I. (1987) The Complexity of Boolean Functions, Wiley.Google Scholar
Wegener, I. (1989) Effiziente Algorithmen für grundlegende Funktionen, B. G. Teubner.Google Scholar
Wendt, P., Coyle, E. and Gallagher, N. (1986) Stack Filters. IEEE Trans. Acoustics Speech Signal Process 34 (4)898–911.CrossRefGoogle Scholar