Deterministic Tree Pushdown Automata and Monadic Tree Rewriting Systems
Deterministic Tree Pushdown Automata and Monadic Tree Rewriting Systems
复制标题
确定性树下推自动机和一元树重写系统
DOI：
10.1016/0022-0000(88)90014-1
复制
发表时间：
1988
期刊：
影响因子：
--
通讯作者：
K. Salomaa
中科院分区：
文献类型：
--
作者：
K. Salomaa
我们证明，J. H. Gallier 和 R. V. Book (Theoret. Comput. Sci.37(1985), 123–150) 的确定性树下推自动机比 K. M. Schimpf 的相应自动机（宾夕法尼亚大学博士论文，1982）更强大。事实上，即使是以前的自动机的附加功能之一，删除或复制树堆栈的子树的能力也提高了识别能力。我们还表明，规范一元树重写系统的同余类的有限并可以通过确定性树下推自动机来识别，而无需使用 inop 的额外接受条件。引用。对于右线性一元树重写系统，对于常规树语言上的同余类的并集也是如此。
We show that the deterministic tree pushdown automata of J. H. Gallier and R. V. Book (Theoret. Comput. Sci.37(1985), 123–150) are strictly more powerful than the corresponding automata of K. M. Schimpf (Ph. D. dissertation, University of Pennsylvania, 1982). In fact, even one of the additional features of the former automata, the capability to delete or to duplicate subtrees of the tree stack increases the recognition power. Also we show that finite unions of congruence classes of canonical monadic tree rewriting systems can be recognized by deterministic tree pushdown automata without the additional acceptance conditions used inop. cit. For right-linear monadic tree rewriting systems the same is true for unions of congruence classes over regular tree languages.