Probabilistic Analysis of Large Finite State Machines

G. D. Hachtel, E. Macii, A. Pardo and F. Somenzi

Proceedings of the Design Automation Conference, pp. 270-275, June, 1994, San Diego, CA.

Abstract

Regarding finite state machines as Markov chains facilitates the application of probabilistic methods to very large logic synthesis and formal verification problems. Recently, we have shown how symbolic algorithms based on Algebraic Decision Diagrams may be used to calculate the steady-state probabilities of finite state machines with more than 108 states. These algorithms treated machines with state graphs composed of a single terminal strongly connected component. In this paper we consider the most general case of systems which can be modeled as state machines with arbitrary transition structures. The proposed approach exploits structural information to decompose and simplify the state graph of the machine.

Click here to download the compressed postscript version.

BibTeX Entry

@InProceedings{Hachte94c,
        ADDRESS = "San Diego, CA" ,
        AUTHOR = "G. D. Hachtel and E. Macii and A. Pardo and F. Somenzi" ,
        BOOKTITLE = "Proceedings of the Design Automation Conference", 
        MONTH =   jun  ,
        PAGES = "270-275" ,
        TITLE = "Probabilistic Analysis of Large Finite State Machines" ,
        YEAR = "1994"
        }
Return to the home page