Specification of extension 2

[dstrueber]

The paper features clear and self-contained specifications for the basis case and extension 1. However, the specification of extension 2 is not self-contained, for example: "outgoing transitions are recalculated" - how precisely are they calcuated?

The paper then just refers to the source code of the reference implementation, leaving it to the contestants to "reverse-engineer" the specification from its implementation (which I find unnecessarily complicated).

I wonder if a specification of the extension can be made available.

[vuducanh1112]

Hi, really sorry for the vague description. We recalculate the probabilities of the outgoing transitions for each state: (1) ignore loops, i.e. ignore transitions from a state to itself (2) also ignore epsilon and empty transitions (3) for all other transitions add all their probabilities to get the new "100%" (4) for all those transitions divide their probabilities by the sum from (3) to get their new probabilities

here an example: Consider a State S and Transitions t = (fromState,ToState,label,probability). Let denote any State that is not S. Suppose S has the Transitions: t1 = (S,S,a,0.6) t2 = (S,,b,0.3) t3 = (S,,c,0.1) After recalculation we get the Transitions: t1 = (S,S,a,0.6) t2 = (S,,b,0.75) t3 = (S,*,c,0.25)

Please note that this simply how we did it for our reference implementation and you are of course free to do the transformation as you like.

hope that helps

[dstrueber]

Thanks, your explanation indeed helped me see how the recalculation at the beginning of the PA-to-SRE conversion works.

My next question concerns the remaining conversion process, in particular, the involved data structures. In Fig. 2, the two shown PAs look different from each other: the transitions in the upper PA each have a label and a probabilty, whereas the transition in the lower PA only has a label (representing the result SRE). I assume that the label was computed during the "label join" step. But what happened to the probability there?

[vuducanh1112]

The probability of the last transition is 1.0, so we omitted it.

[dstrueber]

Ah I see. So there is also a "probability join" step, apart from the label join? Could you illustrate how it works?

[vuducanh1112]

Yes that is correct apart from joining the label we also "join" the probabilities. When we concatenate two labels we multiply their probabilities. When we 'or' two labels we add their probabilities.

So joining probabilities is like walking a probability tree. Walking along a path we multiply all of the probabilities. The probability for two paths is the sum of their probabilities.

Hope that illustrates the idea of how we computed the probabilities along with the labels.

[dstrueber]

Thanks! Your explanation of the probability joining makes sense and clarifies the issue for me.