On Logics and Homomorphism Closure

From International Center for Computational Logic

Toggle side column
Manuel Bodirsky, Thomas Feller, Simon Knäuer, Sebastian Rudolph
On Logics and Homomorphism Closure
Proceedings of the 36th Annual Symposium on Logic in Computer Science (LICS 2021), to appear
  • KurzfassungAbstract
    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.
  • Projekt:Project: DeciGUTQuantLA
  • Forschungsgruppe:Research Group: Algebra und Diskrete StrukturenComputational Logic
@inproceedings{BFKR2021,
  author    = {Manuel Bodirsky and Thomas Feller and Simon Kn{\"{a}}uer and
               Sebastian Rudolph},
  title     = {On Logics and Homomorphism Closure},
  booktitle = {Proceedings of the 36th Annual Symposium on Logic in Computer
               Science (LICS 2021)},
  year      = {2021}
}