@article{BasinGanzinger01,
AUTHOR = "David Basin and Harald Ganzinger",
TITLE = "Automated Complexity Analysis Based on Ordered Resolution",
JOURNAL="Journal of the Association of Computing Machinery",
YEAR="2001",
MONTH="January",
VOLUME="48",
NUMBER="1",
PAGES="70--109",
ABSTRACT={
We define order locality to be a property of clauses relative
to a term ordering.   This property
generalizes the subformula property for proofs where
the terms appearing in proofs can be bounded,
under the given ordering,
by terms appearing in the goal clause.  We show that when a clause set is
order local, then the complexity of its ground entailment problem is
a function of its structure (e.g., full versus Horn clauses),
and the ordering used.   We prove that, in many cases, order locality
is equivalent to a clause set being saturated
under ordered resolution.  This provides a means of using standard
resolution theorem provers for testing order locality and
transforming non-local clause sets into local ones.
We have used the Saturate system to automatically establish complexity
bounds for a number of nontrivial entailment problems
relative to complexity classes which include polynomial and
exponential time and co-NP.}
}