University of Cambridge > Talks.cam > Logic and Semantics Seminar (Computer Laboratory) > Locally Finite Constraint Satisfaction Problems

Locally Finite Constraint Satisfaction Problems

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Jonathan Hayman.

Many natural computational problems, such as satisfiability and systems of equations, can be expressed in a unified way as constraint satisfaction problems (CSPs). They can be understood as asking whether there is a homomorphism between two relational structures over the same signature. We consider structures whose elements are built of so-called atoms, and defined using finitely many FO formulas. Both the domain and the number of relations of such structures are usually infinite, but thanks to the finite presentation they can be treated as an input for algorithms.

A relational structure T is locally finite is every relation of T is finite. We use recent results in topological dynamics to prove that it is decidable whether there exists a homomorphism from a relational structure A to a locally finite relational structure T. As a corollary, we effectively characterize certain subclasses of CSPs solvable in polynomial time, with applications to descriptive complexity .

Joint work with Bartek Klin, Eryk Kopczyński and Szymon Toruńczyk.

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2020 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity