=Paper=
{{Paper
|id=Vol-1231/long17
|storemode=property
|title=Structural complexity of multi-valued partial functions computed by nondeterministic pushdown automata
|pdfUrl=https://ceur-ws.org/Vol-1231/long17.pdf
|volume=Vol-1231
|dblpUrl=https://dblp.org/rec/conf/ictcs/Yamakami14
}}
==Structural complexity of multi-valued partial functions computed by nondeterministic pushdown automata==
<pdf width="1500px">https://ceur-ws.org/Vol-1231/long17.pdf</pdf>
<pre>
    Structural complexity of multi-valued partial
      functions computed by nondeterministic
                pushdown automata
                           (Extended Abstract)

                               Tomoyuki Yamakami

              Department of Information Science, University of Fukui
                     3-9-1 Bunkyo, Fukui 910-8507, Japan



      Abstract. This paper continues a systematic and comprehensive study
      on the structural properties of CFL functions, which are in general multi-
      valued partial functions computed by one-way one-head nondeterministic
      pushdown automata equipped with write-only output tapes (or push-
      down transducers), where CFL refers to a relevance to context-free lan-
      guages. The CFL functions tend to behave quite differently from their
      corresponding context-free languages. We extensively discuss contain-
      ments, separations, and refinements among various classes of functions
      obtained from the CFL functions by applying Boolean operations, func-
      tional 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 func-
      tions, and discuss their relationships to the associated languages.

      Keywords: multi-valued partial function, oracle, Boolean operation, re-
      finement, many-one relativization, Turing relativization, CFL hierarchy,
      optimization, pushdown automaton, context-free language


1   Much Ado about Functions

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 exam-
ple, requires a mechanism of transforming input words to output words. Aho
et al. [1] studied machines that produce words on output tapes while reading
symbols on an input tape. Mappings on strings (or word relations) that are real-
ized by such machines are known as transductions. Since languages are regarded,
from an integrated viewpoint, as Boolean-valued (i.e., {0, 1}-valued) total func-
tions, it seems more essential to study the behaviors of those functions. This


                                       225
T.Yamakami. Structural complexity of multi-valued partial functions

  task is, however, quite challenging, because these functions often demand quite
  different concepts, technical tools, and proof arguments, compared to those for
  languages. When underlying machines are particularly nondeterministic, they
  may produce numerous distinct output values (including the case of no output
  values). Mappings realized by such machines become, in general, multi-valued
  partial functions transforming each admissible string to a certain finite (possibly
  empty) set of strings.
     Based on a model of polynomial-time nondeterministic Turing machine, com-
  putational complexity theory has long discussed the structural complexity of var-
  ious 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 [14].
      Within a scope of formal languages and automata, there is also rich litera-
  ture concerning the behaviors of nondeterministic finite automata equipped with
  write-only output tapes (known as rational transducers) and properties of as-
  sociated multi-valued partial functions (known also as rational transductions).
  Significant efforts have been made over the years to understand the functional-
  ity of such functions. A well-known field of functions include “CFL functions,”
  which were formally discussed in 1963 by Evey [4] and Fisher [6] and general
  properties have been since then discussed in, e.g., [3, 10]. CFL functions are gen-
  erally computed by one-way one-head nondeterministic pushdown automata (or
  npda’s, in short) equipped with write-only output tapes. For example, the function
  P ALsub (w) = {x ∈ {0, 1}∗ | ∃u, v [w = uxv], x = xR } for every w ∈ {0, 1}∗ is a
  CFL function, where xR is x in reverse. As subclasses of CFL functions, three
  fundamental function classes CFLMV, CFLSV, and CFLSVt were recognized
  explicitly in [19] and further explored in [20].
      In recent literature, fascinating structural properties of CFL functions have
  been extensively investigated. Konstantinidis et al. [10] took an algebraic ap-
  proach toward the characterization of CFL functions. In relation to cryptogra-
  phy, it was shown that there exists a pseudorandom generator in CFLSVt that
  “fools” every language in a non-uniform (or an advised) version of REG [19].
  Another function class CFLMV(2) in [20] contains pseudorandom generators
  against a non-uniform analogue of CFL. The behaviors of functions in those func-
  tion classes seem to look quite different from what we have known for context-free
  languages. For instance, the single-valued total function class CFLSV can be seen
  as a functional extension of the language family CFL ∩ co-CFL rather than CFL
  [20]. In stark contrast with a tidy theory of NP functions, circumstances that
  surround CFL functions differ significantly because of mechanical constraints
  (e.g., a use of stacks, one-way moves of tape heads, and λ-moves) that har-
  ness the behaviors of underlying npda’s with output tapes. One such example is
  concerning a notion of refinement [13] (or uniformization [10]). Unlike language
  families, a containment between two multi-valued partial functions is customar-
  ily replaced by refinement. Konstantinidis et al. [10] posed a basic question of
  whether every function in CFLMV has a refinement in CFLSV. This question


                                         226
