BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CSL-TR-75-93
       ENTRY:: December 01, 1994
ORGANIZATION:: Stanford University, Computer Systems Laboratory
       TITLE:: SEQUENTIAL CIRCUIT OUTPUT PROBABILITIES FROM REGULAR
               EXPRESSIONS
        TYPE:: Technical Report
      AUTHOR:: Parker, Kenneth P.
      AUTHOR:: McCluskey, Edward J.
        DATE:: June 1975
       PAGES:: 32
    ABSTRACT:: This paper presents a number of methods for finding
               sequential circuit output probabilities using regular
               expressions. Various classes of regular expressions, based on
               their form, are defined and it is shown how to easily find
               multistep transition probabilities directly from the regular
               expressions. A new procedure for finding steady state
               probabilities is given which proceeds either from a regular
               expression or a state diagram description. This procedure is
               based on the concept of synchronization of the related
               machine, and is useful for those problems where
               synchronization sequences exist. In the cases where these
               techniques can be utilized, substantial savings in
               computation can be realized. Further, application to other
               areas such as multinomial Markov processes is immediate.
       NOTES:: [Adminitrivia V1/Prg/19941201]
         END:: STAN//CSL-TR-75-93