BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

On applications of homogeneous structures in computer science Bodirsky, Manuel


Homogeneous structures and their reducts have been used as templates of Constraint Satisfaction Problems (CSPs) to model qualitative reasoning problems in Artificial Intelligence. But this is not the only context in which homogeneous structures arise naturally in CS; we will discuss more recent links between homogeneous structures and permutation pattern avoidance classes, and between homogeneous structures and automata theory (for data word languages). I will present a fragment of existential second-order logic such that the queries that can be formulated in this logic describe (finite unions of) CSPs for reducts of homogeneous structures. This logic is quite powerful and contains MMSNP and most CSPs that have been studied in temporal and spatial reasoning.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International