Streamability of Nested Word Transductions

Emmanuel Filiot 1 Olivier Gauwin 2 Pierre-Alain Reynier 3 Frederic Servais 1
1 ULB - Computer Science Department [Bruxelles]
2 UMons - Université de Mons
3 LIF - Laboratoire d'informatique Fondamentale de Marseille - UMR 6166
Abstract : We consider the problem of evaluating in streaming (i.e. in a single left-to-right pass) a nested word transduction with a limited amount of memory. A transduction T is said to be height bounded memory (HBM) if it can be evaluated with a memory that depends only on the size of T and on the height of the input word. We show that it is decidable in coNPtime for a nested word transduction defined by a visibly pushdown transducer (VPT), if it is HBM. In this case, the required amount of memory may depend exponentially on the height of the word. We exhibit a sufficient, decidable condition for a VPT to be evaluated with a memory that depends quadratically on the height of the word. This condition defines a class of transductions that strictly contains all determinizable VPTs.
Type de document :
Communication dans un congrès
Supratik Chakraborty and Amit Kumar. FSTTCS - 31st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science - 2011, Dec 2011, Mumbai, India. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 13, pp.312-324, 2011, Leibniz International Proceedings in Informatics (LIPIcs). 〈10.4230/LIPIcs.FSTTCS.2011.312〉
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00566409
Contributeur : Olivier Gauwin <>
Soumis le : mercredi 9 mai 2012 - 15:14:54
Dernière modification le : vendredi 9 mars 2018 - 11:26:03
Document(s) archivé(s) le : vendredi 30 novembre 2012 - 11:30:08

Fichier

bounded-memory-vpt.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

UNIV-AMU | LIF | LIS-LAB

Citation

Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier, Frederic Servais. Streamability of Nested Word Transductions. Supratik Chakraborty and Amit Kumar. FSTTCS - 31st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science - 2011, Dec 2011, Mumbai, India. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 13, pp.312-324, 2011, Leibniz International Proceedings in Informatics (LIPIcs). 〈10.4230/LIPIcs.FSTTCS.2011.312〉. 〈inria-00566409v2〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

170

Téléchargements de fichiers

164

Contact


archive-ouverte@inria.fr