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 | Source: | 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. | Keywords: | formal language; XML; automata | Document URI: | http://hdl.handle.net/1942/13187 | ISBN: | 978-3-939897-34-7 | DOI: | 10.4230/LIPIcs.FSTTCS.2011.312 | Rights: | Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier, and Frédéric Servais; licensed under Creative Commons License NC-ND | Category: | C1 | Type: | Proceedings Paper |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
streamability of nested word transductions.pdf | Published version | 590.28 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
12
checked on Sep 3, 2020
WEB OF SCIENCETM
Citations
11
checked on Sep 29, 2024
Page view(s)
20
checked on Sep 7, 2022
Download(s)
4
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.