Learning ordered binary decision diagrams
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...
| Authors: | ; |
|---|---|
| Format: | Report |
| Publication date: | 1995 |
| Country: | España |
| Institution: | Universitat Politècnica de Catalunya (UPC) |
| Repository: | UPCommons. Portal del coneixement obert de la UPC |
| Language: | English |
| OAI Identifier: | oai:upcommons.upc.edu:2117/82261 |
| Online Access: | https://hdl.handle.net/2117/82261 |
| Access Level: | Open access |
| Keyword: | Obdds Ordered binary decision diagrams Àrees temàtiques de la UPC::Informàtica |
| _version_ | 1878737985505067008 |
|---|---|
| author | Gavaldà Mestre, Ricard|||0000-0003-4736-7179 |
| author2 | Guijarro Guillem, David |
| author2_role | author |
| author_browse | Gavaldà Mestre, Ricard|||0000-0003-4736-7179 Guijarro Guillem, David |
| author_facet | Gavaldà Mestre, Ricard|||0000-0003-4736-7179 Guijarro Guillem, David |
| author_role | author |
| collection | UPCommons. Portal del coneixement obert de la UPC |
| description | 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. |
| eu_rights_str_mv | openAccess |
| format | report |
| id | ES_a7e9d665da2d3e2ba0b38ebfff2a11ef |
| institution | Universitat Politècnica de Catalunya (UPC) |
| instname_str | Universitat Politècnica de Catalunya (UPC) |
| language | eng |
| network_acronym_str | ES |
| network_name_str | España |
| oai_identifier_str | oai:upcommons.upc.edu:2117/82261 |
| publishDate | 1995 |
| publishDateSort | 1995 |
| reponame_str | UPCommons. Portal del coneixement obert de la UPC |
| spelling | Learning ordered binary decision diagrams Gavaldà Mestre, Ricard|||0000-0003-4736-7179 Guijarro Guillem, David Obdds Ordered binary decision diagrams Àrees temàtiques de la UPC::Informàtica 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. https://hdl.handle.net/2117/82261 |
| spellingShingle | Learning ordered binary decision diagrams Gavaldà Mestre, Ricard|||0000-0003-4736-7179 Obdds Ordered binary decision diagrams Àrees temàtiques de la UPC::Informàtica |
| title | Learning ordered binary decision diagrams |
| title_full | Learning ordered binary decision diagrams |
| title_fullStr | Learning ordered binary decision diagrams |
| title_full_unstemmed | Learning ordered binary decision diagrams |
| title_short | Learning ordered binary decision diagrams |
| title_sort | Learning ordered binary decision diagrams |
| topic | Obdds Ordered binary decision diagrams Àrees temàtiques de la UPC::Informàtica |
| topic_facet | Obdds Ordered binary decision diagrams Àrees temàtiques de la UPC::Informàtica |
| url | https://hdl.handle.net/2117/82261 |