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