  To expand a fundamental theory of context-free languages, we equip
nondeterministic one-way pushdown automata with additional oracle mechanisms,
which naturally induce various nondeterministic reducibilities among formal
languages. As a natural restriction of NP-reducibility, we introduce a notion
of many-one CFL reducibility and conduct a ground work to formulate a coherent
framework for further expositions. Two more powerful reducibilities--bounded
truth-table and Turing CFL-reducibilities--are also discussed in comparison.
The Turing CFL-reducibility, in particular, helps us introduce an exquisite
hierarchy, called the CFL hierarchy, built over the family CFL of context-free
languages. For each level of this hierarchy, its basic structural properties
are proven and three alternative characterizations are presented. The second
level is not included in NC(2) unless NP= NC(2). The first and second levels of
the hierarchy are different. The rest of the hierarchy (more strongly, the
Boolean hierarchy built over each level of the hierarchy) is also infinite
unless the polynomial hierarchy over NP collapses. This follows from a
characterization of the Boolean hierarchy over the k-th level of the polynomial
hierarchy in terms of the Boolean hierarchy over the k+1st level of the CFL
hierarchy using log-space many-one reductions. Similarly, the complexity class
Theta(k) is related to the closure of the k-th level of the CFL hierarchy under
log-space truth-table reductions. We also argue that the CFL hierarchy
coincides with a hierarchy over CFL built by application of many-one
CFL-reductions. We show that BPCFL--a bounded-error probabilistic version of
CFL--is not included in CFL even in the presence of advice. Employing a known
circuit lower bound and a switching lemma, we exhibit a relativized world where
BPCFL is not located within the second level of the CFL hierarchy.
