In my first post I promised to give a polynomial-time procedure to compute the probability that an infinite word (chosen uniformly at random) is accepted by a given unambiguous Büchi automaton. For example, let's take this Büchi automaton again: Let's call the probability x_1, x_2, x_3, depending on the start state: \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} := \begin{pmatrix} \text{Pr(state $1$ accepts a random word)}\\ \text{Pr(state $2$ accepts a random word)}\\ \text{Pr(state $3$ accepts a random word)} \end{pmatrix} I showed in the first post that x_1, x_2, x_3 are nonzero in this example. In order to compute the x_i we set up a linear system of equations and solve it. We have x_1 \ = \ \frac12 \cdot x_{1,a} + \frac12 \cdot x_{1,b}\,, where x_{1,a} and x_{1,b} denote the (conditional) probabilities that state 1 accepts a random word, under the condition that the word starts with a and b, respectively. x_{1,b} = 0 because state $...
Blog by Oxford computer scientist Stefan Kiefer