Valeriote, Matt ;
Bova, Simone ;
Chen, Hubie
On the Expression Complexity of Equivalence and Isomorphism of Primitive Positive Formulas
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.
BibTeX - Entry
@InProceedings{valeriote_et_al:DagSemProc.09441.3,
author = {Valeriote, Matt and Bova, Simone and Chen, Hubie},
title = {{On the Expression Complexity of Equivalence and Isomorphism of Primitive Positive Formulas}},
booktitle = {The Constraint Satisfaction Problem: Complexity and Approximability},
pages = {1--20},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {1862-4405},
year = {2010},
volume = {9441},
editor = {Andrei A. Bulatov and Martin Grohe and Phokion G. Kolaitis and Andrei Krokhin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2010/2369},
URN = {urn:nbn:de:0030-drops-23690},
doi = {10.4230/DagSemProc.09441.3},
annote = {Keywords: Expression complexity, equivalence, isomorphism, primitive positive formulas}
}
|
Keywords: |
|
Expression complexity, equivalence, isomorphism, primitive positive formulas |
|
Seminar: |
|
09441 - The Constraint Satisfaction Problem: Complexity and Approximability
|
|
Issue date: |
|
2010 |
|
Date of publication: |
|
07.01.2010 |
07.01.2010
