Representing Boolean Functions by Decision Trees

Igor Chikalov

Research output: Contribution to journalArticlepeer-review

Abstract

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.
Original languageEnglish (US)
Pages (from-to)41-60
Number of pages20
JournalAverage Time Complexity of Decision Trees
Volume21
DOIs
StatePublished - 2011

ASJC Scopus subject areas

  • Library and Information Sciences
  • General Computer Science
  • Information Systems and Management

Fingerprint

Dive into the research topics of 'Representing Boolean Functions by Decision Trees'. Together they form a unique fingerprint.

Cite this