Generic expression hardness results for primitive positive formula comparison (Q1951576): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||||||||||||||
(4 intermediate revisions by 3 users not shown) | |||||||||||||||
aliases / en / 0 | aliases / en / 0 | ||||||||||||||
Generic Expression Hardness Results for Primitive Positive Formula Comparison | |||||||||||||||
description / en | description / en | ||||||||||||||
scientific article | scientific article; zbMATH DE number 5918157 | ||||||||||||||
Property / title | |||||||||||||||
Generic Expression Hardness Results for Primitive Positive Formula Comparison (English) | |||||||||||||||
Property / title: Generic Expression Hardness Results for Primitive Positive Formula Comparison (English) / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH Open document ID | |||||||||||||||
Property / zbMATH Open document ID: 1333.68116 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / DOI | |||||||||||||||
Property / DOI: 10.1007/978-3-642-22012-8_27 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / published in | |||||||||||||||
Property / published in: Automata, Languages and Programming / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / publication date | |||||||||||||||
7 July 2011
| |||||||||||||||
Property / publication date: 7 July 2011 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / Mathematics Subject Classification ID | |||||||||||||||
Property / Mathematics Subject Classification ID: 03B70 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH DE Number | |||||||||||||||
Property / zbMATH DE Number: 5918157 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / OpenAlex ID | |||||||||||||||
Property / OpenAlex ID: W2568552169 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / OpenAlex ID | |||||||||||||||
Property / OpenAlex ID: W2106865935 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / arXiv ID | |||||||||||||||
Property / arXiv ID: 1205.5745 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Conjunctive query evaluation by search-tree revisited / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Constraint Satisfaction Problems of Bounded Width / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Varieties with few subalgebras of powers / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: On the expression complexity of equivalence and isomorphism of primitive positive formulas / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Classifying the Complexity of Constraints Using Finite Algebras / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: A dichotomy theorem for constraint satisfaction problems on a 3-element set / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Recent Results on the Algebraic Approach to the CSP / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Q3775604 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Closed systems of functions and predicates / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: The structure of finite algebras / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Tractability and Learnability Arising from Algebras with Few Subpowers / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: On the Computational Complexity of Algebra on Lattices / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Minimal sets and varieties / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Conjunctive-query containment and constraint satisfaction / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: On the complexity of database queries / rank | |||||||||||||||
Normal rank |
Latest revision as of 06:53, 4 July 2024
scientific article; zbMATH DE number 5918157
- Generic Expression Hardness Results for Primitive Positive Formula Comparison
Language | Label | Description | Also known as |
---|---|---|---|
English | Generic expression hardness results for primitive positive formula comparison |
scientific article; zbMATH DE number 5918157 |
|
Statements
Generic expression hardness results for primitive positive formula comparison (English)
0 references
Generic Expression Hardness Results for Primitive Positive Formula Comparison (English)
0 references
6 June 2013
0 references
7 July 2011
0 references
A primitive positive formula is a first-order formula defined from atomic formulas and equality of variables using conjunction and existential quantification. These formulas are equivalent to conjunctive queries. The authors study the complexity of the following two problems for given primitive positive formulas \(\varphi\) and \(\psi\) over a finite relational structure: -- Equivalence problem: are \(\varphi\) and \(\psi\) equivalent, i.e., do they have the same satisfying assignment? -- Containment problem: are the satisfying assignments of \(\varphi\) contained in those of \(\psi\)? These computational problems are studied with respect to various fixed (finite) structures. The authors' suggestion is that ``various relational structures -- which may represent databases or knowledge bases, according to use -- may possess structural characteristics that affect the complexity of the resulting problems'' and the authors are interested in ``understanding this interplay''. For a finite relational structure \(\bar{B}\) with the universe \(B\) let \(\text{A}_{\bar{B}}\) denote the (finite) algebra \(\langle B,{\mathtt Pol}(\bar{B})\rangle\) where \({\mathtt Pol}(\bar{B})\) is the set of all polymorphisms of \({B}\), i.e., the set of all operations on \(B\) that preserve the relations of \(\bar{B}\). The two main results of the paper are: (1) For any finite relational ``structure \(\bar{B}\) whose associated algebra \(\text{A}_{\bar{B}}\) gives rise to a variety \({\mathcal V}(\text{A}_{\bar{B}})\) that admits the unary type, both the equivalence and containment problem are \(\Pi_2^p\)-hard. Note that this is the maximal complexity possible for these problems, as the problems are contained in the class \(\Pi_2^p\).'' (2) For any finite relational ``structure \(\bar{B}\) if the variety \({\mathcal V}(\text{A}_{\bar{B}})\) is not congruence modular, then the equivalence and containment problems are coNP-hard.''
0 references
primitive positive formulas
0 references
conjunctive queries
0 references
equivalence
0 references
computational complexity
0 references
clones
0 references
0 references