  Predicate logic is the premier choice for specifying classes of relational
structures. Homomorphisms are key to describing correspondences between
relational structures. Questions concerning the interdependencies between these
two means of characterizing (classes of) structures are of fundamental interest
and can be highly non-trivial to answer. We investigate several problems
regarding the homomorphism closure (homclosure) of the class of all (finite or
arbitrary) models of logical sentences: membership of structures in a
sentence's homclosure; sentence homclosedness; homclosure characterizability in
a logic; normal forms for homclosed sentences in certain logics. For a wide
variety of fragments of first- and second-order predicate logic, we clarify
these problems' computational properties.
