Queries written in first-order logic can be efficiently processed over the
class of structures having bounded expansion. We have seen that over this class
the problems investigated in this paper can be computed in time linear in the
size of the input structure. The constant factor however is high. The
approach taken here, as well as the ones of [1]}, [2]},
yields a constant factor that is a tower of exponentials whose height depends
on the size of the query. This nonelementary constant factor is unavoidable
already on the class of unranked trees, assuming
FPT\(\ne \) AW\([*]\)  [3]}. In comparison, this factor can be
triply exponential in the size of the query in the bounded degree
case [4]}, [5]}.
