Open Collections

On applications of homogeneous structures in computer science

Banff International Research Station for Mathematical Innovation and Discovery

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.

Mathematics; Combinatorics; Dynamical systems and ergodic theory; Logic and foundations

video/mp4

Author affiliation: TU Dresden

2016-05-14

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/58145

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/