2026-07-23T19:42:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3352 2024-03-06T10:34:06Z ddc:004 open_access

Streamability of Nested Word Transductions Filiot, Emmanuel Gauwin, Olivier Reynier, Pierre-Alain Servais, Frédéric nested word visibly pushdown transducer streaming XML 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Emmanuel Filiot and Olivier Gauwin and Pierre-Alain Reynier and Frédéric Servais 2011 Is Part Of LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2011.312 urn:nbn:de:0030-drops-33523 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.312 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode