New Algorithms for the Simple Temporal Problem
Léon Planken · Research Repository (Delft University of Technology) · 2008
List of Figures v* Rational weights can easily be recast as integer weights by multiplying each with the least common denominator.Real-valued weights are outside the scope of this discussion; as Schwalb and Dechter note [SD97], rational weights always suffice in practice.* This was proven independently by Neil Immerman [Imm88] and Róbert Szelepcsényi[Sze87] in 1987, for which they shared the 1995 Gödel prize.† Consider a class M of Turing machines with three tapes: read-only, write-only and readwrite; the latter is logarithmically bounded, the others are unbounded.The reduction is valid only if it can be carried out by a Turing machine from M.* The alternative, log w max ∈ O(log log w max ), is clearly useless.