The Recognizability Problem for Tree Automata with Comparisons between Brothers
The Recognizability Problem for Tree Automata with Comparisons between Brothers
复制标题
兄弟比较树自动机的可识别性问题
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
S. Tison
中科院分区：
文献类型：
--
作者：
B. Bogaert;Franck Seynhaeve;S. Tison
树自动机的几个扩展已被定义，以考虑非线性的条款。粗略地说，这些自动机允许子项之间的相等或不等约束。它们已被用于获得决策结果，例如在术语重写中。当我们考虑由这样的自动机识别的语言时，一个自然的问题出现了：这种语言是可识别的吗？也就是说，约束是必要的吗？在这里，我们研究这个问题在类REC#对应的兄弟之间的比较，我们证明了它的可判定性。它给出了例如一个决策过程，用于测试是否由可识别的树语言的准字母同态的图像是可识别的。
Several extensions of tree automata have been defined, in order to take in account non-linearity in terms. Roughly, these automata allow equality or disequality constraints between subterms. They have been used to get decision results, e.g. in term rewriting. One natural question arises when we consider a language recognized by such an automaton: is this language recognizable, i.e. are the constraints necessary? Here we study this problem in the class REC# corresponding to comparisons between brothers and we prove its decidability. It gives e.g. a decision procedure for testing whether the image by a quasi-alphabetic homomorphism of a recognizable tree language is recognizable.