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.
The 2024 Lindström Lectures were delivered in April 2024 by Phokion Kolaitis, Distinguished Research Professor at UC Santa Cruz and a Principal Research Staff Member at the IBM Almaden Research Center, US.
The Public Lindström Lecture was held on Monday, 15 April 2024 at the Faculty of Humanities of Gothenburg University and online. The Research Lecture was delived on Wednesday, 17 April 2024. at the Department of Philosohy, Linguistics and Theory of Science.
See below for information about the talks. Further information about the Lindstrom Lectures are available on the GU page about the lectures.
-
Public Lindström Lecture: Phokion G. Kolaitis (University of California Santa Cruz and IBM Research)
Characterizing Rule-based Languages
-
Research Lindström Lecture: Phokion G. Kolaitis (University of California Santa Cruz and IBM Research)
Homomorphism Counts: Expressive Power and Query Algorithms
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.