%0 Conference Proceedings
%T Not All Multi-Valued Partial CFL Functions Are Refined by Single-Valued Functions (Extended Abstract)
%+ University of Fukui [Bunkyo]
%A Yamakami, Tomoyuki
%Z Part 1: Track A: Algorithms, Complexity and Models of Computation
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 8th IFIP International Conference on Theoretical Computer Science (TCS)
%C Rome, Italy
%Y Josep Diaz
%Y Ivan Lanese
%Y Davide Sangiorgi
%I Springer
%3 Theoretical Computer Science
%V LNCS-8705
%P 136-150
%8 2014-09-01
%D 2014
%R 10.1007/978-3-662-44602-7_12
%K multi-valued partial function
%K CFL function
%K NFA function
%K refinement
%K pushdown automaton
%K context-free language
%K stack history
%Z Computer Science [cs]Conference papers
%X We give an answer to a fundamental question, raised by Konstantinidis, Santean, and Yu [Acta Inform. 43 (2007) 395–417], of whether all multi-valued partial CFL functions can be refined by single-valued partial CFL functions. We negatively solve this 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. 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. Our proof consists of manipulations and close analyses of underlying one-way one-head nondeterministic pushdown automata equipped with write-only output tapes.
%G English
%Z TC 1
%Z TC 2
%Z WG 2.2
%2 https://inria.hal.science/hal-01402038/document
%2 https://inria.hal.science/hal-01402038/file/978-3-662-44602-7_12_Chapter.pdf
%L hal-01402038
%U https://inria.hal.science/hal-01402038
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC2
%~ IFIP-LNCS-8705
%~ IFIP-TCS
%~ IFIP-WG2-2