|
NeuroCOLT
Technical Report NC-TR-95-050
Learning
Ordered Binary Decision Diagrams
Ricard
Gavaldą and David Guijarro
Universitat Politecnica de Catalunya
Abstract
This note studies the learnability of ordered binary decision
diagrams (obdds). We give a polynomial-time algorithm using membership
and equivalence queries that finds the minimum obdd for the target
respecting a given ordering. We also prove that both types of queries
and the restriction to a given ordering are necessary if we want minimality
in the output, unless P=NP. If learning has to occur with respect
to the optimal variable ordering, polynomial-time learnability implies
the approximability of two NP-hard optimization problems: the problem
of finding the optimal variable ordering for a given obdd and the
Optimal Linear Arrangement problem on graphs.
Download Compressed
Postscript
|