Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/13187

Title: Streamability of Nested Word Transductions
Authors: Servais, Frederic
Filiot, Emmanuel
Gauwin, Olivier
Reynier, Pierre-Alain
Issue Date: 2011
Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Citation: Supratik, Chakraborty; Amit, Kumar (Ed.). IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2011, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik,p. 312-324
Series/Report: LIPICS
Series/Report no.: 13
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.
URI: http://hdl.handle.net/1942/13187
DOI: 10.4230/LIPIcs.FSTTCS.2011.312
ISBN: 978-3-939897-34-7
ISSN: 1868-8969
Category: C1
Type: Proceedings Paper
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
Article590.28 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.