Not all multi-valued partial CFL functions are refined by single-valued functions (extended abstract)
Not all multi-valued partial CFL functions are refined by single-valued functions (extended abstract)
复制标题
并非所有多值部分 CFL 函数都由单值函数细化（扩展摘要）
DOI：
10.1007/978-3-662-44602-7_12
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
T. Yamakami
中科院分区：
文献类型：
--
作者：
1.Jesmin S;Mamun AA;Rahman A;Akter S;Iwashima Y;Shimojo N;Yamaguchi N;Hiroe M;Mizutani T;Moroi M（分担）;T. Yamakami
我们给一个基本问题的答案，提出了康斯坦丁，Santean，和余[学报通知。43（2007）395-417]，关于是否所有多值部分CFL函数都可以通过单值部分CFL函数来细化。我们消极地解决这个问题，提出了一个特殊的多值部分CFL函数作为一个例子的功能，并通过证明，没有细化这个特定的功能成为一个单值部分CFL功能。这与小林[Inform. Control 15（1969）95-109]，多值部分NFA函数总是由单值NFA函数精化。我们的例子函数原来是明确的2-值，因此我们得到了更强的分离结果，其中没有明确的2-值部分CFL函数的细化可以是单值的。我们的证明包括操纵和密切的分析基本的单向单头不确定性下推自动机配备只写输出磁带。
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.