Generic expression hardness results for primitive positive formula comparison

DOI10.1016/j.ic.2012.10.008zbMath1295.68121arXiv1205.5745MaRDI QIDQ1951576

Matthew A. Valeriote, Simone Bova, Hubie Chen

Publication date: 6 June 2013

Published in: Information and Computation, Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1205.5745

zbMATH Keywords

equivalence; computational complexity; clones; conjunctive queries; primitive positive formulas

Mathematics Subject Classification ID

03B70: Logic in computer science

08A70: Applications of universal algebra in computer science

03D15: Complexity of computation (including implicit computational complexity)

08A30: Subalgebras, congruence relations

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Unnamed Item, Unnamed Item, Taylor's modularity conjecture and related problems for idempotent varieties, On finitely related semigroups.

Cites Work

• Unnamed Item
• On the expression complexity of equivalence and isomorphism of primitive positive formulas
• Conjunctive query evaluation by search-tree revisited
• On the complexity of database queries
• Conjunctive-query containment and constraint satisfaction
• Closed systems of functions and predicates
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Varieties with few subalgebras of powers
• On the Computational Complexity of Algebra on Lattices
• The structure of finite algebras
• Minimal sets and varieties
• Constraint Satisfaction Problems of Bounded Width
• Classifying the Complexity of Constraints Using Finite Algebras
• Tractability and Learnability Arising from Algebras with Few Subpowers
• Recent Results on the Algebraic Approach to the CSP