Symbolic algorithms to calculate steady-state probabilities of a finite state machine
- 1 January 1994
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 214-218
- https://doi.org/10.1109/edtc.1994.326875
Abstract
In this paper we present two symbolic algorithms to compute the steady-state probabilities for very large finite state machines. These algorithms, based on Algebraic Decision Diagrams (ADD's)/spl minus/an extension of BDDs that allows arbitrary values to be associated with the terminal nodes of the diagrams/spl minus/determine the steady-state probabilities by regarding finite state machines as homogeneous, discrete-parameter Markov chains with finite state spaces, and by solving the corresponding Chapman-Kolmogorov equations. We have implemented two solution techniques: one is based on the Gauss-Jacobi iteration, and the other one on simple matrix multiplication, we report the experimental results obtained for problems with over 10/sup 8/ unknowns in irreducible form.Keywords
This publication has 4 references indexed in Scilit:
- Combinational profiles of sequential benchmark circuitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Synchronizing sequences and symbolic traversal techniques in test generationJournal of Electronic Testing, 1993
- Algebraic decision diagrams and their applicationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1993
- Spectral transforms for large boolean functions with applications to technology mappingPublished by Association for Computing Machinery (ACM) ,1993