Expressive power and complexity in algebraic logic

DOI10.1093/logcom/7.3.309zbMath0874.03051OpenAlexW2101081760MaRDI QIDQ4344697

Robin Hirschl

Publication date: 17 July 1997

Published in: Journal of Logic and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/2e1722eef61c2b7c99c074f8a5866af5a47e00f8

zbMATH Keywords

complexityrelation algebraalgebraic logicintractabilitycylindric algebrasinterpretationhomogeneous representationssatisfaction problemnetwork satisfaction problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Cylindric and polyadic algebras; relation algebras (03G15)

Related Items (16)

Hardness of Network Satisfaction for Relation Algebras with Normal Representations ⋮ Solving infinite-domain CSPs using the patchwork property ⋮ Tractable approximations for temporal constraint handling ⋮ An initial study of time complexity in infinite-domain constraint satisfaction ⋮ Constants and finite unary relations in qualitative constraint reasoning ⋮ A relation-algebraic approach to the region connection calculus ⋮ Unnamed Item ⋮ Relation algebras and their application in temporal and spatial reasoning ⋮ So, what exactly is a qualitative calculus? ⋮ Branching interval algebra: an almost complete picture ⋮ Determining the consistency of partial tree descriptions ⋮ Constraint Satisfaction Problems with Infinite Templates ⋮ The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom ⋮ Point algebras for temporal reasoning: Algorithms and complexity ⋮ The complexity of constraint satisfaction problems for small relation algebras ⋮ Complexity classification in qualitative temporal constraint reasoning

This page was built for publication: Expressive power and complexity in algebraic logic