On the expressiveness of Büchi arithmetic

We show that the existential fragment of B¨uchi arithmetic is strictly less expressive than full B¨uchi arithmetic of any base, and moreover establish that its Σ2-fragment is already expressively complete. Furthermore, we show that regular languages of polynomial growth are definable in the existent...