The notion of e ectively selective languages was introduced into computational complexity theory in late 1970s and it has been discussed extensively in connection to the P=?NP question. Its scope has been extended to nite automata and formal languages in the past literature. By further extending the scope, this paper discusses the computational complexity of selective languages whose underlying selectors are computed in various ways by nondeterministic one-way pushdown automata equipped with write-once output tapes. We explore basic properties of those languages and demonstrate their relationships to the existing language families. We also seek a generalization of such selective languages by taking selectors from a higher functional hierarchy over multi-valued CFL functions.
likely to be a \positive" instance of the language (namely, to belong to the language). We are particularly concerned with the e ciency of such a sector. The computational complexity of languages whose selectors are e ciently computable has been discussed in connection to the P =?NP question. The importance of selectivity also comes from the fact that each selector can induce a certain type of partial pre-order on equivalence classes over strings (see [7, 9]).
The notion of P-selective languages, which was rst introduced into computational complexity theory in 1979 by Selman [9] as a polynomial-time analogue of Jockusch's semi-recursive sets in recursion theory. The selective languages have been since then used as an important tool in studying various structural properties, such as completeness, self-reducibility, search-to-decision reductions, re nements, and promise problems (see [2] for references therein). Later, this notion was extended to NPSV- and NPMV-selective languages [2] and beyond to kPSV- and kPMV-selective languages [6], where two su xes \SV" and \MV" indicate \single-valued function" and \multi-valued function", and kP is the kth level of the polynomial-time hierarchy [8]. More generally, given any function class F , F -selective languages are de ned simply by the choice of appropriate selectors from F . Since the selectivity notion is heavily linked to languages and multi-valued partial functions, it is ideal to study the computational complexity of languages and functions together.
Taking the opposite research direction, we look into more restrictive computational models in order to witness how dramatically the complexity of selecting positive instances changes. A precursor to our investigation is the study of \DFA-selectivity" (which was originally called fa-selectivity) of Tantau [13]. Our main interest, on the contrary, lies on the behaviors of selectors when they are computed on 1npda's equipped with write-once? output tapes. Those machines are quite di erent in nature from powerful Turing machines and their behaviors are quite restrictive because of the limited usage of their memory device. Multi-valued partial functions computed by such machines are generally called CFL-functions and they have been recently discussed in a series of works [17, 20, 18, 21]. More speci cally, we intend to study selective languages whose selectors are particularly chosen from function classes, such as CFLSV and CFLMV [20] (see Section 2.2 for their de nitions), which are natural analogues of the aforementioned function classes NPSV and NPMV, respectively. In a later section, we then turn our attention to higher complexity classes kCFLSV and kCFLMV, which constitute a functional version of the CFL hierarchy [19] de ned in parallel to the polynomial(-time) hierarchy. 2
We will brie y explain existing notions and notations necessary to read through the subsequent sections. ? A tape is write-once if its tape head never moves to the left and, whenever it writes a nonempty symbol, it must move to the next blank cell. 2.1
Given a nite set A, the notation kAk denotes the number of elements in A. Let N indicate the set of all natural numbers (i.e., nonnegative integers) and set N+ = N f0g. For two integers m and n with m n, the notation [m; n]Z denotes the integer interval fm; m + 1; m + 2; : : : ; ng. In particular, we abbreviate [1; n]Z as [n] for any n 2 N+. We use the term \polynomials" to mean polynomials with nonnegative integer coe cients. The notation A B for two sets A and B indicates the di erence fx j x 2 A; x 62 Bg. Given a set A, P(A) denotes the power set of A.
An alphabet is a nonempty nite set of \symbols" or \letters". A string x over is a nite series of symbols chosen from and its length, denoted by jxj, is the total occurrences of symbols in x. The empty string is a unique string of length 0. To express a pair of strings simultaneously, we use the track notation [ xy] and follow its convention, as discussed in [12]. For two symbols and , [ ] expresses a new symbol. For two strings x = x1x2 xn and y = y1y2 yn of length n, [ xy] denotes the concatenated string [ xy11]y[ xy,22][ xy] expresses [ x#ym], where [ xynn]. We further expand this notation as follows. In the case of jxj < j j m = jyj jxj and # is a designated new symbol. Similarly, when jxj > jyj, the same succinct notation [ xy] expresses [ y#xm] with m = jxj jyj.
A language over alphabet is a collection of strings over . Given an index k 2 N, k is composed of all strings of length k; in particular, 0 equals f g. Let = Sk2N k. For any language A over , its complement is A, which is also denoted by A as long as is clear from the context.
A function h : N ! is called length preserving if jh(n)j = n holds for all n 2 N. Recall from [19, 20] the notion of \-extension. For any string x 2 , a \-extension of x is a string x~ over [ f\g such that x is obtained from x~ by deleting all occurrences of \. Given a language A, the characteristic function
A for A is a unique function de ned as A(x) = 1 if x 2 A, and A(x) = 0 otherwise.
ministic nite automata (or 1nfa's, for short) with -moves and 1-way
(onetape, one-head) nondeterministic pushdown automata (or 1npda's) with -moves,
Where a -move is a step at which an input-tape head stays still reading nothing.
We also use their deterministic variants: 1dfa's and 1dpda's. Formally, a 1npda
N with a write-once output tape computing f : ! P( ) has the following
form: N = (Q; ; fcj; $g; ; ; ; q0; ?; Qacc; Qrej ), where Q is a nite set of inner
states, is a stack alphabet, is an output alphabet, q0 (2 Q) is the initial state,
? (
Along each computation path, a machine may produce a string on the output tape. We call such a string a valid output (or a legitimate output ) if it is produced along an appropriate accepting computation path. Only valid outputs are considered as the machine's true \outputs" and we automatically disregard any string produced along any rejecting computation path. This convention is particularly important for one-way machines because this makes it possible for such a one-way machine to start producing all possible strings nondeterministically while reading an input string and then to invalidate any unwanted strings by simply entering rejecting states in the time of halting.
We say that a machine with two heads on input and output tapes is synchronous if, whenever the input-tape head moves to the right, the output-tape head also moves to the right, and vice visa.
To treat input instances of a given \2-ary" partial function f on a model of \1-way" machine M , we use the aforementioned track notation. For technical reason, unlike the case of Turing machines, we do not use two-tape 1nfa's and 1npda's to access two independent input strings x and y; instead, we split a single input tape into two tracks and write x and y on these tracks separately. More precisely, when a pair (x; y) of strings is given as an input instance to the machine M , we place x in the upper track and y in the lower track as [ xy] so that the tape head can read x and y simultaneously from left to right. More formally, if we wish to compute f on input (x; y), we start its underlying machine M x whose input tape contains the string of the form [ y]. From this formalism, we write f ([ xy]), instead of f (x; y), to describe the function f that takes an input of x the form [ y].
The notations REG and CFL stand for the family of all regular languages and
that of all context-free languages, respectively. For each number k 2 N+, the
kconjunctive closure of CFL, denoted CFL(k), is de ned recursively as CFL(
Throughout this paper, similarly to [20], the generic term \function" refers to \multi-valued partial function," provided that single-valued functions are viewed as a special case of multi-valued functions and partial functions include total functions. We are mostly interested in multi-valued partial functions mapping?? to for certain alphabets and , not necessarily limited to f0; 1g. Whenever f is single-valued, we often write f (x) = y instead of y 2 f (x). The domain dom(f ) of f is de ned to be the set fx 2 j f (x) 6= ?g. When x 62 dom(x), f (x) is said to be unde ned.
A multi-valued partial function f : ! P( ) is called polynomially bounded if there exists a polynomial p such that, for any two strings x 2 and y 2 , if y 2 f (x) then jyj p(jxj) holds. We understand that all function classes dealt with in this paper are assumed to be polynomially bounded. Given two alphabets and , a multi-valued partial function f : ! P( ) is called length preserving if, for any two strings x 2 and y 2 , y 2 f (x) implies jxj = jyj. Similarly, f is length decreasing if y 2 f (x) implies jyj < jxj for any x; y 2 .
Given two multi-valued functions f and g, we say that g is a re nement
of f , denoted by f vref g, if (
The following four basic function classes were introduced in [17]. The function
class CFLMV is composed of all multi-valued functions f , each of which maps
to P( ) for a certain alphabet and there exists a 1npda N with a 1-way
read-once input tape together with a write-once output tape such that, for every
input x 2 , f (x) is the set of all valid outcomes of N on the input x. CFLMVt
is a natural restriction of CFLMV onto total functions. Two classes CFLSV
and CFLSVt are subclasses of CFLMV and CFLMVt consisting only of
singlevalued functions. Another function class CFLMV(
In the polynomial-time setting, multi-valued functions have been used to dene the notions of NPMV- and kPMV-selectivity. Here, we introduce CFLMVselectivity and its variants. ?? To describe a multi-valued function f , the expression \f : ! " is customarily used in the literature. This is equivalent to saying that f is a total mapping from to P( ). 3.1
We begin with a general notion of selectors.
De nition 1. Given a multi-valued function f : ! P( ) (called a selector), a language A is f -selective if, for any pair x; y 2 , (a) f ([ xy]) fx; yg, and (b) fx; yg \ A 6= ? implies both f ([ xy]) 6= ? and f ([ xy]) A.
As an essential di erence from two-way Turing machines, when a 1npda on
x
input [ y] produces a string, say, s on its output tape along each computation
path, the 1npda cannot scan the passed tape cells again and thus there seems
no general way of knowing that the produced string s is x or y unless the 1npda
is synchronous. To circumvent the lack of such a post-production checkup of the
output strings, we require the following extra technical setup. When a selector
x
handles a string of the form [ y], we want to provide an underlying machine with
[xy$$21], where $1 and $2 are designated endmarkers used for the rst and the second
tracks. To do so, we introduce the notion of \endmarked extensions." Given a
selector f , another function g is called the endmarked extension of f if, for any
distinct x; y 2 , (
De nition 2. Given a class F of multi-valued partial functions, a language A is F -selective if there exists a multi-valued function f and its endmarked extension f~ such that (i) A is f -selective and (ii) both f and f~ belong to F . We write F -SEL for the collection of all F -selective languages.
We stress that De nition 2 does not change the well-known selective language families, such as P-SEL and NPSV-SEL. For a further discussion on our introduction of endmarked extension, see Section 6.
Unlike P-SEL, however, we do not intend to discuss DFA-SEL and DCFL-SEL throughout this paper because they are too restrictive in practice to contain even their associated underlying language families REG and DCFL, respectively.
Let us make simple observations. Obviously, for any two function classes F and G, if F G, then F -SEL G-SEL. Next, we remark that a 1nfa can decide which of two given strings x and y in the form of [ xy] is lexicographically smaller than the other. This fact will be used in later arguments.
Let denote the lexicographic order (i.e., sort rstly by length and sort secondly by a xed alphabetical order).
Lemma 3. The function f de ned as f ([ xy]) = minfx; yg, where min is taken according to the lexicographic order, can be computed by a certain 1nfa. Proof. Given the function f , let us consider the following 1nfa M . On input x [ y], rst \guess" either x or y (i.e., nondeterministically choose either x or y), write down the guessed string, say, s. Assuming jxj = jyj, determine whether or not s = minfx; yg and then check whether jxj = jyj by reading the entire input. In the case of jxj 6= jyj, we immediately invalidate this computation path by entering a rejecting state. More precisely, we compare x and y symbol by symbol from left to right to check whether x precedes y or y precedes x according to the lexicographic order . If we discover that x precedes y, then we check whether s = x and jxj = jyj. If so, we accept; otherwise, we reject. When y precedes x, we do the same by exchanging x and y. 2
A quick application of the above lemma is the existence of special selectors. We say that a selector f is symmetric if f ([ xy]) = f ([ xy]) for any pair x; y 2 . It is possible to make certain selectors symmetric.
CFL2V-SEL, and CFL2Vt-SEL.
Lemma 5. CFLSVt-SEL CFL2V-SEL.
=
co-(CFLSVt-SEL) and co-(CFLSV-SEL)
The F -selectivity is associated with a certain partial pre-ordering, which
satis es re exivity and transitivity. We give a simple example of CFLSVt-selective
language using the standard lexicographic ordering. Given a machine M and an
input x, M (x) = 1 (resp., M (x) = 0) means that M accepts (resp., rejects) x.
Example 6 (
(
It is known that CFL is closed under union and inverse homomorphism but not intersection. Most F -SEL's are naturally closed under union. By sharp contrast, intersections of even NFASVt-selective languages possess arbitrarily high complexities.
= f0; 1g and assume that kA \ nk 1 holds for all n 2 N+. There exist two languages L1; L2 2 NFASVt-SEL satisfying A = L1 \ L2.
Proof. Using the standard lexicographic ordering on , we de ne L1 = fx 2 j 9y 2 A \ jxj[x y]g. By Lemma 3, the function f ([ xy]) = minfx; yg, where \min" is according to , belongs to NFASVt. Thus, f is an NFASVt-selector for L1. In a similar way, we de ne L2 = fx 2 follows that A = L1 \ L2. jxj[y x]g. It then 2
Since we can freely choose A in Lemma 7, we instantly obtain the following consequence. This is similar to the non-closure property of the class P-SEL of all P-selective sets under intersection [5]. Let TALLY be the set of all tally languages over arbitrary alphabets (i.e., languages consisting only of strings of the form ai for a certain xed symbol a 2 ).
for CFLSVt-SEL and CFLSV-SEL.
Proof. Take a tally language A not in NFASVt-SEL. By Lemma 7, there are two languages L1; L2 2 NFASVt-SEL for which A = L1 \ L2. If NFASVt-SEL is closed under intersection, then A must be in NFASVt-SEL, a contradiction. 2
Note that CFL \ TALLY NFASVt-SEL because all \unary" contextfree languages are regular. However, it is not known whether or not CFL CFLSVt-SEL.
Next, we argue various closure properties of CFLSVt-SEL. The rst property is under a certain weak form of many-one reduction. Given two languages A and B, we say that A is NFASVt-translatable, denoted by A tNrFaAnSsVt B, if there exists a synchronous 1nfa N (called a translator) such that, on input x, N produces a single valid string, say, w on its output tape such that x 2 A i w 2 B. If we further require N to satisfy the length decreasing property (i.e., the length of any string produced on the output tape must be strictly shorter than the input length), then we instead use the term of length-decreasing NFASVttranslatability. We claim the following lemma. In comparison, P-SEL is known to be closed downward under polynomial-time truth-table reductions [10].
is, for any two languages A and B, if A tNrFaAnSsVt B and B 2 CFLSVt-SEL, then A 2 CFLSVt-SEL.
Proof. For any two languages A and B, assume that A tNrFaAnSsVt B via a translator N with synchronized tape heads and that B 2 CFLSVt-SEL via a selector f . Let Nf denote a 1npda computing f . For simplicity, we assume that A and B are languages over the same alphabet, say, . We want to show that A 2 CFLSVt-SEL. Given two strings x; y 2 , assume that N (x) produces a single valid string, say, z and similarly N (y) produces w. Next, we de ne g([ xy]) = x if f ([ wz]) = z, and g([ xy]) = y if f ([ wz]) = w. We claim that g is a selector for A. Let us consider the case where fx; yg\A 6= ?. If x 2 A and y 2= A, then z 2 A and w 2= A; thus, we obtain g([ xy]) = x 2 A. Assume that x; y 2 A. Since z; w 2 A by the de nition of N , we conclude that fx; yg \ g([ xy]) 6= ?.
Next, we show that g is in CFLSVt by constructing an appropriate 1npda M computing g. On input [ xy], M simulates both N (x) and N (y) simultaneously by reading [ xy] symbol by symbol since N 's tape heads are synchronized, and it produces [ wz] on an \imaginary" output tape. During this process, as each symbol of the string [ wz] is produced on the imaginary tape, M simulates one step (together with a series of -moves) of Nf on . It is not di cult to see that M computes g correctly. 2
As for P-selectivity, Buhrman and Torenvliet [1] demonstrated that a language A is in P i A is polynomial-time self-reducible and P-selective. In a similar spirit, we show the following theorem concerning NFASVt-translatability.
decreasing NFASVt-translatable to A, then A belongs to CFL \ co-CFL. Proof. Given any language A, let M denote a 1nfa that translates A to A. Let f be a CFLSVt-selector for A and take an appropriate 1npda Mf computing f . To show that A 2 CFL, we de ne N as follows. On input x, N runs M on x. While M produces z along a certain computation path, N produces [ xz] on an imaginary tape of N . Note that x 6= z since x 2 A i z 2 A. Whenever a single symbol is produced on the imaginary tape, N simulates one step (together with a series of -moves, if necessary) of Mf on using a stack and the imaginary tape. Since jzj < jxj, by simulating Mf , N easily notices which of x and z is a valid outcome of Mf . If f ([ xz]) = x, then N accepts; otherwise, N rejects.
Next, we show that N correctly recognizes A. Assume that x 2 A. If f ([ xz]) = z, then we conclude that z 2 A because fx; zg \ A 6= ?. However, this implies x 2= A, a contradiction. Thus, we obtain f ([ xz]) = x; in other words, N accepts. Next, assume that x 2= A. If f ([ xz]) = x, then z 2= A holds because, otherwise, f ([ xz]) = z must hold. Since z 2= A, we obtain x 2 A, a contradiction. This implies f ([ xz]) = z, and thus N rejects. Therefore, N correctly recognizes A.
By Lemma 5, A is also CFLSVt-SEL. Moreover, A is also length-preserving NFASVt-translatable to A. Since the above argument for A also works for A, we thus conclude that A is in CFL. Therefore, A belongs to CFL \ co-CFL. 2
Proof. Let A denote any language over alphabet in CFLSVt-SEL and let h be any homomorphism from another alphabet to . Our goal is to show that the language Ah 1 = fx 2 j h(x) 2 Ag belongs to CFLSVt-SEL. Take a selector f in CFLSVt for A and consider a 1npda M computing its endmarked extension f~. Consider the following algorithm. On input [ y], we guess z 2 fx; yg x and produce it on an output tape. At the same time, we apply h to each symbol of [ xy]. By adjusting the size of obtained strings by h symbol by symbol, we run M using an \imaginary" output tape. When M ends its computation, M produces either $1 or $2, which indicates which of x and y is actually produced. We accept the input if the string produced by M matches the guessed string; otherwise, we reject the input.
We will continue exploring basic properties of F -selective languages. In Example
6(
(
CFL2V-SEL. (
CFLSVt-SEL.
Proof. (
(
(
The family NFASVt-SEL contains REG by Example 6(
Proof. Consider the non-regular language Lab = fanbn j n 2 Ng over the binary
alphabet = fa; bg. Assume that Lab 2 NFASVt-SEL and take a selector f for
Lab in NFASVt. This f induces a partial pre-order f on as in Example
6(
In Proposition 12(
CFLSV-SEL, then CFL2Vt v(r+ef) CFLSVt.
Proof. Assume that CFL CFLSV-SEL. Take any function f 2 CFL2Vt having its range D of size exactly 2. Let D = fy1; y2g and let d = maxfjyj : y 2 Dg. Let M denote a 1npda computing f . De ne L = f[ xy] j jxj d; y 2 f (x)g, which belongs to CFL since D is nite. Since L 2 CFLSV-SEL by our assumption, take a CFLSV-selector g for L and let N be its underlying 1npda that computes g with a write-once output tape. We then de ne g~ as g^(x) = g([uv]) for u = [ yx1] and v = [ yx2]. Note that g^ is a single-valued function.
Consider the following 1npda, say, N . On input x, compute g^ on x and produce its outcome on an imaginary tape. Instead of producing an outcome of the form [ xy] with y 2 D, write down y on the output tape. Let h be a function computed by this machine N . Note that h is in CFLSVt since f is a total function.
Finally, we want to show that f v(r+ef) h. Assume that f (x) 6= ?. Consider the case where f (x) = fy1; y2g. Since [ yx1]; [ yx2] 2 L, g^(x) must output a single string of the form [ wx] in L, where w 2 fy1; y2g. By the de nition of h, we obtain h(x) = w. The case of f (x) = fyg D is similarly treated. 2
Lemma 14 helps us prove the following assertion.
Proposition 15. CFL2V-SEL = CFLSV-SEL ) CFL CFL2Vt-SEL = CFLSVt-SEL.
CFLSV-SEL )
Proof. Assume that CFLSV-SEL = CFL2V-SEL. Since CFL CFL2V-SEL
by Proposition 12(
We further discuss the limitations of CFLSVt-SEL and CFLMV(
(
Analogously to the polynomial(-time) hierarchy over P and NP, the CFL hierarchy was introduced in [19] over DCFL and CFL by way of respectively viewing DCFL and CFL as P and NP. We quickly review the de nition of this intriguing hierarchy. An oracle 1npda is a 1npda equipped with a write-once query tape by which the 1npda makes queries (adaptively) to a given oracle. Such a query tape is marked by two endmarkers fcj; $g, where $ is placed on a tape cell whose index is bounded by O(n) [19]. Every time when a query is made, the query tape is automatically initialized with the endmarkers. The role of the oracle is to reset the oracle 1npda's inner state to a \yes" state (qyes) or a \no" state (qno) according to the case where a query word belongs to the oracle or it does not, respectively. Given a language A, the notation CFLTA (or CFLT (A)) expresses the collection of all languages recognized by those oracle 1npda's with an access to the oracle A. For a language family C, we use the notation CFLCT (or CFLT (C)) for the union S CFLTA. The CFL hierarchy is f kCFL; kCFL; kCFL j k 2 N+g [19], where A1C2FLC = DCFL, 1CFL = CFL, kCFL = co- kCFL, kC+F1L = CFLT ( kCFL), and kC+F1L = DCFLT ( kCFL) for each k 1.
We have seen a lower bound of the complexity of CFLSVt-SEL in Proposition 12. In what follows, we show an upper bound of the complexity of CFLSVt-SEL. In comparison, we note that P-SEL NP=lin \ co-NP=lin [4]. It is important to note that our advice can use an arbitrary alphabet, not necessarily limited to f0; 1g in the case of NP=lin.
CFLT (CFL(
Proof. Since co-(CFLSVt-SEL) = CFLSVt-SEL by Lemma 5, it su ces to
prove that CFLSVt-SEL CFLT (CFL(
We use the advice alphabet f0; 1; ag and de ne h(n) = an if L \ n = ?, and
wn otherwise, where wn (2 L) is the special player (i.e., node) of the tournament
from which all the other players (nodes) can be reached along paths of length at
most 2. We de ne A = f[ wu] j u = [ xz]; (w; x) 2 E _ [(w; z) 2 E ^ (z; x) 2 E]g. We
claim that A is in CFL(
Multi-valued functional versions of CFLTA and CFLCT are denoted respectively by CFLMVTA (or CFLMVT (A)) and CFLMVCT (or CFLMVT (C)) [18]. The CFLMV hierarchy then consists of language families: 1CFLMV = CFLMV, and kC+F1LMV = CFLMVT ( kCFL), and kCFLMV = co- kCFLMV for every level k 1 [20]. Similarly, kCFLSV is de ned for every k 1.
Here, we only remark that Lemmas 4{5, Theorem 10, and Proposition 12(
kC+F1L2V-SEL.
kCFL2V-SEL 6= kC+F1L2V-SEL.
Since kCFL kC+F1L2V-SEL holds by Proposition 18, the assumption
kCFL2V-SEL implies kCFL2V-SEL 6= kC+F1L2V-SEL. 2
Proposition 12(
1, kCFL
CFL \ k CFLSVt-SEL. k
2. If kCFL = kCFL, then
CFL k
CFLSVt-SEL. k Proof of Theorem 20. We rst note the following claim.
Claim 22 For any index k 1. Given a language A, A 2 kCFL \ kCFL i A 2 kCFLSVt.
The case of k = 1 of Claim 22 was already shown as [21, Lemma 2.1] and its generalization for k 2 can be similarly proven.
Let A 2 kCFL \ kCFL. Claim 22 implies that A is in kCFLSVt. De ne f ([ xy]) = [ uv], where u = A(x) and v = A(y).
Next, we claim the following. Claim 23 Let k as g([ xy]) = [ pp((xy))] for all x; y 2
CFLSVt. The function g de ned k CFLSVt. k
The proof of this claim is quite technical. One may prove it by rst establishing that underlying oracle 1npda's can be replaced by oracle 1nfa's having access to Dyck languages, as shown for kCFL in [19, arXiv version]. Proof of Claim 23. This proof relies on a result of [19, arXiv version]. Let k 2 and let p 2 CFLSVt \ Ffin. Recall that, in [19], for any language A, two language families k mNF;kA;A and mNF;kA;A were introduced. In a similar way, we can de ne mNF;kASVtA and mNF;kASVtA as follows. Let mNF;1ASVtA = (NFASVt)Am,
NFA;A mNF;kASVtA = co- mNF;kASVtA, and mNF;kA+1SVtA = (NFASVt)mm;k 1 for any k 1. Following an argument given in [19, arXiv version], we obtain the following claim.
the Dyck language.
1,
CFLSVt = k
mNF;kASVtDY CK , where DY CK denotes
Since f 2 CFLSVt, take an oracle 1nfa M that computes f with accexss to oracle B in kmNF;kA;D1Y CK . Consider the following machine N . On input [ y], N simulates in parallel both M (x) and M (y) without using any stack. If M (x) produces u and M (y) produces w on their query tapes, then N produces [ wu~~] on its query tape, where u~ and w~ are \-extensions of u and w. Moreover, N outputs [ ab], where a and b are outcomes of M on x and y, respectively. Finally, de ne C = f[ wu~~] j u; w 2 Bg. It was shown in [19] that kCF1L = mNF;kA;D1Y CK . Since C 2 kCF1L, we obtain C 2 mNF;kA;D1Y CK . By the de nition of N and C, the function de ned by g([ xy]) = [ ff((xy))] is computed by N with the oracle C. Therefore, g belongs to kCFLSVt. 2
By Claim 24, it follows that the function f belongs to kCFLSVt. Next, consider the following oracle 1npda, say, N . On input [ xy], guess b 2 f0; 1g and write x (resp., y) on an output tape if b = 0 (resp., b = 1). At the same time, calculate f ([ xy]) and let z be its valid outcome (along a certain accepting computation path). If b = 0 and z is either [ 00] or [ 11], then N accepts. In the case where z is [ 01] (resp., [ 10]), N accepts if b = 1 (resp., b = 0). In all other cases, N rejects. Notice that N runs with synchronized tape heads. Let h denote the function computed by N . It is not di cult to show that h is indeed a selector for A. 2
Let us consider a basic relationship between \re nement" and \selectivity." Proposition 25. For each level k 2, kCFL2V v(r+ef) kCFLSV implies kCFL kCFLSV-SEL. The same statement holds when kCFLSV is replaced by kCFLSVt.
2. If kCFL = Proof. It is shown in [19, arXiv version] that kC+F1L. From kCFL = kCFL, it follows that ally, we can improve this to (*) kCFL = kCFL implies kCFL = kC+F1LMV vref kC+F1LSV [20]; actukCFLMV vref kCFLSV.
2,
(+) CFLSV vref k kC+F1LSVt.
Proof of Claim 27. Let f 2 kCFLSV. Assume that k 2. Since kCFLSV = CFLSVT ( kCF1L) by the de nition, take an oracle 1npda M and an oracle B in kCF1L computing f . Let C = f1y j y 2 Bg [ f0x j f (x) 6= ?g. Since f1y j y 2 Bg is in kCF1L and f0x j f (x) 6= ?g is in kCFL, it follows that C belongs to kCFL. Consider the following machine. On input x, guess b 2 f0; 1g. If b = 1, then simulate M with C as an oracle. If b = 0, then query 0x to C. If C's answer is \yes," then reject; if the answer is \no," then accept. Moreover, whenever M queries y, N queries 1y.
Let g denote the function computed by N with C. Note that g belongs to CFLSVtC CFLSVt kCFL kC+F1LSVt. Moreover, it is not di cult to show that g is a total function and that, if x 2 dom(f ), f (x) = g(x). Therefore, g is a pseudo re nement of f . 2
By Claim 27 together with (*), we obtain kCFL2V v(r+ef) kC+F1LSVt. Since kCFL = kC+F1L, we obtain kCFLSVt = kC+F1LSVt. Therefore, we can conclude that kCFL2V v(r+ef) kCFLSVt.
Notice that combining Propositions 25 and 26 also leads to Corollary 21. 6
The study of e cient selectivity was initiated in 1979 by Selman [9] using polynomial-time computable selectors and it has been since then expanded to other types of selectors. An introduction of selectivity to formal languages and automata theory was found in [13]. To further broaden the scope of study on the selectivity issues in formal languages and automata theory, we have considered in this paper one-way nondeterministic pushdown automata as an underlying machine model to compute selectors.
It is unfortunate that we have left numerous selectivity issues unsettled throughout this paper. For example, it is unclear at this moment that the introduction of the notion of \endmarked extension" of selectors in De nition 2 is truly necessary. We hope to prove that the use of this endmarked extension is actually redundant and we can simplify De nition 2 without endmarked extension.