A finite relation algebra with undecidable network satisfaction problem

DOI10.1093/JIGPAL/7.4.547MaRDI QIDQ4700539zbMATH OpenOpenAlexFDO

Authors Robin Hirsch

Publication date 1 November 1999

Published in Logic Journal of the IGPL (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/5202ba654507d34be9428d8cd8fa2370884dc033

zbMATH Keywords

tilingundecidabilityrelation algebranetwork satisfaction problem

Mathematics Subject Classification ID

Logic in artificial intelligence (68T27) Temporal logic (03B44) Cylindric and polyadic algebras; relation algebras (03G15) Undecidability and degrees of sets of sentences (03D35)

Cited in

(9)

• Algebraic foundations for qualitative calculi and networks
• Hardness of Network Satisfaction for Relation Algebras with Normal Representations
• Tractable approximations for temporal constraint handling
• Qualitative constraint satisfaction problems: an extended framework with landmarks
• The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
• Network satisfaction problems solved by k-consistency
• Relation algebras and their application in temporal and spatial reasoning
• An initial study of time complexity in infinite-domain constraint satisfaction
• The complexity of constraint satisfaction problems for small relation algebras

This page was built for publication: A finite relation algebra with undecidable network satisfaction problem

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