Constraint Satisfaction Problems with Infinite Templates

DOI10.1007/978-3-540-92800-3_8MaRDI QIDQ5504704zbMATH OpenOpenAlexFDO

Authors Manuel Bodirsky

Publication date 22 January 2009

Published in Complexity of Constraints (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-92800-3_8

Mathematics Subject Classification ID

Logic in computer science (03B70) Applications of universal algebra in computer science (08A70)

Recommendations

• Complexity of infinite-domain constraint satisfaction
• The complexity of constraint satisfaction problems (invited talk)
• On the scope of the universal-algebraic approach to constraint satisfaction
• Maximal infinite-valued constraint languages
• Datalog and constraint satisfaction with infinite templates

Cites work

• \(\aleph _ 0\)-categorical, \(\aleph _ 0\)-stable structures
• `` Strong NP-Completeness Results
• A course in model theory. An introduction to contemporary mathematical logic. Transl. from the French by Moses Klein
• A Simple Algorithm for Mal'tsev Constraints
• A survey of clones on infinite sets
• Acyclic Homomorphisms and Circular Colorings of Digraphs
• Building tractable disjunctive constraints
• Categori city of denumerable atomless Boolean rings
• Classification of Infinite Primitive Jordan Permutation Groups
• Classifying the Complexity of Constraints Using Finite Algebras
• Closed systems of functions and predicates
• Computer Science Logic
• Constraints, MMSNP and expander relational structures
• Cores of Countably Categorical Structures
• Datalog and Constraint Satisfaction with Infinite Templates
• Determining the consistency of partial tree descriptions
• Dichotomies in the complexity of solving systems of equations over finite semigroups
• Expressive power and complexity in algebraic logic
• scientific article; zbMATH DE number 3972929 (Why is no real title available?)
• scientific article; zbMATH DE number 3751028 (Why is no real title available?)
• scientific article; zbMATH DE number 44603 (Why is no real title available?)
• scientific article; zbMATH DE number 1324669 (Why is no real title available?)
• scientific article; zbMATH DE number 663783 (Why is no real title available?)
• scientific article; zbMATH DE number 663784 (Why is no real title available?)
• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• scientific article; zbMATH DE number 1064592 (Why is no real title available?)
• scientific article; zbMATH DE number 1149443 (Why is no real title available?)
• scientific article; zbMATH DE number 2086393 (Why is no real title available?)
• scientific article; zbMATH DE number 1912564 (Why is no real title available?)
• scientific article; zbMATH DE number 272725 (Why is no real title available?)
• scientific article; zbMATH DE number 3336816 (Why is no real title available?)
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• Linear unification
• Maintaining knowledge about temporal intervals
• Maximal Infinite-Valued Constraint Languages
• Oligomorphic clones
• On the complexity of H-coloring
• On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus
• On the Structure of Polynomial Time Reducibility
• Point algebras for temporal reasoning: Algorithms and complexity
• Qualitative Temporal and Spatial Reasoning Revisited
• Reasoning about temporal relations
• Reasoning about temporal relations, the tractable subalgebras of Allen's interval algebra
• Reduced Products and Horn Classes
• Relation algebras and their application in temporal and spatial reasoning
• Stable Finitely Homogeneous Structures
• Structure of partially ordered sets with transitive automorphism groups
• The Complexity of Equality Constraint Languages
• The complexity of infinite \(H\)-colouring
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Theory of relations. Transl. from the French by P. Clote
• Tractability and learnability arising from algebras with few subpowers
• Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning
• ℵ₀ -Categorical Structures Smoothly Approximated by Finite Substructures

Cited in

(24)

• Peek arc consistency
• Datalog and constraint satisfaction with infinite templates
• A survey of homogeneous structures
• On the scope of the universal-algebraic approach to constraint satisfaction
• The inference problem for template dependencies
• Non-dichotomies in Constraint Satisfaction Complexity
• Locally finite constraint satisfaction problems
• Loop conditions for strongly connected digraphs
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• Absorption in universal algebra and CSP
• An initial study of time complexity in infinite-domain constraint satisfaction
• The power of Sherali-Adams relaxations for general-valued CSPs
• \({\aleph_{0}}\)-categorical structures: endomorphisms and interpretations
• Maximal Infinite-Valued Constraint Languages
• Datalog and Constraint Satisfaction with Infinite Templates
• Topological Birkhoff
• Dualities for Constraint Satisfaction Problems
• Computational Short Cuts in Infinite Domain Constraint Satisfaction
• The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
• The complexity of recursive constraint satisfaction problems
• Homomorphism-homogeneity classes of countable L-colored graphs
• Morphism extension classes of countable L-colored graphs
• The complexity of equality constraint languages
• Approximability of clausal constraints

This page was built for publication: Constraint Satisfaction Problems with Infinite Templates

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