## 5 Efficiency and Finity of Computations  
One may notice that the incremental computation performed by Algorithm _Incremental_ has a potential for being rather wasteful. In fact, of all the time steps that may have been potentially identified for addition, step 7 only takes one, essentially disregarding other requests for the addition of time steps that, if satisfied, could speed up the process rather substantially. In particular, it is not difficult to see that the number of iterations of the while loop is bound to be proportional to the length of the trajectory returned, which is undesirable when long trajectories are computed. Additionally, one should note that action descriptions that contain durative fluents may sometimes yield infinite trajectories. To see how this may happen, consider fluents \(f\), \(g\) and the corresponding information:  
1. \(f\) and \(g\) are default fluents;
2. if \(f\) holds, then \(g\) holds for a duration of \(n\) units of time;
3. if \(g\) is false, then \(f\) holds. Suppose that \(f\) is observed to hold at step 0. Statement 2 causes \(g\) to hold until time step \(n\). At step \(n+1\), \(g\) defaults to false and the condition of statement 3 becomes satisfied, causing \(f\) to hold. Again, item 2 causes \(g\) to hold until time step \((n+1)+n=2n+1\). At step \(2n+2\), \(g\) defaults to false again and statement 3 causes \(f\) to hold. The same occurs again at \(3n+3\). It is not difficult to see that the process repeats indefinitely, producing an infinite trajectory. Correspondingly, the Algorithm _Incremental_ will yield infinite computations in these cases. Central to overcoming this issue is the following simple but important observation on Algorithm _Incremental_:  
Theorem 3.2: _Let \(\hat{m}\) be the value of \(m\) at step 7 of Incremental during a certain iteration of the while loop. At every subsequent iteration, the value of \(m\) is guaranteed to be no smaller than \(\hat{m}\)._  
This property motivated the development of _Incremental\({}^{h}\)_ (Algorithm 3), shown below. _Incremental\({}^{h}\)_ aims at reducing the number of iterations necessary to compute a trajectory (at least in the average case) by taking into account a larger portion of the requests for the introduction of new time steps. Additionally, the algorithm takes as input an additional parameter \(h\), which acts as a time horizon for the computation. Intuitively, the new algorithm terminates when all requests for new time steps at a given iteration are for time steps greater than \(h\). Theorem 3.2 ensures that no requests for time steps smaller than \(h\) are missed in doing so. The intuition is as follows. The algorithm takes as input a set of pre-determined time steps, e.g., corresponding to time steps that a user or external application would like to query about or about which observations are provided. Step 2 produces the grounding, \(G\), of _base_, \(p\), and \(timedep(0)\). Due to the fact that \(p\) defines the pre-determined time steps, ground instances of the rules of \(timedep(0)\), which are time-dependent, are generated. Ground instances of external \(enabled(T)\) are also generated for every time step defined by \(p\). Recall that externals are false by default: step 3 changes this by asserting all externals from \(G\) true via the corresponding clingo primitive. At step 4, the answer set \(A\) of \(G\) is computed. If \(A\) does not contain any request for new time steps, then \(A\) encodes the complete trajectory that _Incremental_ aims at computing. Thus, all that is left is to ground \(output\) incrementally (step 22) and return the answer set of the updated grounding (step 23). On the other hand, if the answer set computed at step 4 contains requests for new times steps, then those requests need to be satisfied. Recall that the introduction of a new time step may affect the calculation of the state of the domain at the time steps that follow it. For this reason, the algorithm must retract all rules that are related to those time steps.