Tree-walking automata do not recognize all regular languages
Tree-walking automata do not recognize all regular languages
复制标题
树行走自动机无法识别所有常规语言
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Thomas Colcombet
中科院分区：
文献类型：
--
作者：
Mikolaj Bojanczyk;Thomas Colcombet
树行走自动机是一种用于识别树型语言的自然顺序模型。每一个树语言识别的树行走自动机是正规的。在本文中，我们提出了一个树语言，这是定期的，但不承认任何（非确定性）树行走自动机。这解决了恩格尔弗里特、胡格布姆和货车贝斯特的一个猜想。此外，分离树语言已经在包含左子、右子和祖先关系的签名上在一阶逻辑中是可定义的。
Tree-walking automata are a natural sequential model for recognizing tree languages. Every tree language recognized by a tree-walking automaton is regular. In this paper, we present a tree language which is regular but not recognized by any (nondeterministic) tree-walking automaton. This settles a conjecture of Engelfriet, Hoogeboom and Van Best. Moreover, the separating tree language is definable already in first-order logic over a signature containing the left-son, right-son and ancestor relations.