Manuel Bodirsky
Datalog and Constraint Satisfaction with Infinite Templates
With Victor Dalmau. Journal on Computer and System Sciences 79 (2013), pp. 79-100. An extended abstract appeared in the proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science (STACS06), Marseille, LNCS 3884, pages 646-659, Springer Verlag.
Abstract
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 for whether 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 tree-width. Finally, we prove universal-algebraic characterizations of those omega-categorical templates whose CSP has Datalog width 1, and for those whose CSP has strict Datalog width k.
Download
Download: the journal version of this paper is available at arxiv.org/abs/0809.2386.
