Expressive power and complexity in algebraic logic

DOI10.1093/LOGCOM/7.3.309zbMATH Open0874.03051OpenAlexW2101081760MaRDI QIDQ4344697FDOQ4344697

Authors: Robin Hirsch 

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

Recommendations

• Comparing decision problems for various paradigms of algebraic logic.
• The complexity of constraint satisfaction problems for small relation algebras
• The complexity of problems connected with two-element algebras
• Algebraic foundations for qualitative calculi and networks
• scientific article; zbMATH DE number 4212010

zbMATH Keywords

complexityinterpretationintractabilityrelation algebraalgebraic logiccylindric algebrashomogeneous 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)

Cited In (19)

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

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

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