A Generalization of Cobham’s Theorem to Automata over Real Numbers

Abstract. This paper studies the expressive power of finite-state automata recognizing sets of real numbers encoded positionally. It is known that the sets that are definable in the first-order additive theory of real and integer variables 〈R, Z, +, < 〉 can all be recognized by weak deterministic Büchi automata, regardless of the encoding base r> 1. In this paper, we prove the reciprocal property, i.e., that a subset of R that is recognizable by weak deterministic automata in every base r> 1 is necessarily definable in 〈R, Z, +, <〉. This result generalizes to real numbers the well-known Cobham’s theorem on the finite-state recognizability of sets of integers. Our proof gives interesting insight into the internal structure of automata recognizing sets of real numbers, which may lead to efficient data structures for handling these sets.