Isomorphism of regular trees and words
Isomorphism of regular trees and words
复制标题
正则树与词的同构
DOI：
10.1016/j.ic.2013.01.002
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Christian Mathissen
中科院分区：
文献类型：
--
作者：
Markus Lohrey;Christian Mathissen
分析了正则树、正则线性序和正则词同构问题的计算复杂度。如果树与正则语言上的前缀顺序同构，则树是正则树。如果正则语言由nfa （dfa）表示，那么正则树的同构问题就变成了EXPTIME-complete（见图2）。穷)。当输入自动机为无环nfa（无环dfa）时，相应的树是有限树（简洁地表示），同构问题证明是pspace完全的（见图2）。穷)。如果线性顺序与正则语言的字典顺序同构，则线性顺序是正则的。给出了一种多项式时间算法，用于求解由dfa给出的正则线性阶（甚至正则字）的同构问题。这解决了Ésik和Bloom提出的一个开放性问题。类似的技术可以用来证明一个人可以在多项式时间内检验一个给定的正则线性序列是否具有非平凡自同构。这改进了最近Kuske的可决性结果。
The computational complexity of the isomorphism problem for regular trees, regular linear orders, and regular words is analyzed. A tree is regular if it is isomorphic to the prefix order on a regular language. In case regular languages are represented by NFAs (DFAs), the isomorphism problem for regular trees turns out to be EXPTIME-complete (resp. P-complete). In case the input automata are acyclic NFAs (acyclic DFAs), the corresponding trees are (succinctly represented) finite trees, and the isomorphism problem turns out to be PSPACE-complete (resp. P-complete). A linear order is regular if it is isomorphic to the lexicographic order on a regular language. A polynomial time algorithm for the isomorphism problem for regular linear orders (and even regular words, which generalize the latter) given by DFAs is presented. This solves an open problem by Ésik and Bloom. Similar techniques can be used to show that one can check in polynomial time whether a given regular linear order has a non-trivial automorphism. This improves a recent decidability result of Kuske.