Generic expression hardness results for primitive positive formula comparison
Publication:1951576
DOI10.1016/j.ic.2012.10.008zbMath1295.68121arXiv1205.5745OpenAlexW2568552169MaRDI 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
Logic in computer science (03B70) Applications of universal algebra in computer science (08A70) Complexity of computation (including implicit computational complexity) (03D15) Subalgebras, congruence relations (08A30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (4)
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
This page was built for publication: Generic expression hardness results for primitive positive formula comparison
