Scholarly Works

Generic Expression Hardness Results for Primitive...

Generic Expression Hardness Results for Primitive Positive Formula Comparison

Abstract

We study the expression complexity of two basic problems involving the comparison of primitive positive formulas: equivalence and containment. We give two generic hardness results for the studied problems, and discuss evidence that they are optimal and yield, for each of the problems, a complexity trichotomy.

Authors

Bova S; Chen H; Valeriote M

Series

Lecture Notes in Computer Science

Volume

6756

Pagination

pp. 344-355

Publisher

Springer Nature

Publication Date

July 11, 2011

DOI

10.1007/978-3-642-22012-8_27

Conference proceedings

Lecture Notes in Computer Science

ISSN

0302-9743

Associated Experts

Matthew Anthony Valeriote

Professor Emeritus, Faculty of Science

Labels

Fields of Research (FoR)

46 Information and computing sciences

View published work (Non-McMaster Users)

Contact the Experts team

Get technical help

or

Provide website feedback