DagSemProc.09441.3.pdf
- Filesize: 396 kB
- 20 pages
Document
On the Expression Complexity of Equivalence and Isomorphism of Primitive Positive Formulas
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 9441
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2010-01-07
Cite AsGet BibTex
Matt Valeriote, Simone Bova, and Hubie Chen. On the Expression Complexity of Equivalence and Isomorphism of Primitive Positive Formulas. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Seminar Proceedings, Volume 9441, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
https://doi.org/10.4230/DagSemProc.09441.3
https://doi.org/10.4230/DagSemProc.09441.3
Abstract
We study the complexity of
equivalence and isomorphism on
primitive positive formulas with respect to a given structure.
We study these problems for various fixed structures;
we present generic hardness and complexity class containment
results, and give classification theorems for the case of
two-element (boolean) structures.
Keywords
- Expression complexity
- equivalence
- isomorphism
- primitive positive formulas
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads