Streamability of Nested Word Transductions - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2011

Streamability of Nested Word Transductions

Résumé

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.
Fichier principal
Vignette du fichier
bounded-memory-vpt.pdf (435.73 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00566409 , version 1 (16-02-2011)
inria-00566409 , version 2 (09-05-2012)

Identifiants

Citer

Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier, Frederic Servais. Streamability of Nested Word Transductions. FSTTCS - 31st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science - 2011, Dec 2011, Mumbai, India. pp.312-324, ⟨10.4230/LIPIcs.FSTTCS.2011.312⟩. ⟨inria-00566409v2⟩
198 Consultations
134 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More