The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom

DOI10.1613/JAIR.1.14195MaRDI QIDQ5870532zbMATH OpenOpenAlexFDO

Authors Manuel Bodirsky, Simon Knäuer

Publication date 9 January 2023

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.11943

zbMATH Keywords

constraint satisfactionqualitative reasoningspatial reasoning

Mathematics Subject Classification ID

Artificial intelligence (68Txx)

Recommendations

• Hardness of Network Satisfaction for Relation Algebras with Normal Representations
• A finite relation algebra with undecidable network satisfaction problem
• Publication:4729350
• The complexity of constraint satisfaction problems for small relation algebras
• The complexity of constraint satisfaction: an algebraic approach
• STACS 2004
• Complexity of satisfiability problems with symmetric polynomial clauses
• Flexibility in Algebraic Nets
• On computation complexity problems concerning relation algebras
• On the parallel complexity of discrete relaxation in constraint satisfaction networks

Cites work

• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• scientific article; zbMATH DE number 7406819 (Why is no real title available?)
• A finite relation algebra with undecidable network satisfaction problem
• A model-theoretic view on qualitative constraint reasoning
• A perspective on the theory of relation algebras
• A proof of the CSP dichotomy conjecture
• A strong Mal'cev condition for locally finite varieties omitting the unary type
• A survey of homogeneous structures
• Algebraic foundations for qualitative calculi and networks
• All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms)
• Asking the Metaquestions in Constraint Tractability
• Chromatic graphs, Ramsey numbers and the flexible atom conjecture
• Combinatorial aspects of relations
• Complexity of infinite-domain constraint satisfaction
• Conservative constraint satisfaction re-revisited
• Constraint Satisfaction Problems with Infinite Templates
• Constraint Satisfaction with Countable Homogeneous Templates
• Constraint satisfaction problems for reducts of homogeneous graphs
• Datalog and constraint satisfaction with infinite templates
• Determining the consistency of partial tree descriptions
• Divisibility of countable metric spaces
• Expressive power and complexity in algebraic logic
• Finite Symmetric Integral Relation Algebras with No 3-Cycles
• Finite relation algebras with normal representations
• Hardness of Network Satisfaction for Relation Algebras with Normal Representations
• Maintaining knowledge about temporal intervals
• Minimal functions on the random graph
• On binary constraint problems
• On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus
• PROJECTIVE CLONE HOMOMORPHISMS
• Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction
• Relation algebras and their application in temporal and spatial reasoning
• Relation algebras by games
• Representations for small relation algebras
• Some Varieties Containing Relation Algebras
• Strongly representable atom structures of relation algebras
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• The complexity of constraint satisfaction problems for small relation algebras
• The complexity of temporal constraint satisfaction problems
• The partite construction and Ramsey set systems
• The representation of relational algebras

Cited in

(1)

• Smooth approximations and CSPs over finitely bounded homogeneous structures

This page was built for publication: The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom

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