Deterministic tree pushdown automata and monadic tree rewriting systems

摘要

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 in op. cit. For right-linear monadic tree rewriting systems the same is true for unions of congruence classes over regular tree languages.