Fall 2016

FO-Definable Constraint Satisfaction Problems

Wednesday, November 9th, 2016 4:00 pm4:30 pm

Add to Calendar

We study infinite CSPs defined by finitely many first-order formulas. We determine the decidability status of FO-definable CSP depending on whether the number of allowed types of constraints or/and number of tuples in each constraint are allowed to be infinite. This is joint work with Bartek Klin, Eryk Kopczynski, Slawek Lasota and Szymon Torunczyk.