• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Annual ACM/IEEE Symposium on Logic in Computer Science >Two-Way Visibly Pushdown Automata and Transducers*
【24h】

Two-Way Visibly Pushdown Automata and Transducers*

机译：双向可视下推自动机和换能器 *

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Automata-logic connections are pillars of the theory of regular languages. Such connections are harder to obtain for transducers, but important results have been obtained recently for word-to-word transformations, showing that the three following models are equivalent: deterministic two-way transducers, monadic second-order (MSO) transducers, and deterministic one-way automata equipped with a finite number of registers. Nested words are words with a nesting structure, allowing to model unranked trees as their depth-first-search linearisations. In this paper, we consider transformations from nested words to words, allowing in particular to produce unranked trees if output words have a nesting structure. The model of visibly pushdown transducers allows to describe such transformations, and we propose a simple deterministic extension of this model with two-way moves that has the following properties: i) it is a simple computational model, that naturally has a good evaluation complexity; ii) it is expressive: it subsumes nested word-to-word MSO transducers, and the exact expressiveness of MSO transducers is recovered using a simple syntactic restriction; iii) it has good algorithmic/closure properties: the model is closed under composition with a unambiguous one-way letter-to-letter transducer which gives closure under regular look-around, and has a decidable equivalence problem.
机译：自动逻辑连接是常规语言理论的基础。对于换能器来说，很难获得这样的连接，但是对于词到词的转换，最近已经获得了重要的结果，表明以下三个模型是等效的：确定性双向换能器，二阶二阶（MSO）换能器和确定性装有有限数量寄存器的单向自动机。嵌套词是具有嵌套结构的词，可以将未排序的树建模为深度优先搜索线性化。在本文中，我们考虑了从嵌套单词到单词的转换，如果输出单词具有嵌套结构，则特别允许生成未排序的树。可见下推传感器模型允许描述这种转换，我们提出了该模型的双向移动的简单确定性扩展，该扩展具有以下特性：i）它是一个简单的计算模型，自然地具有良好的评估复杂性; ii）具有表达力：它包含嵌套的词对词MSO转换器，并且使用简单的语法限制即可恢复MSO转换器的确切表达; iii）它具有良好的算法/闭合特性：使用明确的单向字母至字母换能器在组成下闭合该模型，该传感器在常规环视条件下给出闭合，并且存在可判定的等效性问题。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号