A finite relation algebra with undecidable network satisfaction problem

DOI10.1093/jigpal/7.4.547zbMath0933.03051OpenAlexW2043885318MaRDI QIDQ4700539

Robin Hirschl

Publication date: 1 November 1999

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

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

zbMATH Keywords

undecidabilitytilingrelation algebranetwork satisfaction problem

Mathematics Subject Classification ID

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

Related Items (8)

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