  Decidability of the determinization problem for weighted automata over the
semiring $(\mathbb{Z} \cup {-\infty}, \max, +)$, WA for short, is a
long-standing open question. We propose two ways of approaching it by
constraining the search space of deterministic WA: k-delay and r-regret. A WA N
is k-delay determinizable if there exists a deterministic automaton D that
defines the same function as N and for all words {\alpha} in the language of N,
the accepting run of D on {\alpha} is always at most k-away from a maximal
accepting run of N on {\alpha}. That is, along all prefixes of the same length,
the absolute difference between the running sums of weights of the two runs is
at most k. A WA N is r-regret determinizable if for all words {\alpha} in its
language, its non-determinism can be resolved on the fly to construct a run of
N such that the absolute difference between its value and the value assigned to
{\alpha} by N is at most r.
  We show that a WA is determinizable if and only if it is k-delay
determinizable for some k. Hence deciding the existence of some k is as
difficult as the general determinization problem. When k and r are given as
input, the k-delay and r-regret determinization problems are shown to be
EXPtime-complete. We also show that determining whether a WA is r-regret
determinizable for some r is in EXPtime.
