Algorithms for Guided Tree Automata
Algorithms for Guided Tree Automata
复制标题
引导树自动机的算法
DOI：
10.1007/3-540-63174-7_2
复制
发表时间：
1996
期刊：
影响因子：
10.8
通讯作者：
Theis Rauhe
中科院分区：
文献类型：
--
作者：
M. Biehl;Nils Klarlund;Theis Rauhe
当读取输入树时，自下而上的树自动机不知道它相对于根的位置。这个问题对于有限树上一元二阶逻辑(M2L)决策过程的有效实现具有重要意义。在[KS97]中，证明了指数状态空间爆破在一般情况下是如何发生的。对问题的分析引出了用于对抗此类爆炸的有导树自动机的概念。导引自动机配备了独立的状态空间，这些状态空间由自上而下的自动机分配，称为向导。
When reading an input tree, a bottom-up tree automaton is] “unaware” of where it is relative to the root. This problem is important to the efficient implementation of decision procedures for the Monadic Second-order Logic (M2L) on finite trees. In [KS97], it is shown how exponential state space blow-ups may occur in common situations. The analysis of the problem leads to the notion of guided tree automaton for combatting such explosions. The guided automaton is equipped with separate state spaces that are assigned by a top-down automaton, called the guide.