and also an alphabet from {a, b} to emit. Note that to specify a fact set Fh and the associated distribution compactly, we introduce here a new notation values(i,[v1,...,vm]). It declares that F h contains msw atoms of the form msw(i,n,v) (v E {v1,..., vm}) whose distribution is P (i,n) given by (7) in Subsection 4.2. For example, (f3), values(tr(_),[s0,s1])
introduces msw(tr(t),n,v) atoms into the program such that t can be any ground term, v E {s0,s1} and for a ground term n, they have a distribution P(tr(t),n)(msw(tr(t),n,s0) = x,msw(tr(t),n,s1) = y | 0i,s0,0i,s1) = 0i,s00i,s1 where i = tr(t), x,yE {0,1} and x + y = 1.

This program runs like a Prolog program. For a non-ground top-goal ~ hmm(S), it functions as a stochastic string generator returning a list of alphabets such as [a,b,a] in the variable S as follows. The top-goal calls clause ( h1 ) and ( h1 ) selects the initial state by executing subgoal msw(init,once,Si) 33 which returns in Si an initial state probabilistically chosen from {s0, s1}. The second clause (h2) is called from (h1) with ground S and ground T. It makes a probabilistic choice of an output alphabet C by asking msw(out(S),T,C) and then determines NextS , the next state, by asking msw(tr(S),T,NextS). (h3) is there to stop the transition. For simplicity, the length of output strings is fixed to three. This way of execution is termed as sampling execution because it corresponds to a random sampling from PpB,,. If the top-goal is ground like ~ hmm([a,b,a]), it works as an acceptor, i.e. returning success (yes) or failure (no).

If all explanations for hmm([a,b,a]) are sought for, we keep all msw atoms resolved upon during the refutation as a conjunction (explanation), and repeat this process by backtracking until no more refutation is found. If we need t-explanations however, backtracking must be abandoned because sharing of partial explanations through t-explanations, the purpose of t-explanations itself, becomes impossible. We therefore instead use OLDT search for all t1:
top_hmm(Cs,Ans):- tab_hmm(Cs,Ans, []).

t2:
tab_hmm(Cs,[hmm(Cs)|X],X):- hmm(Cs,_,[]).

t3:
tab_hmm(T,S,Cs,[hmm(T,S,Cs)|X],X):- hmm(T,S,Cs,_,[]).

t4:
e_msw(init,T,s0,[msw(init,T,s0)|X],X).

t4': e_msw(init,T,s1,[msw(init,T,s1)|X],X).

hmm(Cs,X0,X1):- e_msw(init,once,Si,X0,X2), tab_hmm(1,Si,Cs,X2,X1).

t7:
t8:
hmm(T,S,[C|Cs],X0,X1):-
T=<3, e_msw(out(S),T,C,X0,X2), e_msw(tr(S),T,NextS,X2,X3), T1 is T+1, tab_hmm(T1,NextS,Cs,X3,X1).

hmm(T,S,[],X,X):- T>3.

t9:
Figure 5: Translated program of DB h