A finite relation algebra with undecidable network satisfaction problem

DOI10.1093/JIGPAL/7.4.547MaRDI QIDQ4700539zbMATHOpenAlexFDO

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

(8)

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

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)