Emmanuel Filiot ; Olivier Gauwin ; Pierre-Alain Reynier ; Frédéric Servais - Streamability of nested word transductions

lmcs:3763 - Logical Methods in Computer Science, April 4, 2019, Volume 15, Issue 2 - https://doi.org/10.23638/LMCS-15(2:1)2019
Streamability of nested word transductions

Authors: Emmanuel Filiot ; Olivier Gauwin ; Pierre-Alain Reynier ; Frédéric Servais

    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.


    Volume: Volume 15, Issue 2
    Published on: April 4, 2019
    Accepted on: April 4, 2019
    Submitted on: July 4, 2017
    Keywords: Computer Science - Formal Languages and Automata Theory

    Linked data

    Source : ScholeXplorer IsPartOf DOI 10.4230/lipics.fsttcs.2011
    • 10.4230/lipics.fsttcs.2011
    LIPIcs, Volume 13, FSTTCS'11, Complete Volume
    Chakraborty, Supratik ; Kumar, Amit ;

    Share

    Consultation statistics

    This page has been seen 470 times.
    This article's PDF has been downloaded 213 times.