Streamability of Nested Word Transductions

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...