A Dichotomy for k-automatic expansions of Presburger Arithmetic

2025/08/06 by Bell, Jason, Gorman, Alexi Block, Schulz, Chris
#03C64 #03D05 #28A80 #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Logic (math.LO)

paper · doi:10.48550/arxiv.2508.04851

Abstract

Let k≥ 2 and let X be a subset of the natural numbers that is k-automatic and not eventually periodic. We show that a dichotomy holds: either all k-automatic subsets are definable in the expansion of Presburger arithmetic in which we adjoin the predicate X, or (ℕ,+,X)=(ℕ,+,k^ℕ).

Related

• Undefinability of multiplication in Presburger arithmetic with sets of powers
• The complexity of Presburger arithmetic with power or powers
• Distal expansions of Presburger arithmetic by a sparse predicate
• Multi-Dimensional Interpretations of Presburger Arithmetic in Itself
• Bounding quantification in parametric expansions of Presburger\n arithmetic