On 15-17 April, 2024 the University of Gothenburg will host the
2024 edition of its annual Lindström Lectures. The Lindström Lectures is
a distinguished lecture series initiated in 2013 celebrating the memory
of Per (Pelle) Lindström, former (and first)
professor in logic at the University of Gothenburg. For information
about the Lindström lecture series see:
https://www.gu.se/en/flov/the-lindstrom-lectures
Public Lindström Lecture
Monday, 15 April 2024 at 18:00 (UTC+2) at the Faculty of Humanities, University of Gothenburg and over Zoom
Phokion G. Kolaitis (University of California Santa Cruz and IBM Research)
Characterizing Rule-based Languages
Abstract: There is a mature body of work in logic aiming to
characterize logical formalisms in terms of their structural or
model-theoretic properties. The origins of this work can be traced to
Alfred Tarski’s program to characterize metamathematical notions
in “purely mathematical terms” and to Per Lindström’s abstract
characterizations of first-order logic. For the past forty years,
rule-based logical languages have been widely used in databases and in
related areas of computer science to express integrity constraints
and to specify transformations in data management tasks, such as data
exchange and ontology-based data access. The aim of this talk is to
present an overview of more recent results that characterize various
classes of rule-based logical languages in terms
of their structural or model-theoretic properties.
Research Lindström Lecture
Wednesday, 17 April 2024 at 10:00 (UTC+2)
Phokion G. Kolaitis (University of California Santa Cruz and IBM Research)
Homomorphism Counts: Expressive Power and Query Algorithms
Abstract: A classical result by Lovász asserts that two graphs G
and H are isomorphic if and only if they have the same left profile,
that is, for every graph F, the number of homomorphisms from F to G
coincides with the number of homomorphisms from F
to H. A similar result is also known to hold for right profiles, that
is, two graphs G and H are isomorphic if and only if for every graph F,
the number of homomorphisms from G to F coincides with the number of
homomorphisms from H to F. During the past several
years, there has been a study of equivalence relations that are
relaxations of isomorphism obtained by restricting the left profile or
the right profile to suitably restricted classes of graphs, instead of
the class of all graphs. Furthermore, a notion of
a query algorithm based on homomorphism counts was recently introduced
and investigated. The aim of this talk is to present an overview of some
of the main results in this area with emphasis on the differences
between left homomorphism counts and right homomorphism
counts.
The Zoom link and meeting ID:
- Meeting ID: 661 2518 2087
- Passcode: 218237