Computer Science – Logic in Computer Science
Scientific paper
2008-09-14
Computer Science
Logic in Computer Science
28 pages. This is an extended long version of a conference paper that appeared at STACS'06. In the third version in the arxiv
Scientific paper
On finite structures, there is a well-known connection between the expressive power of Datalog, finite variable logics, the existential pebble game, and bounded hypertree duality. We study this connection for infinite structures. This has applications for constraint satisfaction with infinite templates. If the template Gamma is omega-categorical, we present various equivalent characterizations of those Gamma such that the constraint satisfaction problem (CSP) for Gamma can be solved by a Datalog program. We also show that CSP(Gamma) can be solved in polynomial time for arbitrary omega-categorical structures Gamma if the input is restricted to instances of bounded treewidth. Finally, we characterize those omega-categorical templates whose CSP has Datalog width 1, and those whose CSP has strict Datalog width k.
Bodirsky Manuel
Dalmau Víctor
No associations
LandOfFree
Datalog and Constraint Satisfaction with Infinite Templates does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Datalog and Constraint Satisfaction with Infinite Templates, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Datalog and Constraint Satisfaction with Infinite Templates will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-156163