Hostname: page-component-7b7567c8c-w7t8q Total loading time: 0 Render date: 2026-11-19T05:23:03.341Z Has data issue: false hasContentIssue false

An analysis of the W*-hierarchy

Published online by Cambridge University Press:  12 March 2014

Yijia Chen
Affiliation:
Basics, Department of Computer Science, Shanghai Jiaotong University, Shanghai 200030, China, E-mail: yijia.chen@cs.sjtu.edu.cn
Jörg Flum
Affiliation:
Abteilung für Mathematische Logik, Universität Freiburg, Eckerstr. 1, 79104 Freiburg, Germany, E-mail: joerg.flum@math.uni-freiburg.de
Martin Grohe
Affiliation:
Institut für Informatik, Humboldt-Universität zu Berlin, Unter den Linden 6, 10099 Berlin, Germany, E-mail: grohe@informatik.hu-berlin.de

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].

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable