Efficient algorithms for the transformation between different types of binary decision diagrams

The problem of transforming an FBDD (free binary decision diagram) P on n variables or a pi 'OBDD (ordered binary decision diagram with respect to the variable ordering pi ') P for the Boolean function f into the reduced pi OBDD Q for f is considered. The algorithms run in time O(|P| |Q|lo...

Full description

Saved in:
Bibliographic Details
Published in:Acta informatica 1997-04, Vol.34 (4), p.245-256
Main Authors: Savický, Petr, Wegener, Ingo
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The problem of transforming an FBDD (free binary decision diagram) P on n variables or a pi 'OBDD (ordered binary decision diagram with respect to the variable ordering pi ') P for the Boolean function f into the reduced pi OBDD Q for f is considered. The algorithms run in time O(|P| |Q|log|Q|) (where, e. g, |P| is the size of P) and need space O(|P|+n times |Q|), if P may be an FBDD, or O(|P|+|Q|), if P is known to be an OBDD. The problem is important for the improvement of given variable orderings, e.g., by simulated annealing or genetic algorithms, and in the situation where incompatible representations of functions have to be made compatible.
ISSN:0001-5903
1432-0525
DOI:10.1007/s002360050083