𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Generic separations and leaf languages

✍ Scribed by Matthias Galota; Sven Kosub; Heribert Vollmer

Book ID
102482999
Publisher
John Wiley and Sons
Year
2003
Tongue
English
Weight
167 KB
Volume
49
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

✦ Synopsis

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 of Blum and Impagliazzo. We obtain several consequences of this result, regarding, e. g., universal oracles, simultaneous separations and type‐2 complexity.

πŸ“œ SIMILAR VOLUMES

Logspace and Logtime Leaf Languages
Logspace and Logtime Leaf Languages
✍ Birgit Jenner; Pierre McKenzie; Denis ThΓ©rien πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 611 KB
Separation Results for Separated Apex NL
Separation Results for Separated Apex NLC and NCE Graph Languages
✍ Changwook Kim πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 268 KB

Relations among various types of node replacement graph languages are known in the literature but there has remained a gap in the hierarchy of these graph languages. The present paper fills this gap by proving a separation result for k-separated apex graph languages and by extending a known result f