User: Guest  Login
Document type:
Technical Report 
Author(s):
Matthias Galota; Sven Kosub; Heribert Vollmer 
Title:
Generic Separations and Leaf Languages 
Abstract:
In the early nineties of the previous century, leaf languages were introduced as a means for the uniform characterization of many complexity classes, mainly in the range between P (polynomial time) and PSPACE (polynomial space). It was shown that the separability of two complexity classes can be reduced to a combinatorial property of the corresponding defining leaf languages. In the present paper, it is shown that every separation obtained in this way holds for every generic oracle in the sense...    »
 
Keywords:
computational and structural complexity; leaf language; oracle separation; generic oracle; type-2 complexity theory 
Year:
2001 
Year / month:
2001-09-01 00:00:00 
versions