Logic characterisation of p/q-recognisable sets.
Victor Marsault · 2018
Let $\frac{p}{q}$ be a rational number. Numeration in base $\frac{p}{q}$ is defined by a function that evaluates each finite word over $A_p=\{0,1,\ldots,{p-1}\}$ to a rational number in some set $N_{\frac{p}{q}}$. In particular, $N_{\frac{p}{q}}$ contains all integers and the literature on base $\frac{p}{q}$ usually focuses on the set of words that are evaluated to integers; it is a rather chaotic language which is not context-free. On the contrary, we study here the subsets of $(N_{\frac{p}{q}})^d$ that are $\frac{p}{q}$-recognisable, i.e. realised by finite automata over $(A_p)^d$. First, we give a characterisation of these sets as those definable in a first-order logic, similar to the one given by the B\uchi-Bruy\`ere Theorem for integer bases. Second, we show that the order relation and the modulo-$q$ operator are not $\frac{p}{q}$-recognisable.