Maximal infinite-valued constraint languages

DOI10.1016/J.TCS.2008.12.050MaRDI QIDQ1014639zbMATH OpenOpenAlexFDO

Authors Manuel Bodirsky, Hubie Chen, Jan Kára, 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

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

Recommendations

• Maximal Infinite-Valued Constraint Languages
• The complexity of maximal constraint languages
• A Galois connection for valued constraint languages of infinite size
• STACS 2005
• Nondeterminism and infinite computations in constraint programming
• scientific article; zbMATH DE number 1231566
• The syntax and semantics of infinitary languages
• scientific article; zbMATH DE number 3906482
• Complexity of infinite-domain constraint satisfaction
• Datalog and constraint satisfaction with infinite templates

Cites work

• scientific article; zbMATH DE number 3972929 (Why is no real title available?)
• scientific article; zbMATH DE number 3972930 (Why is no real title available?)
• scientific article; zbMATH DE number 663783 (Why is no real title available?)
• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• scientific article; zbMATH DE number 1149443 (Why is no real title available?)
• Classifying the Complexity of Constraints Using Finite Algebras
• Closure properties of constraints
• Constraint Satisfaction with Countable Homogeneous Templates
• Datalog and Constraint Satisfaction with Infinite Templates
• Infinite Dimensional Classical Groups
• Maintaining knowledge about temporal intervals
• Oligomorphic clones
• On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus
• Reasoning about temporal relations
• Reasoning about temporal relations, the tractable subalgebras of Allen's interval algebra
• Relation algebras and their application in temporal and spatial reasoning
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The complexity of equality constraint languages
• The complexity of maximal constraint languages
• The core of a graph

Cited in

(11)

• Tractability in constraint satisfaction problems: a survey
• The complexity of maximal constraint languages
• Maximal Infinite-Valued Constraint Languages
• Necessary conditions for tractability of valued CSPs
• An algebraic view on p-admissible concrete domains for lightweight description logics
• Using model theory to find decidable and tractable description logics with concrete domains
• The complexity of recursive constraint satisfaction problems
• Minimal functions on the random graph
• Constraint Satisfaction Problems with Infinite Templates
• Solving equation systems in ω-categorical algebras
• Constraint satisfaction problems for reducts of homogeneous graphs

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

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