| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
Streamability of Nested Word Transductions
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.
Cited literature [19 references]
https://hal.inria.fr/inria-00566409
Contributor : Olivier Gauwin <>
Submitted on : Wednesday, May 9, 2012 - 3:14:54 PM
Last modification on : Thursday, June 4, 2020 - 10:40:07 AM
Long-term archiving on: : Friday, November 30, 2012 - 11:30:08 AM
Contributor : Olivier Gauwin <>
Submitted on : Wednesday, May 9, 2012 - 3:14:54 PM
Last modification on : Thursday, June 4, 2020 - 10:40:07 AM
Long-term archiving on: : Friday, November 30, 2012 - 11:30:08 AM
File
bounded-memory-vpt.pdf
Files produced by the author(s)