Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Learning ordered binary decision diagrams

Autor
Gavaldà, R.; Guijarro, D.
Tipus d'activitat
Document cientificotècnic
Data
1995-03
Repositori
http://hdl.handle.net/2117/82261 Obrir en finestra nova
Resum
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...
Citació
Gavaldà, R., Guijarro, D. "Learning ordered binary decision diagrams". 1995.
Grup de recerca
LARCA - Laboratori d'Algorísmia Relacional, Complexitat i Aprenentatge

Participants

Arxius