Article

Free access

Functional approaches to generating orderings for efficient symbolic representations

Authors:

M. R. Mercer,

R. Kapur,

D. E. RossAuthors Info & Claims

DAC '92: Proceedings of the 29th ACM/IEEE Design Automation Conference

Pages 624 - 627

Published: 01 July 1992 Publication History

PDF eReader

References

[1]

C.L. Berman, "Circuit width, register allocation, and reduced function graphs," IBM Res. Rep. RC 14127, Nov. 1988.

Google Scholar

[2]

C.L. Berman, "Ordered Binary Decision Diagrams and Circuit Structure," Extended Abstract, Proc. international Conference Computer Design, Oct. 1989, pp. 392-395.

Google Scholar

[3]

K.S. Brace, R.E. Bryant and R.L. Rudell, "Efficient implementation of a BDD package," Proc. A CM/IEEE PTth Design Automation Conf., Jun. 1990, pp. 40-45.

Digital Library

Google Scholar

[4]

F. Brglez and H. Fujiwara, "A neutral netlist of 10 combinational benchmark circuits and a target translator in FORTRAN," Proc. IEEE International Symposium on Circuits and Systems (ISCAS), Jun. 1985, pp. 695-698.

Google Scholar

[5]

R.E. Bryant, "Graph-based algorithms for Boolean function manipulation," IEEE Transactions on Computers, Vol C-35, No. 8, Aug. 1986, pp. 677-692.

Digital Library

Google Scholar

[6]

R.E. Bryant, "On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication," IEEE Transactions on Computers, Vol. C-40, No. 2, Feb. 1991, pp. 205-213.

Digital Library

Google Scholar

[7]

K.M. Butler, D.E. Ross, R. Kaput and M.R. Mercer, "Heuristics to compute variable orderings for efficient manipulation of ordered binary decision diagrams," Proc. ACM-IEEE P8th Design Automation Conference, Jun. 1991, pp. 417-420.

Digital Library

Google Scholar

[8]

S.J. Friedman and K.J. Supowit, "Finding the optimal variable ordering for binary decision diagrams," IEEE Trans. on Comput., vol C-39, no. 5, May 1990, pp. 710-713. see also Proc. A CM. IEEE 24th Design Automation Conference, Jun. 1987, pp. 348-356.

Digital Library

Google Scholar

[9]

M. Fujita, H. Fujisawa and N. Kawato, "Evaluation and improvements of Boolean comparison method based on binary decision diagrams," Dig. Technical Papers, International Conference on CAD, Nov. 1988, pp. 2-5.

Google Scholar

[10]

M. Fujita, Y. Matunaga and T. Kakuda, "On the variable ordering for binary decision diagrams for the application of multilevel logic synthesis," Proceedings of the European Design Automation Conference, Feb. 1991, pp. 50-54.

Digital Library

Google Scholar

[11]

N. Ishiura, H. Sawada and S. Yajima, "Minimization of binary decision diagrams based on exchange of variables," Proc. International Conference of Computer-Aided Design, Nov. 1991, pp. 472-475.

Google Scholar

[12]

S. Malik, A.R. Wang, R.K. Brayton and A. Sangiovanni-Vincentelli, "Logic verification using binary decision diagrams in a logic synthesis environment," Dig. Technical Papers, International Conference on CAD, Nov. 1988, pp. 6-9.

Google Scholar

[13]

S. Minato, N. Ishiura and S. Yajima, "Shared Binary Decision Diagram with attributed edges for efficient Boolean function manipulation," Proc. 27th A CM/IEEE Deszgn Automation Conference, Jun. 1990, pp. 52-57.

Digital Library

Google Scholar

[14]

D.E. Ross, "Functional calculations using ordered partial multi decision diagrams," Ph.D. Dissertation, The University of Texas at Austin, Aug. 1990.

Digital Library

Google Scholar

[15]

D.E. Ross, K.M. Butler, R. Kapur and M.R. Mercer, "Fast Functional Evaluation of Candidate OBDD Variable Orderings," Proceedings of the European Design Automation Conference, Feb. 1991, pp. 4-10.

Digital Library

Google Scholar

Cited By

View all

Grumberg OLivne SMarkovitch S(2003)Learning to order BDD variables in verificationJournal of Artificial Intelligence Research10.5555/1622420.162242318:1(83-116)Online publication date: 1-Jan-2003
https://dl.acm.org/doi/10.5555/1622420.1622423
Schmiedle FDrechsler NGroße DDrechsler R(2002)Heuristic Learning Based on Genetic ProgrammingGenetic Programming and Evolvable Machines10.1023/A:10209889259233:4(363-388)Online publication date: 1-Dec-2002
https://dl.acm.org/doi/10.1023/A%3A1020988925923
Harlow JBrglez FYasuura H(1998)Design of experiments in BDD variable orderingProceedings of the 1998 IEEE/ACM international conference on Computer-aided design10.1145/288548.289103(646-652)Online publication date: 1-Nov-1998
https://dl.acm.org/doi/10.1145/288548.289103
Show More Cited By

Index Terms

Functional approaches to generating orderings for efficient symbolic representations

Recommendations

