On applications of homogeneous structures in computer science

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.Non UBCUnreviewedAuthor affiliation: TU DresdenFacult