DECIDING EMPTINESS FOR STACK AUTOMATA ON INFINITE-TREES

Authors
HAREL D RAZ D
Citation
D. Harel et D. Raz, DECIDING EMPTINESS FOR STACK AUTOMATA ON INFINITE-TREES, Information and computation, 113(2), 1994, pp. 278-299
Citations number
11
Categorie Soggetti
Information Science & Library Science",Mathematics,"Computer Science Information Systems
Journal title
Information and computation → ACNP
ISSN journal
08905401
Volume
113
Issue
2
Year of publication
1994
Pages
278 - 299
Database
ISI
SICI code
0890-5401(1994)113:2<278:DEFSAO>2.0.ZU;2-Q
Abstract
We show that the emptiness problem for Buchi stack automata on infinit e trees is decidable in elementary time. We first establish the decida bility of the emptiness problem for pushdown automata on infinite tree s. This is done using a pumping-like argument applied to computation t rees. We then show how to reduce the emptiness problem for stack autom ata to the emptiness problem for pushdown automata. Elsewhere, we have used the result to establish the decidability of several versions of nonregular dynamic logic. (C) 1994 Academic Press, Inc.