Hardness of Network Satisfaction for Relation Algebras with Normal Representations

DOI10.1007/978-3-030-43520-2_3OpenAlexW3013737276MaRDI QIDQ5098711

Simon Knäuer, Manuel Bodirsky

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)

Related Items (1)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maintaining knowledge about temporal intervals
• Relation algebras by games
• The complexity of constraint satisfaction problems for small relation algebras
• Relation algebras
• Conservative constraint satisfaction re-revisited
• Determining the consistency of partial tree descriptions
• On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus
• Finite relation algebras with normal representations
• The wonderland of reflections
• Relation algebras and their application in temporal and spatial reasoning
• Representations for small relation algebras
• Relation algebras of intervals
• Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
• A Model-Theoretic View on Qualitative Constraint Reasoning
• Constraint Satisfaction with Countable Homogeneous Templates
• On binary constraint problems
• Expressive power and complexity in algebraic logic
• A finite relation algebra with undecidable network satisfaction problem
• PROJECTIVE CLONE HOMOMORPHISMS
• Constraint Satisfaction Problems for Reducts of Homogeneous Graphs

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