Title:
|
Learning ordered binary decision diagrams
|
Author:
|
Gavaldà Mestre, Ricard; Guijarro Guillem, David
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació |
Abstract:
|
We study 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. |
Subject(s):
|
-Àrees temàtiques de la UPC::Informàtica -Obdds -Ordered binary decision diagrams |
Rights:
|
|
Document type:
|
Article - Published version Report |
Share:
|
|