  Multi-valued partial CFL functions are functions computed along accepting
computation paths by one-way nondeterministic pushdown automata, equipped with
write-only output tapes, which are allowed to reject an input, in comparison
with single-valued partial CFL functions. We give an answer to a fundamental
question, raised by Konstantinidis, Santean, and Yu [Act. Inform. 43 (2007)
395-417], of whether all such multi-valued partial CFL functions can be refined
by single-valued partial CFL functions. We negatively solve this open question
by presenting a special multi-valued partial CFL function as an example
function and by proving that no refinement of this particular function becomes
a single-valued partial CFL function. This contrasts an early result of
Kobayashi [Inform. Control 15 (1969) 95-109] that multi-valued partial NFA
functions are always refined by single-valued NFA functions, where NFA
functions are computed by one-way nondeterministic finite automata with output
tapes. Our example function turns out to be unambiguously 2-valued, and thus we
obtain a stronger separation result, in which no refinement of unambiguously
2-valued partial CFL functions can be single-valued. For the proof of this
fact, we first introduce a new concept of colored automata having no output
tapes but having "colors," which can simulate pushdown automata equipped with
constant-space output tapes. We then conduct an extensive combinatorial
analysis on the behaviors of transition records of stack contents (called stack
histories) of these colored automata.
