  Motivated by the successful application of the theory of regular languages to
formal verification of finite-state systems, there is a renewed interest in
developing a theory of analyzable functions from strings to numerical values
that can provide a foundation for analyzing {\em quantitative} properties of
finite-state systems. In this paper, we propose a deterministic model for
associating costs with strings that is parameterized by operations of interest
(such as addition, scaling, and $\min$), a notion of {\em regularity} that
provides a yardstick to measure expressiveness, and study decision problems and
theoretical properties of resulting classes of cost functions. Our definition
of regularity relies on the theory of string-to-tree transducers, and allows
associating costs with events that are conditional upon regular properties of
future events. Our model of {\em cost register automata} allows computation of
regular functions using multiple "write-only" registers whose values can be
combined using the allowed set of operations. We show that classical
shortest-path algorithms as well as algorithms designed for computing {\em
discounted costs}, can be adopted for solving the min-cost problems for the
more general classes of functions specified in our model. Cost register
automata with $\min$ and increment give a deterministic model that is
equivalent to {\em weighted automata}, an extensively studied nondeterministic
model, and this connection results in new insights and new open problems.
