POPL 2027
Sun 10 - Sat 16 January 2027 Mexico City, Mexico

Buchi arithmetic on a fixed integer $k\geq 2$ is the first-order theory of the structure $(\Z; 0, 1, +, V_k, \leq)$, where the binary relation $V_k(x,y)$ is true if and only if $y$ is the greatest power of $k$ dividing $x$. By the Buchi-Bruyere theorem, this theory completely describes the sets of integers that are recognizable by finite automata when encoded in the $k$-ary positional number system.

Motivated by recent advances in symbolic automata, in this paper we study expressivity and decidability problems for Buchi arithmetic with a \emph{parametric positional encoding}, where $k$ is treated as a variable rather than a fixed constant. We show that this \emph{parametric} Buchi arithmetic provides a logical characterization of a class of \emph{parametric symbolic automata} over Linear Integer Arithmetic (LIA), thus extending the Buchi-Bruyere theorem to the parametric setting. As a corollary, we obtain that, for every first-order sentence $\varphi_t$ (parametric in $t$) in the language of $(\Z; 0, 1, +, V_t, \leq)$, the set of bases $k \geq 2$ where $\varphi_k$ is true is ultimately periodic.

At a technical level, the original Buchi-Bruyere theorem translates finite automata to the $\exists^\forall^$ fragment of Buchi arithmetic, while our proof translates parametric symbolic automata to the $\exists^\forall^\exists^$ fragment of parametric Buchi arithmetic. We trace this discrepancy in the number of quantifier alternations to the use of the map $x \mapsto k \cdot x$ multiplying a natural number by the fixed base $k$, whose parametric counterpart $x \mapsto t \cdot x$ is not definable in parametric Buchi arithmetic. Indeed, we show that given a $\exists^\forall^*$ sentence $\varphi_t$ in the language of ${(\Z; 0, 1, +, x \mapsto t \cdot x, V_t, \leq)}$, the existence of a base $k\geq 2$ such that $\varphi_k$ is true is an undecidable problem.

Finally, we provide a prototype implementation of both parametric and standard symbolic automata, and experiments on problems that ask to decide whether a formula is satisfied \emph{for all (or for some) bases $k \geq 2$} in an input segment $[\alpha..\beta]$. These experiments indicate that parametric symbolic automata are more efficient when the range of bases is large, or so is $\alpha$.