An optimal Gaifman normal form construction for structures of bounded degree

This paper's main result presents a $3$-fold exponential algorithm that transforms a first-order formula $\varphi$ together with a number $d$ into a formula in Gaifman normal form that is equivalent to $\varphi$ on the class of structures of degree at most~$d$. For structures of polynomial growth, we even get a $2$-fold exponential algorithm. These results are complemented by matching lower bounds: We show that for structures of degree $2$, a $2$-fold exponential blow-up in the size of formulas cannot be avoided. And for structures of degree $3$, a $3$-fold exponential blow-up is unavoidable. As a result of independent interest we obtain a $1$-fold exponential algorithm which transforms a given first-order sentence~$\varphi$ of a very restricted shape into a sentence in Gaifman normal form that is equivalent to $\varphi$ on all structures.

Authors

• Lucas Heimberg
• Dietrich Kuske
• Nicole Schweikardt

Keywords

No keywords are indexed for this paper.