  Deterministic one-way time-bounded multi-counter automata are studied with
respect to their ability to perform reversible computations, which means that
the automata are also backward deterministic and, thus, are able to uniquely
step the computation back and forth. We study the computational capacity of
such devices and obtain separation results between irreversible and reversible
k-counter automata for superpolynomial time. For exponential time we obtain
moreover an infinite and tight hierarchy with respect to the number of
counters. This hierarchy is shown with Kolmogorov complexity and
incompressibility arguments. In this way, on passing we can prove this
hierarchy also for ordinary counter automata. This improves the known hierarchy
for ordinary counter automata in the sense that here we consider a weaker
acceptance condition. Then, it turns out that k+1 reversible counters are not
better than k ordinary counters and vice versa. Finally, almost all usually
studied decidability questions turn out to be undecidable and not even
semidecidable for reversible multi-counter automata, if at least two counters
are provided.
