Quantifier elimination with floor functions for parametric Presburger arithmetic

Let R=Z[t]R=\Z[t] and X=NX=\N. Define

LR=LRgα(t):αR,\mathcal{L}'_R=\mathcal{L}_R\cup\\{g_{\alpha(t)}:\alpha\in R\\},

where each gα(t)g_{\alpha(t)} is interpreted by

gα(t)(x)=maxqZ:qα(t)x,g_{\alpha(t)}(x)=\max\\{q\in\Z:q\cdot|\alpha(t)|\leq x\\},

with gα(t)(x)=0g_{\alpha(t)}(x)=0 when α(t)=0\alpha(t)=0. Quantifier-elimination conjecture. Every LR\mathcal{L}_R-formula is logically equivalent to a quantifier-free formula in LR\mathcal{L}'_R. The paper presents this as a suggestion motivated by related work, and the supplied text gives no resolution status.

Sources & referencesView supporting material

Primary source

John Goodrick, “Bounding quantification in parametric expansions of Presburger arithmetic”, arXiv:1604.06166 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.