Learning Magnitudes of Energy Consumption with Symbolic or Iconic Representations
Diagrammatic Representation and Inference
Abstract
Learning about the magnitude of energy consumption is crucial for responsible energy management in today’s society. This study investigates the use of symbolic and iconic representations for learning and mentally comparing the energy consumption ...
Set Manipulation with Boolean Functional Vectors for Symbolic Reachability Analysis
DATE '03: Proceedings of the conference on Design, Automation and Test in Europe - Volume 1

Symbolic techniques usually use characteristic functions for representing sets of states. Boolean functional vectors provide an alternate set representation which is suitable for symbolic simulation. Their use in symbolic reachability analysis and model ...
Fast functional evaluation of candidate OBDD variable orderings
EURO-DAC '91: Proceedings of the conference on European design automation

Symbolic simulation via Ordered Binary Decision Diagrams (OBDDs) is becoming more feasible each year. These representations are often very efficient under an appropriate ordering of the variables of the functions represented. Recently, heuristics for ...

Comments

Information & Contributors

Information

Published In

DAC '92: Proceedings of the 29th ACM/IEEE Design Automation Conference

July 1992

752 pages

ISBN:089791516X

Chairman:
Daniel G. Schweikert
Cadence Design Systems, Inc., San Jose, CA

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 July 1992

Check for updates

Qualifiers

Article

Conference

DAC92

Sponsor:

EDAC
SIGDA
IEEE-CAS
IEEE-CS

DAC92: The 29th ACM/IEEE-CS Design Automation Conference

June 8 - 12, 1992

California, Anaheim, USA

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
155
Total Downloads

Downloads (Last 12 months)28
Downloads (Last 6 weeks)4

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Grumberg OLivne SMarkovitch S(2003)Learning to order BDD variables in verificationJournal of Artificial Intelligence Research10.5555/1622420.162242318:1(83-116)Online publication date: 1-Jan-2003
https://dl.acm.org/doi/10.5555/1622420.1622423
Schmiedle FDrechsler NGroße DDrechsler R(2002)Heuristic Learning Based on Genetic ProgrammingGenetic Programming and Evolvable Machines10.1023/A:10209889259233:4(363-388)Online publication date: 1-Dec-2002
https://dl.acm.org/doi/10.1023/A%3A1020988925923
Harlow JBrglez FYasuura H(1998)Design of experiments in BDD variable orderingProceedings of the 1998 IEEE/ACM international conference on Computer-aided design10.1145/288548.289103(646-652)Online publication date: 1-Nov-1998
https://dl.acm.org/doi/10.1145/288548.289103
Jain JAdams WFujita MYasuura H(1998)Sampling schemes for computing OBDD variable orderingsProceedings of the 1998 IEEE/ACM international conference on Computer-aided design10.1145/288548.289099(631-638)Online publication date: 1-Nov-1998
https://dl.acm.org/doi/10.1145/288548.289099
Kamhi GFix LYasuura H(1998)Adaptive variable reordering for symbolic model checkingProceedings of the 1998 IEEE/ACM international conference on Computer-aided design10.1145/288548.289054(359-365)Online publication date: 1-Nov-1998
https://dl.acm.org/doi/10.1145/288548.289054
Drechsler RDrechsler NGünther WChawla BBryant RRabaey J(1998)Fast exact minimization of BDDsProceedings of the 35th annual Design Automation Conference10.1145/277044.277099(200-205)Online publication date: 1-May-1998
https://dl.acm.org/doi/10.1145/277044.277099
Wang YMcCrosky C(1998)Solving Boolean Equations Using ROSOP FormsIEEE Transactions on Computers10.1109/12.66376347:2(171-177)Online publication date: 1-Feb-1998
https://dl.acm.org/doi/10.1109/12.663763
Falkowski BChang C(1997)Forward and Inverse Transformations Between Haar Spectra and Ordered Binary Decision Diagrams of Boolean FunctionsIEEE Transactions on Computers10.1109/12.64430146:11(1272-1279)Online publication date: 1-Nov-1997
https://dl.acm.org/doi/10.1109/12.644301
Bollig BWegener I(1996)Improving the Variable Ordering of OBDDs Is NP-CompleteIEEE Transactions on Computers10.1109/12.53712245:9(993-1002)Online publication date: 1-Sep-1996
https://dl.acm.org/doi/10.1109/12.537122
Reddy SKunz WPradhan DPreas B(1995)Novel verification framework combining structural and OBDD methods in a synthesis environmentProceedings of the 32nd annual ACM/IEEE Design Automation Conference10.1145/217474.328705(414-419)Online publication date: 1-Jan-1995
https://dl.acm.org/doi/10.1145/217474.328705
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Learning Magnitudes of Energy Consumption with Symbolic or Iconic Representations

Set Manipulation with Boolean Functional Vectors for Symbolic Reachability Analysis

Fast functional evaluation of candidate OBDD variable orderings

Comments

Published In

Sponsors

Publisher

Publication History

Check for updates

Qualifiers

Conference

Acceptance Rates

Upcoming Conference

Other Metrics

Article Metrics

Other Metrics

Cited By

PDF

eReader

Login options

Full Access

References

Cited By

Index Terms

Recommendations

Learning Magnitudes of Energy Consumption with Symbolic or Iconic Representations

Set Manipulation with Boolean Functional Vectors for Symbolic Reachability Analysis

Fast functional evaluation of candidate OBDD variable orderings

Comments

Information

Published In

Sponsors

Publisher

Publication History

Check for updates

Qualifiers

Conference

Acceptance Rates

Upcoming Conference

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations