Characterizing Simpler Recognizable Sets of Integers

摘要

For a given numeration system U, a set X of integers is said to be U-star-free if the language of the normalized U-representations of the elements in X is star-free. Adapting a result of McNaughton and Papert, we give a first-order logical characterization of these sets for various numeration systems including integer base systems and the Fibonacci system. For k-ary systems, the problem of the base dependence of this property is also studied. Finally, the case of k-adic systems is developed.