The Countably Infinite Boolean Vector Space and Constraint Satisfaction Problems

Datum

04.09.2015

Zeit

13:15 - 14:15

Sprecher

Francois Bossiere

Sprache

en

Hauptthema

Mathematik

Andere Themen

Mathematik

Host

Jun.-Prof. Dr. Martin Schneider

Beschreibung

Given a relational structure Gamma, the problem CSP(Gamma) takes as an argument a primitive positive sentence phi and asks whether Gamma satisfies phi. Let (V ; +) be the countably infinite vector space over the two-element field. A first-order definable structure over (V ; +) with domain V is called a reduct of (V ; +). This talk presents a method combining universal algebra, model theory and Ramsey theory in order to classify the complexity of CSPs over reducts of (V ; +). Besides establishing P/NP-complete dichotomy results for the complexity of the CSPs for nearly every reduct of (V ; +), this approach yields on the way an algebraic description of the lattices of automorphism groups and monoids of self-embeddings of reducts of (V ; +). A sizeable part of the lattice of endomorphism monoids of reducts of (V ; +) is then described. Lastly, endomorphism monoids of model-complete cores of reducts of (V ; +) are fully classfiied, foraying toward a dichotomy classication result for CSPs.

Links

• Institut für Algebra: International Seminar

Letztmalig verändert: 15.09.2015, 18:28:52