The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
From MaRDI portal
Publication:5870532
DOI10.1613/JAIR.1.14195OpenAlexW4313395388MaRDI QIDQ5870532FDOQ5870532
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
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
- Maintaining knowledge about temporal intervals
- The partite construction and Ramsey set systems
- Schaefer's theorem for graphs
- Constraint Satisfaction with Countable Homogeneous Templates
- The complexity of temporal constraint satisfaction problems
- Title not available (Why is that?)
- Conservative constraint satisfaction re-revisited
- On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus
- The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
- Relation algebras by games
- Minimal functions on the random graph
- A survey of homogeneous structures
- A strong Mal'cev condition for locally finite varieties omitting the unary type
- On binary constraint problems
- Some Varieties Containing Relation Algebras
- A finite relation algebra with undecidable network satisfaction problem
- Divisibility of countable metric spaces
- Expressive power and complexity in algebraic logic
- Constraint Satisfaction Problems with Infinite Templates
- The representation of relational algebras
- Combinatorial aspects of relations
- Relation algebras and their application in temporal and spatial reasoning
- A perspective on the theory of relation algebras
- Representations for small relation algebras
- The complexity of constraint satisfaction problems for small relation algebras
- All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms)
- PROJECTIVE CLONE HOMOMORPHISMS
- Chromatic graphs, Ramsey numbers and the flexible atom conjecture
- Datalog and constraint satisfaction with infinite templates
- Complexity of infinite-domain constraint satisfaction
- Determining the consistency of partial tree descriptions
- Finite relation algebras with normal representations
- Strongly representable atom structures of relation algebras
- Asking the Metaquestions in Constraint Tractability
- Algebraic foundations for qualitative calculi and networks
- A model-theoretic view on qualitative constraint reasoning
- A proof of the CSP dichotomy conjecture
- Constraint satisfaction problems for reducts of homogeneous graphs
- Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction
- Title not available (Why is that?)
- Hardness of Network Satisfaction for Relation Algebras with Normal Representations
- Finite Symmetric Integral Relation Algebras with No 3-Cycles
Cited In (1)
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)
