This paper continues a systematic and comprehensive study on the structural properties of CFL functions, which are in general multivalued partial functions computed by one-way one-head nondeterministic pushdown automata equipped with write-only output tapes (or pushdown transducers), where CFL refers to a relevance to context-free languages. The CFL functions tend to behave quite differently from their corresponding context-free languages. We extensively discuss containments, separations, and refinements among various classes of functions obtained from the CFL functions by applying Boolean operations, functional composition, many-one relativization, and Turing relativization. In particular, Turing relativization helps construct a hierarchy over the class of CFL functions. We also analyze the computational complexity of optimization functions, which are to find optimal values of CFL functions, and discuss their relationships to the associated languages.
In a traditional field of formal languages and automata, we have dealt primarily with languages because of their practical applications to, for example, a parsing analysis of programming languages. Most fundamental languages listed in many undergraduate textbooks are, unarguably, regular (or rational) languages and context-free (or algebraic) languages.
Opposed to the recognition of languages, translation of words, for
example, requires a mechanism of transforming input words to output words. Aho
et al. [
Based on a model of polynomial-time nondeterministic Turing machine,
computational complexity theory has long discussed the structural complexity of
various NP function classes, including NPMV, NPSV, and NPSVt (where MV and
SV respectively stand for “multi-valued” and “single-valued” and the subscript
“t” does for “total”). See, e.g., a survey [
Within a scope of formal languages and automata, there is also rich
literature concerning the behaviors of nondeterministic finite automata equipped with
write-only output tapes (known as rational transducers) and properties of
associated multi-valued partial functions (known also as rational transductions).
Significant efforts have been made over the years to understand the
functionality of such functions. A well-known field of functions include “CFL functions,”
which were formally discussed in 1963 by Evey [
In recent literature, fascinating structural properties of CFL functions have
been extensively investigated. Konstantinidis et al. [
Amazingly, there still remains a vast range of structural properties that await
for further investigation. Thus, we wish to continue a coherent and systematic
study on the structural behaviors of the aforementioned CFL functions. This
paper aims at exploring fundamental relationships (such as, containment,
separation, and refinement) among the above function classes and their natural
extensions via four typical operations: (i) Boolean operations, (ii) functional
composition, (iii) many-one relativization, and (iv) Turing relativization. The
last two operations are a natural generalization of many-one and Turing
CFLreducibilities among languages [
Every nondeterministic machine with an output tape can be naturally seen as
a process of generating a set of feasible “solutions” of each instance. Among those
solutions, it is useful to study the complexity of finding “optimal” solutions. This
gives rise to optimization functions. Earlier, Krentel [
To see a role of functions during a process of recognizing languages, K¨obler
and Thierauf [
All omitted or abridged proofs, because of the page limit, will appear shortly in a complete version of this paper. 2
Formal Languages. Let N be the set of all natural numbers (i.e., nonnegative integers) and set N+ = N − {0}. Throughout this paper, we use the term “ polynomial” to mean polynomials on N with nonnegative coefficients. In particular, a linear polynomial is of the form ax + b with a, b ∈ N. The notation A − B for two sets A and B indicates the set difference {x | x ∈ A, x 6∈ B}. Given any set A, P(A) denotes the power set of A. A set Σk (resp., Σ≤k), where k ∈ N, consists only of strings of length k (resp., at most k). Here, we set Σ∗ = Sk∈N Σk. The empty string is always denoted λ. Given any language A over Σ, its complement is Σ∗ − A, which is also denoted by A as long as Σ is clear from the context.
We adopt a track notation [xy] from [
As our basic computation model, we use one-way one-head nondeterministic
pushdown automata (or npda’s, in short) allowing λ-moves (or λ-transitions)
of their input-tape heads. The notations REG and CFL stand for the families
of all regular languages and of all context-free languages, respectively. For each
number k ∈ N+, the k-conjunctive closure of CFL, denoted by CFL(k), is defined
to be {Tik=1 Ai | A1, A2, . . . , Ak ∈ CFL} (see, e.g., [
Given any language A (used as an oracle), CFLTA (or CFLT (A)) expresses a
collection of all languages recognized by npda’s equipped with write-only query
tapes with which the npda’s make non-adaptive oracle queries to A, provided
that all computation paths of the npda’s must terminate in O(n) steps no
matter what oracle is used [
For any language A, the characteristic function for A, denoted by χA, is a function defined as χA(x) = 1 if x ∈ A and χA(x) = 0 otherwise. We also use a quasi-characteristic function ηA, which is defined as ηA(x) = 1 for any string x in A and ηA(x) is not defined for all the other strings x.
Concerning all function classes discussed in this paper, it is natural to concentrate only on functions whose outcomes are bounded in size by fixed polynomials. More precisely, a multi-valued partial function f : Σ∗ → P(Γ ∗) is called polynomially bounded (resp., linearly bounded) if there exists a polynomial (resp., a linear polynomial) p such that, for any two strings x ∈ dom(f ) and y ∈ Γ ∗, if 1 To describe a multi-valued partial function f , the expression “f : Σ∗ → Γ ∗” is customarily used in the literature. However, the current expression “f : Σ∗ → P(Γ ∗)” matches a fact that the outcome of f on each input string in Σ∗ is a subset of Γ ∗. y ∈ f (x) then |y| ≤ p(|x|) holds. In this paper, we understand that all function classes are made of polynomially-bounded functions. Given two alphabets Σ and Γ , a function f : Σ∗ → P(Γ ∗) is called length preserving if, for any x ∈ Σ∗ and y ∈ Γ ∗, y ∈ f (x) implies |x| = |y|.
Whenever we refer to a write-only tape, we always assume that (i) initially, all cells of the tape are blank, (ii) a tape head starts at the so-called start cell, (iii) the tape head steps forward whenever it writes down any non-blank symbol, and (iv) the tape head can stay still only in a blank cell. An output (outcome or output string) along a computation path is a string produced on the output tape after the computation path is terminated. We call an output string valid (or legitimate) if it is produced along a certain accepting computation path.
To describe npda’s, we take the following specific definition. For any given
function f : Σ∗ → P(Γ ∗), an npda N equipped with a one-way read-only
input tape and a write-only output tape that computes f must have the form
(Q, Σ, {c|, $}, Θ, Γ, δ, q0, Z0, Qacc, Qrej ), where Q is a set of inner states, Θ is a
stack alphabet, q0 (∈ Q) is the initial state, Z0 (∈ Θ) is the stack’s bottom
marker, and δ : (Q − Qhalt) × (Σˇ ∪ {λ}) × Θ → P(Q × Θ∗ × (Γ ∪ {λ})) is a
transition function, where Qhalt = Qacc ∪ Qrej , Σˇ = Σ ∪ {c|, $}, and c| and $ are
respectively left and right endmarkers. It is important to note that, in
accordance with the basic setting of [
A function class CFLMV is composed of all (multi-valued partial) functions
f , each of which maps Σ∗ to P(Γ ∗) for certain alphabets Σ and Γ and there
exists an npda N with a one-way read-only input tape and a write-only output
tape such that, for every input x ∈ Σ∗, f (x) is a set of all valid outcomes of
N on the input x. The termination condition imposed on our npda’s obviously
leads to an anticipated containment CFLMV ⊆ NPMV. Another class CFLSV is
a subclass of CFLMV consisting of single-valued partial functions. In addition,
CFLMVt and CFLSVt are respectively restrictions of CFLMV and CFLSV onto
total functions. Those function classes were discussed earlier in [
An important concept associated with multi-valued partial functions is
refinement [
Let us discuss our theme of the structural complexity of various classes of (multivalued partial) functions by exploring fundamental relationships among those function classes. In the course of our discussion, we will unearth an exquisite nature of CFL functions, which looks quite different from that of NP functions.
We begin with demonstrating basic features of CFL functions. First, let us
present close relationships between CFL functions and context-free languages.
Notice that, for any function f in CFLMV, both dom(f ) and ran(f ) belong
to CFL. It is useful to recall from [
Lemma 1. For any function f ∈ CFLMV, there exist a language A ∈ CFL and a linear polynomial p such that, for every pair x and y, y ∈ f (x) iff (i) [ xy˜˜] ∈ A, (ii) |y| ≤ p(|x|), and (iii) |x˜| = |y˜| for certain strings x˜ and y˜, which are \-extensions of x and y, respectively.
An immediate application of Lemma 1 leads to a functional version of the
well-known pumping lemma [
Lemma 2. (functional pumping lemma for CFLMV) Let Σ and Γ be any two alphabets and let f : Σ∗ → P(Γ ∗) be any function in CFLMV. There exist three numbers m ∈ N+ and c, d ∈ N that satisfy the following condition. Any string w ∈ Σ∗ with |w| ≥ m and any string s ∈ f (w) are decomposed into w = uvxyz and s = abpqr such that (i) |vxy| ≤ m, (ii) |vybq| ≥ 1, (iii) |bq| ≤ cm + d, and (iv) abipqir ∈ f (uvixyiz) for any number i ∈ N. In the case where f is further length preserving, the following condition also holds: (v) |v| = |b| and |y| = |q|. Moreover, (i)–(ii) can be replaced by (i’) |bq| ≥ 1.
Boolean operations over languages in CFL have been extensively discussed
in the past literature (e.g., [
Proposition 3. Let k, m ≥ 1. 1. CFLMV(max{k, m}) ⊆ CFLMV(k) ∨ CFLMV(m) ⊆ CFLMV(km). 2. CFLMV(max{k, m}) ⊆ CFLMV(k) ∧ CFLMV(m) ⊆ CFLMV(k + m). 3. CFLSV(k) $ CFLSV(k + 1).
Note that Proposition 3(3) follows indirectly from a result in [
Fenner et al. [
The use of set difference in the above definition makes us introduce another class operator . Given two sets F , G of functions, F G denotes a collection of functions h satisfying the following: for certain two functions f ∈ F and g ∈ G, h(x) = f (x) − g(x) (set difference) holds for any x.
In Proposition 4, we will give basic properties of functions in co-CFLMV and of the operator . To describe the proposition, we need to introduce a new function class, denoted by NFAMV, which is defined in a similar way of introducing CFLMV using, in place of npda’s, one-way (one-head) nondeterministic finite automata (or nfa’s, in short) with write-only output tapes, provided that the termination condition (i.e., all computation paths terminate in linear time) must hold.
Proposition 4. 1. co-(co-CFLMV) = CFLMV. 2. co-CFLMV = NFAMV CFLMV. 3. CFLMV CFLMV = CFLMV ∧ co-CFLMV. 4. CFLMV 6= co-CFLMV. The same holds for CFLMVt.
Proof Sketch. We will show only (2). (⊇) Let f ∈ NFAMV CFLMV and take two functions h ∈ NFAMV and g ∈ CFLMV for which f (x) = h(x) − g(x) (set difference) for all inputs x ∈ Σ∗. Choose a linear polynomial p satisfying that, for every pair (x, y), y ∈ h(x) ∪ g(x) implies |y| ≤ p(|x|). By the definition of f , it holds that f (x) = Σ≤p(|x|) − (g(x) ∪ (Σ≤p(|x|) − h(x))) for all x. For simplicity, we define r(x) = g(x) ∪ (Σ≤p(|x|) − h(x)) for every x. It thus holds that f (x) = Σ≤p(|x|) − r(x). It is not difficult to show that r is in CFLMV.
(⊆) Let f ∈ co-CFLMV. There are a linear polynomial p and a function g ∈ CFLMV satisfying that f (x) = Σ≤p(|x|) − g(x) for all x. We set h(x) = Σ≤p(|x|). Since h ∈ NFAMV, we conclude that f belongs to NFAMV CFLMV. 2
Another basic operation used for functions is functional composition. The functional composition f ◦ g of two functions f and g is defined as (f ◦ g)(x) = Sy∈g(x) f (y) for every input x. For two function classes F and G, let F ◦ G = {f ◦ g | f ∈ F , g ∈ G}. In particular, we inductively define CFLSV(1) = CFLSV and CFLSV(k+1) = CFLSV ◦ CFLSV(k) for each index k ≥ 1. For instance, the function f (x) = {xx} defined for any x ∈ Σ∗ belongs to CFLSV(2). This fact yields, e.g., CFLSV(2) ⊆ CFLSV(4). Unlike NP function classes (such as, NPSV and NPMV), CFLSVt (and therefore CFLSV and CFLMV) is not closed under functional composition.
Proposition 5. CFLSVt 6= CFLSVt(2). (Also for CFLSV and CFLMV.) Proof Sketch. Let Σ = {0, 1, \} be our alphabet and define fdup\(x) = {x\x} for any input x ∈ {0, 1}∗ and fdup\(x) = {λ} for any other inputs x. It is not difficult to show that fdup\ ∈ CFLSVt(2). To show that fdup\ 6∈ CFLSVt, we assume that fdup\ ∈ CFLSVt. Let DU P\ be a “marked” version of DU P (duplication), defined as DU P\ = {x\x | x ∈ {0, 1}∗}. It holds that, for every w 6= λ, w ∈ ran(fdup\) iff there is a string x such that w ∈ fdup\(x) iff w ∈ DU P\. Thus, DU P\ ∪ {λ} = ran(fdup\). Note that DU P\ ∈ CFL since fdup\ ∈ CFLSVt. However, it is well-known that DU P\ ∈/ CFL. This leads to a contradiction. Therefore, we conclude that fdup\ 6∈ CFLSVt. 2
To examine the role of functions in a process of recognizing a given language,
a //-advice operator, defined by K¨obler and Thierauf [
In the polynomial-time setting, it holds that NP ∩ co-NP = P//NPSVt [
Proposition 6. 1. REG//NFASVt * CFL and CFL * REG//NFAMV. 2. REG//NFASVt is closed under complement but REG//NFAMV is not. 3. CFL ∩ co-CFL $ REG//CFLSVt.
Proof Sketch. (1) Note that the language DU P# = {x#x | x ∈ {0, 1}∗}
(duplication) falls into REG//NFASVt by setting h(x#y) = y and B = {[ xx] |
x ∈ {0, 1}∗}. The key idea is the following claim. (*) A language L is in
REG//NFAMV iff L is recognized by a certain one-way two-head (non-sensing)
nfa (or an nfa(2), in short) with λ-moves. See a survey, e.g., [
(2) The non-closure property of REG//NFAMV follows from a fact that the class of languages recognized by nfa(2)’s is not closed under complement. Use the above claim (*) to obtain the desired result. 2
Bwfore closing this section, we exhibit a simple structural difference between languages and functions. It is well-known that all languages over the unary alphabet {1} in CFL belong to REG. On the contrary, there is a function f : {1}∗ → {0, 1}∗ such that f is in CFLMV but not in NFAMV. 4
Oracle computation is a natural extension of ordinary stand-alone computation by providing external information by way of query-and-answer communication.
Such oracle computation can realize various forms of relativizations, including
many-one and Turing relativizations and thus introduce relativized languages
and functions. By analogy with relativized NP functions (e.g., [
Proposition 8. 1. REG//CFLSVt ⊆ CFLCmFL(2) ∩ co-CFLCmFL(2). 2. CFL//CFLSVt ⊆ CFLCmFL(3).
Proof Sketch. We will prove only (2). For convenience, we write [x, y]T for [ xy]
in this proof. Let CFLm[
A A A
index k ≥ 1 [
CFL. Hence, A is in CFLBm ⊆ CFLCmF[2L], and thus L is in
Note that B is in CFLm
CFLCmF[3L]. Since CFLCmF[3L] = CFLCmFL(3) [
The second relativization is Turing relativization. A multi-valued partial function f belongs to CFLMVTA (or CFLMVT (A)) if there exists an oracle npda M having three extra inner states {qquery, qyes, qno} that satisfies the following three conditions: on each input x, (i) if M enters a query state qquery, then a valid string, say, s written on the query tape is sent to A and, automatically, the content of the query tape becomes blank and the tape head returns to the start cell, (ii) oracle A sets M ’s inner state to qyes if s ∈ A and qno otherwise, and (iii) all computation paths of M terminate in time O(n) no matter what oracle is used.
Obviously, CFLMVTA = CFLMVTA holds for any oracle A. Define CFLMVCT (or CFLMVT (C)) to be the union SA∈C CFLMVTA for a given language family C.
Analogously to the well-known NPMV hierarchy, composed of ΣkpMV and
ΠkpMV for k ∈ N+ [
For k ≥ 3, it is possible to give the exact characterization of REG//ΣkCFLSVt. This makes a sharp contrast with Proposition 6(3).
Proposition 10. For every index k ≥ 3, ΣkCFL ∩ ΠkCFL = REG//ΣkCFLSVt.
Proof Sketch. By extending the proof of Proposition 6(3), it is possible to show
that ΣkCFL ∩ ΠkCFL ⊆ REG//ΣkCFLSVt. Similarly to Proposition 6(2), it holds
that REG//ΣCFLSVt is closed under complement. It thus suffices to show that
k
REG//ΣkCFLSVt ⊆ ΣkCFL. This can be done by a direct simulation. 2
ΣkC+F1LSV = ΣkC+FeLSV.
Proof Sketch. Assuming ΣkCFLSV = ΣkC+F1LSV, let us take any language A ∈
ΣkC+F1L and consider ηA. It is not difficult to show that, for any index d ∈ N+,
A ∈ ΣCFL iff ηA ∈ ΣCFLSV. Thus, ηA ∈ ΣkC+F1LSV = ΣCFLSV. This implies
d d k
that A ∈ ΣCFL. Next, assume that ΣCFL = ΣkC+F1L. It is proven in [
Regarding refinement, from the proof of [8, Theorem 3] follows NFAMV vref
NFASV. This result leads to NFAMV ◦ CFLSV vref CFLSV in [
k
Recently, it was shown in [
An optimization problem is to find an optimal feasible solution that satisfy a given
condition. Krentel [
The first part of Proposition 13 comes from a fact that the function f (w) = max{g(w)}, where g(w) = {λ} ∪ {xiyi | w = x1\x2\x3#y1\y2\y3, xi = yiR, i ∈ {1, 2, 3}}, is in OptCFL but not in CFLSVt. This latter part is proven by applying the functional pumping lemma.
Note that, in the polynomial-time setting, a much sharper upper-bound of p OptP ⊆ Σ2 SVt is known. Similarly to OptCFL, let us define OptNFAEL using nfa’s M instead of npda’s with an extra condition that M (x) outputs only strings of the equal length. This new class is located within Σ2CFLSVt.
Proof Sketch. Let f ∈ OptNFAEL and take an underlying nfa N that forces f (x) to equal max{N (x)} for every x. Define an oracle npda M1 to simulate N on x and output, say, y. Simultaneously, query y#xR using a stack wisely. If its oracle answer is 1, enter an accepting state; otherwise, reject. Make another npda M2 receive y#xR, simulate N R on xR, and compare its outcome with yR, where the notation N R refers to an nfa that reverses the computation of N . 2 Proposition 15. 1. CFL ∪ co-CFL ⊆ REG//OptCFL ⊆ Σ4CFL ∩ Π4CFL. 2. CFL//OptCFL ⊆ Σ5CFL.
Proof Sketch. We will show only (1). Note that REG//OptCFL is closed under complementation. Let L ∈ CFL and take an npda M recognizing L. Define N1 as follows. On input x, guess a bit b. If b = 0, then output 0 in an accepting state. Otherwise, simulate M on x and output 1 along only accepting computation paths of M . Let h(x) be max{N1(x)} for all x’s. It follows that L = {[ h(xx)] | h(x) 6= Ø}. This proves that L ∈ REG//OptCFL. Next, let L ∈ REG//OptCFL. Since OptCFL ⊆ Σ4CFLSVt, we obtain L ∈ REG//Σ4CFLSVt. By Proposition 10, this implies that L belongs to Σ4CFL ∩ Π4CFL. 2