Deciding Emptiness for Stack Automata on Infinite Trees

Résumé du livre

Abstract: "We show that the emptiness problem for stack automata on infinite trees is decidable in elementary time. We first reduce the problem to the emptiness problem for pushdown automata on infinite trees, and then use a pumping-like argument applied to computation trees, to show that this simpler problem is elementarily decidable. Elsewhere, we have used the result to establish the decidability of several versions of nonregular dynamic logic."