An Analysis of the W -Hierarchy

Journal of Symbolic Logic 72 (2):513 - 534 (2007)
  Copy   BIBTEX

Abstract

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] ⊆ W*[t] ⊆ 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]

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,991

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

On some sets of dictionaries whose ω ‐powers have a given.Olivier Finkel - 2010 - Mathematical Logic Quarterly 56 (5):452-460.
Sparse parameterized problems.Marco Cesati & Michael R. Fellows - 1996 - Annals of Pure and Applied Logic 82 (1):1-15.
On Genericity and Ershov's Hierarchy.Amy Gale & Rod Downey - 2001 - Mathematical Logic Quarterly 47 (2):161-182.
On the distribution of Lachlan nonsplitting bases.S. Barry Cooper, Angsheng Li & Xiaoding Yi - 2002 - Archive for Mathematical Logic 41 (5):455-482.

Analytics

Added to PP
2010-08-24

Downloads
85 (#203,104)

6 months
36 (#102,149)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references