  A data word is a sequence of pairs of a letter from a finite alphabet and an
element from an infinite set, where the latter can only be compared for
equality. To reason about data words, linear temporal logic is extended by the
freeze quantifier, which stores the element at the current word position into a
register, for equality comparisons deeper in the formula. By translations from
the logic to alternating automata with registers and then to faulty counter
automata whose counters may erroneously increase at any time, and from faulty
and error-free counter automata to the logic, we obtain a complete complexity
table for logical fragments defined by varying the set of temporal operators
and the number of registers. In particular, the logic with future-time
operators and 1 register is decidable but not primitive recursive over finite
data words. Adding past-time operators or 1 more register, or switching to
infinite data words, cause undecidability.
