Hardness of Network Satisfaction for Relation Algebras with Normal Representations

DOI10.1007/978-3-030-43520-2_3MaRDI QIDQ5098711zbMATH OpenOpenAlexFDO

Authors Manuel Bodirsky, Simon Knäuer

Publication date 30 August 2022

Published in Relational and Algebraic Methods in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
• Expressive power and complexity in algebraic logic
• The complexity of constraint satisfaction problems for small relation algebras
• Finite relation algebras with normal representations
• Algebraic foundations for qualitative calculi and networks

Cites work

• A finite relation algebra with undecidable network satisfaction problem
• A model-theoretic view on qualitative constraint reasoning
• Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
• Canonical functions: a proof via topological dynamics
• Conservative constraint satisfaction re-revisited
• Constraint satisfaction problems for reducts of homogeneous graphs
• Constraint Satisfaction with Countable Homogeneous Templates
• Determining the consistency of partial tree descriptions
• Expressive power and complexity in algebraic logic
• Finite relation algebras with normal representations
• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• Maintaining knowledge about temporal intervals
• On binary constraint problems
• On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus
• PROJECTIVE CLONE HOMOMORPHISMS
• Relation algebras
• Relation algebras and their application in temporal and spatial reasoning
• Relation algebras by games
• Relation algebras of intervals
• Representations for small relation algebras
• The complexity of constraint satisfaction problems for small relation algebras
• The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems
• The wonderland of reflections

Cited in

(2)

• The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
• Network satisfaction problems solved by k-consistency

This page was built for publication: Hardness of Network Satisfaction for Relation Algebras with Normal Representations

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