joint work with Joanna Ochremiak, Bartek Klin and Eryk Kopczyński

Speaker(s)

Szymon Toruńczyk

Affiliation

Uniwersytet Warszawski

Date

Feb. 11, 2015, 2:15 p.m.

Room

room 5870

Title in Polish

Orbit-finite Constraint Satisfaction Problems

Seminar

Seminar Automata Theory

---

We study extensions of the classical Constraint Satisfaction Problem, to the orbit-finite setting. In one direction, we allow the instances to be orbit-finite, while preserving a finite template. We show that the problem remains decidable (where orbit-finite instances are represented by formulas), and we provide tight complexity bounds. In another direction, we extend the classical setting by keeping the instances finite and allowing the templates to be orbit-finite over an orbit-finite signature, which consists of finite relations. We show that most of the classical complexity results lift to this setting.

---