COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

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

## Locally Finite Constraint Satisfaction ProblemsAdd to your list(s) Download to your calendar using vCal - Joanna Ochremiak, University of Warsaw
- Friday 15 May 2015, 14:00-15:00
- Computer Laboratory, William Gates Building, Room FW11.
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. ## This talk is included in these lists:- All Talks (aka the CURE list)
- Cambridge talks
- Computer Laboratory talks
- Computer Laboratory, William Gates Building, Room FW11
- Computing and Mathematics
- Interested Talks
- Logic and Semantics Seminar (Computer Laboratory)
- School of Technology
- Trust & Technology Initiative - interesting events
- bld31
- yk373's list
Note that ex-directory lists are not shown. |
## Other listsOne Day Meeting - 6th Annual Symposium of the Cambridge Computational Biology Institute cuscrs Contagion and Containment## Other talksThe interpretation of black hole solutions in general relativity Anthropological engineering and hominin dietary ecology Lipschitz Global Optimization Insight into the molecular mechanism of extracellular matrix calcification in the vasculature from NMR spectroscopy and electron microscopy CANCELLED DUE TO STRIKE ACTION Recent advances in understanding climate, glacier and river dynamics in high mountain Asia |