Datalog and constraint satisfaction with infinite templates

DOI10.1016/J.JCSS.2012.05.012MaRDI QIDQ1936249zbMATH OpenOpenAlexFDO

Authors Manuel Bodirsky, Víctor Dalmau

Publication date 21 February 2013

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2012.05.012

zbMATH Keywords

computational complexityconstraint satisfactioncountably categorical structuresDataloglogic in computer science

Mathematics Subject Classification ID

Logic in computer science (03B70) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Datalog and Constraint Satisfaction with Infinite Templates
• Temporal constraint satisfaction problems in fixed-point logic
• Constraint Satisfaction Problems with Infinite Templates
• The collapse of the bounded width hierarchy
• Linear Datalog and Bounded Path Duality of Relational Structures

Cited in

(35)

• Maximal infinite-valued constraint languages
• Constants and finite unary relations in qualitative constraint reasoning
• Using model theory to find decidable and tractable description logics with concrete domains
• ASNP: a tame fragment of existential second-order logic
• On a stronger reconstruction notion for monoids and clones
• Emptiness problems for distributed automata
• Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
• The collapse of the bounded width hierarchy
• The inference problem for template dependencies
• \(n\)-permutability and linear Datalog implies symmetric Datalog
• A dichotomy for first-order reducts of unary structures
• The language of stratified sets is confluent and strongly normalising
• A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
• Why are CSPs based on partition schemes computationally hard?
• Temporal constraint satisfaction problems in fixed-point logic
• Rewritability in monadic disjunctive Datalog, MMSNP, and expressive description logics
• Datalog and Constraint Satisfaction with Infinite Templates
• Dualities for Constraint Satisfaction Problems
• Constraint Satisfaction Problems with Infinite Templates
• The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
• The algebraic structure of the densification and the sparsification tasks for CSPs
• Solving infinite-domain CSPs using the patchwork property
• On the descriptive complexity of temporal constraint satisfaction problems
• Collapsing the bounded width hierarchy for infinite-domain constraint satisfaction problems: when symmetries are enough
• Sensitive instances of the constraint satisfaction problem
• Network satisfaction problems solved by k-consistency
• Identifying tractable quantified temporal constraints within Ord-Horn
• Homogeneity and homogenizability: hard problems for the logic SNP
• Symmetric linear arc monadic Datalog and gadget reductions
• Algorithms and complexity of difference logic
• Datalog-expressibility for monadic and guarded second-order logic
• Smooth approximations and relational width collapses
• Datalog-expressibility for monadic and guarded second-order logic
• Symmetric linear arc monadic Datalog and gadget reductions
• Three fundamental questions in modern infinite-domain constraint satisfaction

Describes a project that uses

Uses Software

• Datalog

This page was built for publication: Datalog and constraint satisfaction with infinite templates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1936249)