An analysis of the W*-hierarchy

作者：Chen, Yijia^*; Flum, Jorg; Grohe, Martin

来源：Journal of Symbolic Logic, 2007, 72(2): 513-534.

DOI：10.2178/jsl/1185803622

We observe that the W*-hierarchy, a variant (introduced by Downey, Fellows, and Taylor [7]) of the better known W-hierarchy, coincides with the W-hierarchy, though not level wise, but just as a whole hierarchy. More precisely, we prove that W[t] subset of W* [t] subset of W[2t - 2] for each t > 2. It was known before that W[1] = W* [1] and W[2] - W* [2].
Our second main result is a new logical characterization of the W*-hierarchy in terms of "Fagin-definable problems." As a by-product, we also obtain an improvement of our earlier characterization of the hierarchy in terms of model-checking problems. Furthermore. we obtain new complete problems for the classes W[3] and W* [3].

• 出版日期2007-6
• 单位上海交通大学