On Logics and Homomorphism Closure

Manuel BodirskyManuel Bodirsky, Thomas FellerThomas Feller, Simon KnäuerSimon Knäuer, Sebastian RudolphSebastian Rudolph

ISBN: 978-1-6654-4895-6
Download
Slides
DOI Link

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), 1-13, 2021. IEEE

Details
Bibtex

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.
Weitere Informationen unter:Further Information: Link
Projekt:Project: DeciGUT, QuantLA
Forschungsgruppe:Research Group: Algebra und Diskrete StrukturenAlgebra and Discrete Structures, Computational LogicComputational 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)},
  publisher = {IEEE},
  year      = {2021},
  pages     = {1-13},
  doi       = {10.1109/LICS52264.2021.9470511}
}