School of Computer Science, University of Waterloo, Ont., Canada N2L 3G1
Abstract:
We give simple, self-contained proofs of the basic hardness results for the classes Wt] of the weft hierarchy. We extend these proofs to higher levels of the hierarchy and illuminate the distinctions among its classes. The anti-monotone collapse at W1,s] and the normalization of weft-t formulas arise as by-products of the proofs.