## Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 2864-2873 |

Number of pages | 10 |

Journal | Expert Systems with Applications |

Volume | 37 |

Issue number | 4 |

DOIs | |

Publication status | Published - Apr 2010 |

## Keywords

- Area complexity
- Binary decision diagrams
- Circuit complexity
- Complexity prediction
- Machine learning
- Neural network modeling
- Path length complexity

## ASJC Scopus subject areas

- General Engineering
- Computer Science Applications
- Artificial Intelligence