Characterizing simpler recognizable sets of integers (Q1826937)

The paper contributes to the area of characterizing recognizable sets of integers. One of the sources for the work was the well-known result by Mc Naughton and Papert which characterizes star-free languages (a proper subclass of regular languages) as those expressible in the first-order theory of linear order. Here the author considers sets of (nonnegative) integers as languages, containing representations of the integers in a (linear) numeration system (which includes the usual \(k\)-base systems or the Fibonacci system). A set of numbers \(X\) is \(U\)-recognizable (\(U\) being a numeration system) if the set of \(U\)-representations of elements of \(X\) is regular. The author recalls a nice result by Bruyere and Hansel showing that \(U\)-recognizability coincides with \(U\)-definability, for a certain class of numeration systems \(U\) (where the characteristic polynomial is the minimal polynomial of a Pisot number). Inspired by the mentioned sources, the author concentrates on star-free sets, and develops special logics \({\mathcal L}_{k,n}\), which characterize when a given set \(X\) is \(k\)-star-free (i.e., w.r.t. the integer base \(k\)). He then generalizes the obtained result for the above mentioned class of ``Pisot number numeration systems''. Further results are given for \(k\)-ary systems (in particular, the base dependence question is studied) and for \(k\)-adic systems.