On minimal expansions in redundant number systems: Algorithms and quantitative analysis

We consider digit expansions in base q greater than or equal to 2 with arbi trary integer digits such that the length of the expansion plus the sum of the absolute values of the digits is minimal. Since this does not determine a unique minimal representation, we describe some reduced minimal expansio ns. We completely characterize its syntactical properties, give a simple algori thm to compute the reduced minimal expansion and a formula to compute a sin gle digit without having to compute the others, and we calculate the averag e cost of such an expansion.