Prediction of area and length complexity measures for binary decision diagrams

Research output: Contribution to journalArticlepeer-review


Measuring the complexity of functions that represent digital circuits in non-uniform computation models is an important area of computer science theory. This paper presents a comprehensive set of machine learnt models for predicting the complexity properties of circuits represented by binary decision diagrams. The models are created using Monte Carlo data for a wide range of circuit inputs and number of minterms. The models predict number of nodes as representations of circuit size/area and path lengths: average path length, longest path length, and shortest path length. The models have been validated using an arbitrarily-chosen subset of ISCAS-85 and MCNC-91 benchmark circuits. The models yield reasonably low RMS errors for predictions, so they can be used to estimate complexity metrics of circuits without having to synthesize them.Keywords: Circuit complexity; Complexity prediction; Area complexity; Path length complexity; Binary decision diagrams; Machine learning; Neural network modeling
Original languageEnglish
Pages (from-to)2864-2873
Number of pages10
JournalExpert Systems with Applications
Issue number4
Publication statusPublished - 2010


Dive into the research topics of 'Prediction of area and length complexity measures for binary decision diagrams'. Together they form a unique fingerprint.

Cite this