一句话：研究可见下推转换器定义的嵌套词转导能否单遍流式求值，给出 HBM 判定与二次内存充分条件。
本文研究如何以单次从左到右遍历和有限内存来求值嵌套词转导。作者将一类转导称为高度有界内存（HBM）：其求值所需内存仅依赖转导器本身大小和输入词的高度。对于由可见下推转换器（VPT）定义的嵌套词转导，论文证明其是否为 HBM 可在 coNPTime 内判定；当其为 HBM 时，所需内存可能随输入词高度指数增长。文章进一步给出一个可判定的充分条件，保证 VPT 可用随高度二次增长的内存求值。该条件定义的转导类严格包含所有可确定化的 VPT，从而刻画了比确定性 VPT 更广的可流式求值场景。
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.
@article{paperbot805,
title = {Streamability of nested word transductions},
author = {Emmanuel Filiot and Olivier Gauwin and Pierre-Alain Reynier and Frédéric Servais},
journal = {Logical Methods in Computer Science},
volume = {Volume 15, Issue 2},
year = {2019},
doi = {10.23638/lmcs-15(2:1)2019}
}