TITLE: Estimating Shortest Circuit Path Length Complexity

AUTHORS: Azam Beg, P. W. Chandana Prasad, and S.M.N.A. Senenayake

PUBLICATION/VENUE: International Journal of Intelligent Systems and Technologies (IJIST), vol. 3, no. 3, Jun 2008, pp. 133-138.


When binary decision diagrams are formed from uniformly distributed Monte Carlo data for a large number of variables, the complexity of the decision diagrams exhibits a predictable relationship to the number of variables and minterms. In the present work, a neural network model has been used to analyze the pattern of shortest path length for larger number of Monte Carlo data points. The neural model shows a strong descriptive power for the ISCAS benchmark data with an RMS error of 0.102 for the shortest path length complexity. Therefore, the model can be considered as a method of predicting path length complexities; this is expected to lead to minimum time complexity of very large-scale integrated circuitries and related computer-aided design tools that use binary decision diagrams.


CITATIONS: Google | Yahoo