Abstract : 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.
https://hal.inria.fr/hal-01402038 Contributor : Hal IfipConnect in order to contact the contributor Submitted on : Thursday, November 24, 2016 - 10:49:47 AM Last modification on : Thursday, November 24, 2016 - 11:14:11 AM Long-term archiving on: : Monday, March 20, 2017 - 4:32:26 PM