Datalog and constraint satisfaction with infinite templates

Mostra el registre complet Registre parcial de l'ítem

• dc.contributor.author Bodirsky, Manuel
• dc.contributor.author Dalmau, Víctor
• dc.date.accessioned 2019-01-22T09:10:47Z
• dc.date.available 2019-01-22T09:10:47Z
• dc.date.issued 2013
• dc.description.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 Γ is ω-categorical, we present various equivalent characterizations of those Γ such that the constraint satisfaction problem (CSP) for Γ can be solved by a Datalog program. We also show that can be solved in polynomial time for arbitrary ω-categorical structures Γ if the input is restricted to instances of bounded treewidth. Finally, we characterize those ω-categorical templates whose CSP has Datalog width 1, and those whose CSP has strict Datalog width k.en
• dc.description.sponsorship The first author has received funding from the European Research Council under the European Community’s Seventh Framework Programme (FP7/2007-2013 Grant Agreement No. 257039). Supported by the MICINN through grant TIN2010-20967-C04-02.
• dc.format.mimetype application/pdf
• dc.identifier.citation Bodirsky M, Dalmau V. Datalog and constraint satisfaction with infinite templates. J Comput Syst Sci. 2013 Feb;79(1):79-100. DOI: 10.1016/j.jcss.2012.05.012
• dc.identifier.doi http://dx.doi.org/10.1016/j.jcss.2012.05.012
• dc.identifier.issn 0022-0000
• dc.identifier.uri http://hdl.handle.net/10230/36351
• dc.language.iso eng
• dc.publisher Elsevier
• dc.relation.ispartof Journal of Computer and System Sciences. 2013 Feb;79(1):79-100
• dc.relation.projectID info:eu-repo/grantAgreement/EC/FP7/257039
• dc.relation.projectID info:eu-repo/grantAgreement/ES/3PN/TIN2010-20967-C04-02
• dc.rights © Elsevier http://dx.doi.org/10.1016/j.jcss.2012.05.012
• dc.rights.accessRights info:eu-repo/semantics/openAccess
• dc.subject.keyword Logic in computer science
• dc.subject.keyword Computational complexity
• dc.subject.keyword Constraint satisfaction
• dc.subject.keyword Datalog
• dc.subject.keyword Countably categorical structures
• dc.title Datalog and constraint satisfaction with infinite templates
• dc.type info:eu-repo/semantics/article
• dc.type.version info:eu-repo/semantics/acceptedVersion