Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
436357 | Theoretical Computer Science | 2014 | 15 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Florent Bouchy, Alain Finkel, Pierluigi San Pietro,