An optimal Gaifman normal form construction for structures of bounded degree

Nicole Schweikardt (joint work with Lucas Heimberg and Dietrich Kuske)

This talk presents a 3-fold exponential algorithm that transforms a first-order formula \phi together with a number d into a formula in Gaifman normal form that is equivalent to \phi 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 \phi of a very restricted shape into a sentence in Gaifman normal form that is equivalent to \phi on all structures.