Dense-choice Counter Machines revisited

This paper clarifies the picture about Dense-choice Counter Machines (DCM), a less studied version of Counter Machines where counters range on a dense, rather than discrete, domain. The definition of DCM is revisited to make it extend (discrete) Counter Machines, and new undecidability and decidability results are proved. Using the first-order additive mixed theory of reals and integers, the paper presents a logical characterization of the sets of configurations reachable by reversal-bounded DCM. We also relate the DCM model to more common models of systems.