On the influence of the variable ordering for algorithmic learning using OBDDs

DOI10.1016/J.IC.2005.05.004MaRDI QIDQ2568437zbMATH OpenOpenAlexFDO

Authors Matthias Krause, Petr Savický, Ingo Wegener

Publication date 10 October 2005

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2005.05.004

Mathematics Subject Classification ID

Boolean functions (06E30) Data structures (68P05) Computational learning theory (68Q32)

Recommendations

• The complexity of minimizing and learning OBDDs and FBDDs
• An efficient query learning algorithm for ordered binary decision diagrams
• On the effect of local changes in the variable ordering of ordered decision diagrams
• scientific article; zbMATH DE number 1088264
• Variable orderings and the size of OBDDs for random partially symmetric Boolean functions

Cites work

• Branching Programs and Binary Decision Diagrams
• Communication Complexity
• Cryptographic limitations on learning Boolean formulae and finite automata
• Efficient data structures for Boolean functions
• Graph-Based Algorithms for Boolean Function Manipulation
• scientific article; zbMATH DE number 3908323 (Why is no real title available?)
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 1011685 (Why is no real title available?)
• scientific article; zbMATH DE number 795587 (Why is no real title available?)
• scientific article; zbMATH DE number 795588 (Why is no real title available?)
• Improving the variable ordering of OBDDs is NP-complete
• Learnability and the Vapnik-Chervonenkis dimension
• Occam's razor
• On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs
• Using computational learning strategies as a tool for combinatorial optimization

Cited in

(4)

• An efficient query learning algorithm for ordered binary decision diagrams
• scientific article; zbMATH DE number 1946864 (Why is no real title available?)
• A Machine Learning Based Software Pipeline to Pick the Variable Ordering for Algorithms with Polynomial Inputs
• ON OBDD-BASED ALGORITHMS AND PROOF SYSTEMS THAT DYNAMICALLY CHANGE THE ORDER OF VARIABLES

This page was built for publication: On the influence of the variable ordering for algorithmic learning using OBDDs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2568437)