loading...
Complete Problems for Dynamic Complexity Classes
Copenhagen, Denmark July 22-July 25
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/LICS.2002.102983917th Annual IEEE Symposium on Logic i ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
William Hesse, Neil Immerman, "Complete Problems for Dynamic Complexity Classes," Logic in Computer Science, Symposium on, pp. 313, 17th Annual IEEE Symposium on Logic in Computer Science (LICS'02), 2002.
 
 
BibTex
x
 
@article{ 10.1109/LICS.2002.1029839,
author = {William Hesse and Neil Immerman},
title = {Complete Problems for Dynamic Complexity Classes},
journal ={Logic in Computer Science, Symposium on},
volume = {0},
year = {2002},
issn = {1043-6871},
pages = {313},
doi = {http://doi.ieeecomputersociety.org/10.1109/LICS.2002.1029839},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Logic in Computer Science, Symposium on
TI - Complete Problems for Dynamic Complexity Classes
SN - 1043-6871
SP
EP
A1 - William Hesse,
A1 - Neil Immerman,
PY - 2002
KW - null
VL - 0
JA - Logic in Computer Science, Symposium on
ER -
 
William Hesse, University of Massachusetts at Amherst
Neil Immerman, University of Massachusetts at Amherst

We present the first complete problems for dynamic complexity classes including the classes Dyn-FO and Dyn-ThC0, the dynamic classes corresponding to relational calculus and (polynomially bounded) SQL, respectively. The first problem we show complete for Dyn-FO is a single-step version of the circuit value problem (SSCV).

Of independent interest, our construction also produces a first-order formula, &zgr;, that is in a sense universal for all first-order formulas. Since first-order formulas are stratified by quantifier depth, the first-order formula &zgr; emulates formulas of greater depth by iterated application. As a corollary we obtain a fixed quantifier block, QBC, that is complete for all first-order quantifier blocks.

Citation:
William Hesse, Neil Immerman, "Complete Problems for Dynamic Complexity Classes," lics, pp.313, 17th Annual IEEE Symposium on Logic in Computer Science (LICS'02), 2002
Usage of this product signifies your acceptance of the Terms of Use.