Maximal infinite-valued constraint languages

DOI10.1016/j.tcs.2008.12.050zbMath1172.68052OpenAlexW1997175672MaRDI QIDQ1014639

Jan Kára, Manuel Bodirsky, Hubie Chen, Timo von Oertzen

Publication date: 29 April 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.12.050

zbMATH Keywords

computational complexityconstraint satisfactioncountably categorical structuresuniversal algebra in computer science

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Categoricity and completeness of theories (03C35)

Related Items (8)

Tractability in constraint satisfaction problems: a survey ⋮ Necessary Conditions for Tractability of Valued CSPs ⋮ Solving equation systems in ω-categorical algebras ⋮ Minimal functions on the random graph ⋮ Schaefer's Theorem for Graphs ⋮ An algebraic view on p-admissible concrete domains for lightweight description logics ⋮ Constraint Satisfaction Problems for Reducts of Homogeneous Graphs ⋮ Using model theory to find decidable and tractable description logics with concrete domains

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maintaining knowledge about temporal intervals
• The core of a graph
• The complexity of equality constraint languages
• Oligomorphic clones
• On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus
• Relation algebras and their application in temporal and spatial reasoning
• Constraint Satisfaction with Countable Homogeneous Templates
• Reasoning about temporal relations
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Reasoning about temporal relations
• Closure properties of constraints
• Infinite Dimensional Classical Groups
• The complexity of maximal constraint languages
• Classifying the Complexity of Constraints Using Finite Algebras
• Datalog and Constraint Satisfaction with Infinite Templates

This page was built for publication: Maximal infinite-valued constraint languages