Expressive power and complexity in algebraic logic

DOI10.1093/LOGCOM/7.3.309MaRDI QIDQ4344697zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

algebraic logiccomplexitycylindric algebrashomogeneous representationsinterpretationintractabilitynetwork satisfaction problemrelation algebrasatisfaction problem

Mathematics Subject Classification ID

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

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

Cited in

(20)

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

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)