T.Yamakami. Structural complexity of multi-valued partial functions

  was lately solved negatively [22] and this result clearly contrasts a situation that
  a similar relationship is not known to hold between NPMV and NPSV.
      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, sep-
  aration, 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 CFL-
  reducibilities among languages [21]. We use the Turing relativization to introduce
  a hierarchy of function classes ΣkCFL MV, ΠkCFL MV, and ΣkCFL SV for each level
  k ≥ 1, in which the first Σ-level classes coincide with CFLMV and CFLSV,
  respectively. We show that all functions in this hierarchy have linear space-
  complexity. With regard to refinement, we show that, if the CFL hierarchy of
                                                          CFL
  [21] collapses to the kth level, every function in Σk+1     MV has a refinement in
    CFL
  Σk+1 SV for every index k ≥ 2.
      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 [11] discussed properties of
  OptP that is composed of polynomial-time optimization functions. Here, we are
  focused on similar functions induced by npda’s with output tapes. We denote
  by OptCFL a class of those optimization CFL functions. This function class is
  proven to be located between CFLSVt and Σ4CFL SVt . Moreover, we show the
  class separation between CFLSVt and OptCFL.
      To see a role of functions during a process of recognizing languages, Köbler
  and Thierauf [9] introduced a //-advice operator by generalizing the Karp-Lipton
  /-advice operator, and they argued the computational complexity of languages
  in P//F and NP//F induced by any given function class F. Likewise, we discuss
  the complexity of REG//F and CFL//F when F are various subclasses of CFL
  functions, particularly CFLSVt and OptCFL.
      All omitted or abridged proofs, because of the page limit, will appear shortly
  in a complete version of this paper.

  2    A Starting Point
  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 “ poly-
  nomial” 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 kS∈ N, consists
  only of strings of length k (resp., at most k). Here, we set Σ ∗ = k∈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.


                                         227
