where "OLDT time" denotes time to construct all support graphs for G. It is the sum of time for OLDT search and time for the topological sorting of the table atoms, but because the latter is part of the former order-wise, 36 we represent "OLDT time" by time for OLDT
search. Also observe that the total size of support graphs does not exceed time for OLDT
search for G order-wise To evaluate OLDT time for a specific class of models such as HMMs, we need to know time for table operations. Observe that our OLDT search in this paper is special in the sense that table atoms are always ground when called and there is no resolution with solved goals. Accordingly a solution table is used only

- to check if a goal G already has an entry in the solution table, i.e. if it was called before, and
- to add a new searched t-explanation for G to the list of discovered t-explanations under G's entry.
The time complexity of these operations is equal to that of table access which depends both on the program and on the implementation of the solution table. 37 We first suppose programs are carefully written in such a way that the arguments of table atoms used as indecies for table access are integers. Actually all programs used in the subsequent complexity analysis ( DB h in Subsection 4.7, DB g and DB g in Subsection 5.3, DB Gr in Subsection 5.5) sssees the contract of the state of the contract to the contract the contract to the contr gers. We also suppose that the solution table is implemented using an array so that table access can be done in O (1) time. 38 In what follows, we present a detailed analysis of the time complexity of the graphical EM algorithm applied to HMMs, PCFGs, pseudo PCSGs and Bayesian networks, assuming O(1) time access to the solution table. We remark by the way that their space complexity is just the total size of solution tables (support graphs).

## 5.2 Hmms

The standard EM algorithm for HMMs is the Baum-Welch algorithm (Rabiner, 1989; Rabiner & Juang, 1993). An example of HMM is shown in Figure 3 in Subsection 4.7.39  Given T observations w 1 , . . , wT of output string of length L , it computes in O( N 2 LT ) time in each iteration the forward probability a t n ( g ) = P ( o 1 o 2 · · o t n -1, q | θ ) and the backward probability β L (q) = P( o L o L +1 …o L | q, θ) for each state q ∈ Q , time step m (1 ≤ m ≤ L )
and a string w t = 0 1 0 2 · · · 0 t (1 ≤ t ≤ T ), where Q is the set of states and N the number of states. The factor N 2 comes from the fact that every state has N possible destinations and