Not All Multi-Valued Partial CFL Functions Are Refined by Single-Valued Functions (Extended Abstract)

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.
Type de document :
Communication dans un congrès
Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.136-150, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_12〉
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01402038
Contributeur : Hal Ifip <>
Soumis le : jeudi 24 novembre 2016 - 10:49:47
Dernière modification le : jeudi 24 novembre 2016 - 11:14:11
Document(s) archivé(s) le : lundi 20 mars 2017 - 16:32:26

Fichier

978-3-662-44602-7_12_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Tomoyuki Yamakami. Not All Multi-Valued Partial CFL Functions Are Refined by Single-Valued Functions (Extended Abstract). Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.136-150, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_12〉. 〈hal-01402038〉

Partager

Métriques

Consultations de la notice

16

Téléchargements de fichiers

5