  Additive Cost Register Automata (ACRA) map strings to integers using a finite
set of registers that are updated using assignments of the form "x := y + c" at
every step. The corresponding class of additive regular functions has multiple
equivalent characterizations, appealing closure properties, and a decidable
equivalence problem. In this paper, we solve two decision problems for this
model. First, we define the register complexity of an additive regular function
to be the minimum number of registers that an ACRA needs to compute it. We
characterize the register complexity by a necessary and sufficient condition
regarding the largest subset of registers whose values can be made far apart
from one another. We then use this condition to design a PSPACE algorithm to
compute the register complexity of a given ACRA, and establish a matching lower
bound. Our results also lead to a machine-independent characterization of the
register complexity of additive regular functions. Second, we consider
two-player games over ACRAs, where the objective of one of the players is to
reach a target set while minimizing the cost. We show the corresponding
decision problem to be EXPTIME-complete when costs are non-negative integers,
but undecidable when costs are integers.

Formal Languages and Automata Theory