首页    期刊浏览 2024年11月07日 星期四
登录注册

文章基本信息

  • 标题:Streamability of Nested Word Transductions
  • 本地全文:下载
  • 作者:Emmanuel Filiot ; Olivier Gauwin ; Pierre-Alain Reynier
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2011
  • 卷号:13
  • 页码:312-324
  • DOI:10.4230/LIPIcs.FSTTCS.2011.312
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要: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.
  • 关键词:nested word; visibly pushdown transducer; streaming; XML
国家哲学社会科学文献中心版权所有