T.Yamakami. Structural complexity of multi-valued partial functions

        We adopt a track notation [xy] from [15]. For two symbols σ and τ , [στ] expresses
  a new symbol. For two strings x = x1 x2 · · · xn and y = y1 y2 · · · yn of length n,
  [ xy] denotes a string [ xy11 ][ xy22 ] · · · [ xynn ]. Whenever |x| =
                                                                       6 |y|, we follow a convention
                                                                               m
  introduced in [15]: if |x| < |y|, then [ xy] actually means [ x#y ], where m = |y| − |x|
  and # is a designated new symbol. Similarly, when |x| > |y|, the notation [ xy]
  expresses [ y#xm ] with m = |x| − |y|.
        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
           Tk
  to be { i=1 Ai | A1 , A2 , . . . , Ak ∈ CFL} (see, e.g., [19]).
        Given any language A (used as an oracle), CFLA                  T (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 [21]. We use S                   the notation CFLCT (or CFLT (C)) for
  language family C to denote the union A∈C CFLA                        T . Its deterministic version
                              C
  is expressed as DCFLT . The CFL hierarchy {∆k , ΣkCFL , ΠkCFL | k ∈ N+ }
                                                                      CFL

  is composed of classes ∆CFL         1          = DCFL, Σ1CFL = CFL, ΠkCFL = co-ΣkCFL ,
      CFL               CFL                      CFL
  ∆k+1 = DCFLT (Πk ), and Σk+1                            = CFLT (ΠkCFL ) for each index k ≥ 1 [21].

  Functions and Refinement. Our terminology associated with multi-valued
  partial functions closely follows the standard terminology in computational com-
  plexity theory. Throughout this paper, we adopt the following convention: the
  generic term “function” always refers to “multi-valued partial function,” pro-
  vided that single-valued functions are viewed as a special case of multi-valued
  functions and, moreover, partial functions include total functions. We are in-
  terested in multi-valued partial functions mapping1 Σ ∗ to P(Γ ∗ ) for certain
  alphabets Σ and Γ . When f is single-valued, we often write f (x) = y instead
  of y ∈ f (x). Associated with f , dom(f ) denotes the domain of f , defined to be
  {x ∈ Σ ∗ | f (x) 6= Ø}. If x 6∈ dom(x), then f (x) is said to be undefined. The
  range ran(f ) of f is a set {y ∈ Γ ∗ | f −1 (y) 6= Ø}.
      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 concen-
  trate only on functions whose outcomes are bounded in size by fixed polynomials.
  More precisely, a multi-valued partial function f : Σ ∗ → P(Γ ∗ ) is called poly-
  nomially 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 cus-
       tomarily 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 Γ ∗ .



                                                228
T.Yamakami. Structural complexity of multi-valued partial functions

  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 in-
  put 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 accor-
  dance with the basic setting of [21], we consider only npda’s whose computation
  paths are all terminate (i.e., reach halting states) in O(n) steps,2 where n refers
  to input size. We refer to this specific condition regarding execution time as the
  termination condition.
       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 [19].
      An important concept associated with multi-valued partial functions is re-
  finement [13]. This concept (denoted by vref ) is more suitable to use than set
  containment (⊆). Given two multi-valued partial functions f and g, we say that
  f is a refinement of g, denoted by g vref f , if (1) dom(f ) = dom(g) and (2)
  for every x, f (x) ⊆ g(x) (as a set inclusion). We also say that g is refined by f .
  Given two sets F and G of functions, G vref F if every function g in G can be
  refined by a certain function f in F. When f is additionally single-valued, we
  call f a single-valued refinement of g.


   2
       If no execution time bound is imposed, a function computed by an npda that non-
       deterministically produces every binary string on its output tape for each input
       becomes a valid CFL function; however, this function is no longer an NP function.



                                           229
T.Yamakami. Structural complexity of multi-valued partial functions

  3    Basic Operations for Function Classes
  Let us discuss our theme of the structural complexity of various classes of (multi-
  valued 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 [21] a notion of \-extension. Assuming that
  \ 6∈ Σ, a \-extension of a given string x ∈ Σ ∗ is a string x̃ over Σ ∪ {\} satisfying
  the following requirement: x is obtained directly from x̃ simply by removing all
  occurrences of \ in x̃. For example, if x = 01101, then x̃ may be 01\1\01 or
  \0110\\1. The next lemma resembles Nivat’s representation theorem for rational
  transductions (see, e.g., [10, Theorem 2]).

  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)
  [ x̃ỹ ] ∈ A, (ii) |y| ≤ p(|x|), and (iii) |x̃| = |ỹ| for certain strings x̃ and ỹ, 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 [2].

  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) abi pq i r ∈ f (uv i xy i z) 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., [16, 21]). Similarly, it is possible to consider Boolean
  operations that are directly applicable to functions. In particular, we are focused
  on three typical Boolean operations: union, intersection, and complement. Let us
  define the first two operations. Given two function classes F1 and F2 , let F1 ∧ F2
  (resp., F1 ∨ F2 ) denote a class of all functions f defined as f (x) = f1 (x) ∩ f2 (x)
  (set intersection) (resp., f (x) = f1 (x) ∪ f2 (x), set union) over all inputs x, where
  f1 ∈ F1 and f2 ∈ F2 . Expanding CFLMV(2) in Section 1, we inductively define
  a k-conjunctive function class CFLMV(k) as follows: CFLMV(1) = CFLMV
  and CFLMV(k + 1) = CFLMV(k) ∧ CFLMV for any index k ∈ N+ . Likewise,
  CFLSV(k) is defined using CFLSV instead of CFLMV.

  Proposition 3. Let k, m ≥ 1.
   1. CFLMV(max{k, m}) ⊆ CFLMV(k) ∨ CFLMV(m) ⊆ CFLMV(km).


                                            230
T.Yamakami. Structural complexity of multi-valued partial functions

   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 [12].
      Fenner et al. [5] considered “complements” of NP functions. Likewise, we can
  discuss complements of CFL functions. Let F be any family of functions whose
  output sizes are upper-bounded by certain linear polynomials. A function f is in
  co-F if there are a linear polynomial p, another function g ∈ F, and a constant
  n0 ∈ N such that, for any pair (x, y) with |x| ≥ n0 , y ∈ f (x) iff both |y| ≤ p(|x|)
  and y 6∈ g(x) holds. This condition implies that f (x) = Σ ≤a|x|+b − g(x) (set
  difference) for all x ∈ Σ ≥n0 . The finite portion Σ <n0 of inputs is ignored.
      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 intro-
  ducing 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
  S           composition f ◦ g of two functions f and g is defined as (f ◦ g)(x) =
    y∈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


                                         231
T.Yamakami. Structural complexity of multi-valued partial functions

  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öbler and Thierauf [9], is quite useful. Given
  a class F of functions, a language L is in CFL//F if there exists a language
  B ∈ CFL and a function h ∈ F satisfying L = {x | ∃ y ∈ h(x) s.t. [ xy] ∈
  B}. Analogously, REG//F is defined using REG instead of CFL. This operator
  naturally extends a /-advice operator of [15, 17].
      In the polynomial-time setting, it holds that NP ∩ co-NP = P//NPSVt [9].
  A similar equality, however, does not hold for CFL functions.
  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}∗ } (du-
  plication) 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., [7], for this model.
  Now, consider Lpal = {x#xR | x ∈ {0, 1}∗ } (palindromes). Since Lpal cannot be
  recognized by any nfa(2), it follows that Lpal 6∈ REG//NFAMV.
      (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 and Two Relativizations
  Oracle computation is a natural extension of ordinary stand-alone computation
  by providing external information by way of query-and-answer communication.


                                          232
T.Yamakami. Structural complexity of multi-valued partial functions

  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., [14]), let us con-
  sider many-one and Turing relativizations of CFL functions. The first notion
  of many-one relativization was discussed for languages in automata theory [8,
  21] and we intend to extend it to CFL functions. Given any language A over
  alphabet Γ , a function f : Σ ∗ → P(Γ ∗ ) is in CFLMVA    m (or CFLMVm (A)) if
  there exists an npda M with two write-only tapes (one of which is a standard
  output tape and the other is a query tape) such that, for any x ∈ Σ ∗ , (i) along
  any accepting computation path p of M on x (notationally, p ∈ ACCM (x)),
  M produces a query string yp on the query tape as well as an output string zp
  on the output tape and (ii) f (x) equals the set {zp | yp ∈ A, p ∈ ACCM (x)}.
  Such an M is referred to as an oracle npda. Given S any language family C, we
  further set CFLMVCm (or CFLMVm (C)) to be A∈C CFLMVA             m . Similarly, we
                 A              C
  define CFLSVm and CFLSVm by additionally demanding the size of each out-
  put string set is at most 1. Using CFLSVAm , a relativized language family CFLm
                                                                                   A
                                          A                       A
  defined in [21] can be expressed as CFLm = {L | ηL ∈ CFLSVm }.
  Lemma 7. 1. CFLMVREG  m   = CFLMV and CFLSVREG
                                             m   = CFLSV.
            (k+1)         CFL(k)
   2. CFLSV       = CFLSVm       .
  Proposition 8. 1. REG//CFLSVt ⊆ CFLCFL(2)
                                     m      ∩ co-CFLCFL(2)
                                                    m      .
                       CFL(3)
  2. CFL//CFLSVt ⊆ CFLm       .

  Proof Sketch. We will prove only (2). For convenience, we write [x, y]T for [ xy]
  in this proof. Let CFLA            A            A                      A
                         m[1] = CFLm and CFLm[k+1] = CFLm (CFLm[k] ) for every
  index k ≥ 1 [21]. Let L ∈ CFL//CFLSVt and take an npda M and a function
  h ∈ CFLSVt for which L = {x | M accepts [x, h(x)]T }. Let M 0 be an npda
  with an output tape computing h. An oracle npda N is also defined as follows.
  On input x, N simulates M 0 on x and nondeterministically produces [x̃, ỹ]T on its
  query tape when M 0 outputs y, where x̃ and ỹ are appropriate \-extensions of x
  and y, respectively. An oracle A receives a \-extension [x̃, ỹ]T and decides whether
  M accepts [x, y]T by removing all \s. Clearly, L belongs to CFLA      m via N . Define
  another npda N1 . On input w = [x̃, ỹ]T , N1 simulates M on [x, z]T by guessing
  z symbol by symbol. At the same time, it writes [ỹ 0 , z̃]T on a query tape and
  accepts w exactly when M enters an accepting state. Let B = {[ỹ 0 , z̃]T | y = z}.
  Note that B is in CFLCFL                           B            CFL
                          m . Hence, A is in CFLm ⊆ CFLm[2] , and thus L is in
  CFLCFL                CFL
       m[3] . Since CFLm[3] = CFLm
                                   CFL(3)
                                          [21], the desired conclusion follows. 2

       The second relativization is Turing relativization. A multi-valued partial func-
  tion f belongs to CFLMVA    T (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 con-
  tent 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.


                                           233
T.Yamakami. Structural complexity of multi-valued partial functions

  Obviously, CFLMVA   T = CFLMV
                                   A
                                 ST holds for any oracle A. Define CFLMVCT (or
                                               A
  CFLMVT (C)) to be the union A∈C CFLMVT for a given language family C.
      Analogously to the well-known NPMV hierarchy, composed of Σkp MV and
    p
  Πk MV for k ∈ N+ [14], we inductively define Σ1CFL MV = CFLMV, ΠkCFL MV =
  co-ΣkCFL MV, and Σk+1CFL
                           MV = CFLMVT (ΠkCFL ) for every index k ≥ 1. In a
  similar fashion, we define ΣkCFL SV using CFLSVA                      A
                                                   T in place of CFLMVT . The
  above CFLMV hierarchy is useful to scaling the computational complexity of
  given functions. For example, the function f (w) = {x ∈ {0, 1}∗ | ∃u, v [w =
  uxxv]} for every w ∈ {0, 1}∗ belongs to Σ2CFL MV. Moreover, it is possible to
  show that CFLMV ∪ co-CFLMV ⊆ CFLMV CFLMV ⊆ Σ4CFL MV.
                                     S
  Proposition 9. Each function in k∈N+ ΣkCFL SVt can be computed by an ap-
  propriate O(n) space-bounded multi-tape deterministic Turing machine.
  Proof Sketch. It is known in [21] that ΣkCFL ⊆ DSPACE(O(n)) for every k ≥ 1.
  It therefore suffices to show that, for any fixed language A ∈ DSPACE(O(n)),
  every function f in CFLSVtA can be computed using O(n) space. This is done
  by a direct simulation of f on a multi-tape Turing machine.              2

     For k ≥ 3, it is possible to give the exact characterization of REG//ΣkCFL SVt .
  This makes a sharp contrast with Proposition 6(3).
  Proposition 10. For every index k ≥ 3, ΣkCFL ∩ ΠkCFL = REG//ΣkCFL SVt .
  Proof Sketch. By extending the proof of Proposition 6(3), it is possible to show
  that ΣkCFL ∩ ΠkCFL ⊆ REG//ΣkCFL SVt . Similarly to Proposition 6(2), it holds
  that REG//ΣkCFL SVt is closed under complement. It thus suffices to show that
  REG//ΣkCFL SVt ⊆ ΣkCFL . This can be done by a direct simulation.             2

  Lemma 11. Let e ≥ 2 and k ≥ 1. ΣkCFL SV = Σk+1
                                             CFL
                                                 SV ⇒ ΣkCFL = Σk+1
                                                               CFL
                                                                   ⇒
   CFL       CFL
  Σk+1 SV = Σk+e SV.
  Proof Sketch. Assuming ΣkCFL SV = Σk+1     CFL
                                                 SV, let us take any language A ∈
  Σk+1 and consider ηA . It is not difficult to show that, for any index d ∈ N+ ,
    CFL

  A ∈ ΣdCFL iff ηA ∈ ΣdCFL SV. Thus, ηA ∈ Σk+1    CFL
                                                      SV = ΣkCFL SV. This implies
              CFL                          CFL       CFL
  that A ∈ Σk . Next, assume that Σk            = Σk+1 . It is proven in [21] that
  ΣkCFL = Σk+1
            CFL
                 iff ΣkCFL = Σk+e
                               CFL
                                   for all e ≥ 1. Hence, for every e ≥ 2, we obtain
  ΣkCFL = Σk+e−1
             CFL
                   , which is equivalent to ΠkCFL = Πk+e−1
                                                         CFL
                                                              . It then follows that
    CFL                    CFL                   CFL       CFL
  Σk+e SV = CFLSVT (Πk+e−1 ) = CFLSVT (Πk ) = Σk+1             SV.                2

     Regarding refinement, from the proof of [8, Theorem 3] follows NFAMV vref
  NFASV. This result leads to NFAMV ◦ CFLSV vref CFLSV in [10]. By a direct
  simulation, nevertheless, it is possible to show that ΣkCFL MV vref Σk+1
                                                                         CFL
                                                                             SV for
  every k ≥ 1. Lemma 11 together with this fact leads to the following consequence.
  Proposition 12. Let k ≥ 2. If ΣkCFL = Σk+1
                                         CFL         CFL
                                             , then Σk+1          CFL
                                                         MV vref Σk+1 SV.
      Recently, it was shown in [22] that CFLMV 6vref CFLSV holds. However, it
  is not known if this can be extended to every level of the CFLMV hierarchy.


                                         234
T.Yamakami. Structural complexity of multi-valued partial functions

  5    Optimization Functions

  An optimization problem is to find an optimal feasible solution that satisfy a given
  condition. Krentel [11] studied the complexity of those optimization problems.
  Analogously to OptP of Krentel, we define OptCFL as a collection of single-
  valued total functions f : Σ ∗ → Γ ∗ such that there exists an npda M and an
  opt ∈ {maximum,minimum} for which, for every string x ∈ Σ ∗ , f (x) denotes the
  opt output string of M on input x along an appropriate accepting computation
  path, assuming that M must have at least one accepting computation path. Here,
  we use the dictionary (or alphabetical) order < over Γ ∗ (e.g., abbe < abc and
  ab < aba) instead of the lexicographic order to compensate the npda’s limited
  ability of comparing two strings from left to right. For example, the function
  f (w) = max{P ALsub (w)} for w ∈ {0, 1}∗ , where P ALsub is defined in Section
  1, is a member of OptCFL. It holds that CFLMVt vref OptCFL.

  Proposition 13. CFLSVt $ OptCFL ⊆ Σ4CFL SVt .

      The first part of Proposition 13 comes from a fact that the function f (w) =
  max{g(w)}, where g(w) = {λ} ∪ {xi yi | 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 ap-
  plying the functional pumping lemma.
      Note that, in the polynomial-time setting, a much sharper upper-bound of
  OptP ⊆ Σ2p 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 Σ2CFL SVt .

  Proposition 14. OptNFAEL ⊆ Σ2CFL SVt .

  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 y R ,
  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
                                                                               x
  paths of M . Let h(x) be max{N1 (x)} for all x’s. It follows that L = {[ h(x)] |
  h(x) 6= Ø}. This proves that L ∈ REG//OptCFL. Next, let L ∈ REG//OptCFL.
  Since OptCFL ⊆ Σ4CFL SVt , we obtain L ∈ REG//Σ4CFL SVt . By Proposition 10,
  this implies that L belongs to Σ4CFL ∩ Π4CFL .                                 2



                                         235
T.Yamakami. Structural complexity of multi-valued partial functions

  References
       1. Aho, A.V., Hopcroft, J.E., Ullman, J.D.: A general theory of translation. Math.
          Systems Theory, 3, 193–221 (1967)
       2. Bar-Hillel, Y., Perles, M., Shamir, E.: On formal properties of simple phrase-
          structure grammars. Z. Phonetik Sprachwiss. Kommunik., 14, 143–172 (1961)
       3. Choffrut, C., Culik, K.: Properties of finite and pushdown transducers. SIAM
          J. Comput., 12, 300–315 (1983)
       4. Evey, R.J.: Application of pushdown-store machines. In: Proc. 1963 Fall Joint
          Computer Conference, AFIPS Press, pp.215–227, 1963
       5. Fenner, S.A., Homer, S., Ogihara, M., Selman, A.L.: Oracles that compute
          values. SIAM J. Comput., 26, 1043–1065 (1997)
       6. Fisher, P.C.: On computability by certain classes of restricted Turing machines.
          In: Proc. 4th Annual IEEE Symp. on Switching Circuit Theory and Logical
          Design (SWCT’63), IEEE Computer Society, pp.23–32, 1963
       7. Holzer, M., Kutrib, M., Malcher, A.: Multi-head finite automata: characteri-
          zations, concepts and open problems. In: Proc. of the Workshop on The Com-
          plexity of Simple Programs, number 1 in EPTCS, pp.93–107, 2008
       8. Kobayashi, K.: Classification of formal langauges by functional binary trans-
          ductions. Inform. Control, 15, 95–109 (1969)
       9. Köbler, J., Thierauf, T.: Complexity-restricted advice functions. SIAM J. Com-
          put., 23, 261–275 (1994)
      10. Konstantinidis, S., Santean, N., Yu, S.: Representation and uniformization of
          algebraic transductions. Acta Inform., 43, 395–417 (2007)
      11. Krentel, M.: The complexity of optimization problems. J. Comput. System
          Sci., 36, 490–509 (1988)
      12. Liu, L.Y., Weiner, P.: An infinite hierarchy of intersections of context-free
          languages. Math. Systems Theory, 7, 185–192 (1973)
      13. Selman, A.L.: A taxonomy of complexity classes of functions. J. Comput. Sys-
          tem Sci., 48, 357–381 (1994)
      14. Selman, A.L.: Much ado about functions. In: Proc. of the 11th Annual IEEE
          Conference on Computational Complexity, pp.198–212, 1996
      15. Tadaki, K., Yamakami, T., Lin, J. C. H.: Theory of one-tape linear-time Turing
          machines. Theor. Comput. Sci., 411, 22–43 (2010)
      16. Wotschke, D.: Nondeterminism and Boolean operations in pda’s. J. Comp.
          System Sci., 16, 456–461 (1978)
      17. Yamakami, T.: Swapping lemmas for regular and context-free languages. Avail-
          able at arXiv:0808.4122 (2008)
      18. Yamakami, T.: The roles of advice to one-tape linear-time Turing machines
          and finite automata. Int. J. Found. Comput. Sci., 21, 941–962 (2010)
      19. Yamakami, T.: Immunity and pseudorandomness of context-free languages.
          Theor. Comput. Sci., 412, 6432–6450 (2011)
      20. Yamakami, T.: Pseudorandom generators against advised context-free lan-
          guages. See arXiv:0902.2774 (2009)
      21. Yamakami, T.: Oracle pushdown automata, nondeterministic reducibilities,
          and the hierarchy over the family of context-free languages. In: Proc. of SOF-
          SEM 2014, V. Geffert et al. (eds.), LNCS, vol. 8327, pp. 514–525 (2014). A
          complete version appears at arXiv:1303.1717.
      22. Yamakami, T.: Not all multi-valued partial CFL functions are refined by single-
          valued functions. In: Proc. of IFIP TCS 2014, J. Diaz et al. (eds), LNCS vol.
          8705, pp. 136–150 (2014)




                                          236

</pre>