On the complexity of analysis and manipulation of Boolean functions in terms of decision graphs
type: Item
instance of: scholarly article
title: On the complexity of analysis and manipulation of Boolean functions in terms of decision graphs
zbMATH Open document ID: 0803.68049
DOI: 10.1016/0020-0190(94)00048-4
author: Jordan Gergov
author: Christoph Meinel
published in: Information Processing Letters
publication date: 1994-07-21T00:00:00Z
review text: One of the fundamental problems in computer-aided circuit design is the task of representing logic functions. Although, in principle, any valid representation is allowed, some representations may be preferred because they are more efficient in memory, more efficient to manipulate, or more indicative of the complexity of the final implementation. The search of an optimal trade-off between these competing objectives -- succinct representation of Boolean functions and feasible manipulation algorithms -- is a central theme of computer-aided logic synthesis. One candidate which seems to satisfy these two conditions is the concept of decision graphs or branching programs. The paper reports results of a systematic inspection of the computational complexity of basic tasks of Boolean manipulation such as satisfiability, tautology test, equivalence test, and binary Boolean synthesis in terms of different restricted types of branching programs.
reviewed by: Christoph Meinel
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68U07
Mathematics Subject Classification ID: 68P10
zbMATH DE Number: 609771
zbMATH Keywords: CAD
zbMATH Keywords: data structures
zbMATH Keywords: BDD
zbMATH Keywords: efficient algorithms
zbMATH Keywords: computer-aided circuit design
zbMATH Keywords: Boolean functions
zbMATH Keywords: computer-aided logic synthesis
zbMATH Keywords: decision graphs
zbMATH Keywords: branching programs
zbMATH Keywords: Boolean manipulation
MaRDI profile type: Publication
full work available at URL: 0020-0190(94)00048-4
OpenAlex ID: W1972591946
cites work: Binary Decision Diagrams
cites work: Equivalence of free Boolean graphs can be decided probabilistically in polynomial time
cites work: On the size of binary decision diagrams representing Boolean functions
cites work: Graph-Based Algorithms for Boolean Function Manipulation
cites work: Q4037091
cites work: Q4160379
cites work: Q4198056
cites work: Q5628016
cites work: Modified branching programs and their computational power
cites work: Q4005192
description: scientific article; zbMATH DE number 609771