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 As Get 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
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.
Subject Classification
Keywords
- Expression complexity
- equivalence
- isomorphism
- primitive positive formulas
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads