Home
Scholarly Works
On the Expression Complexity of Equivalence and...
Conference

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.

Authors

Bova S; Chen H; Valeriote M

Volume

9441

Publication Date

January 1, 2010

Conference proceedings

Dagstuhl Seminar Proceedings

ISSN

1862-4405

Contact the Experts team