The emptiness problem for automata on infinite trees
- 1 October 1972
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02724847,p. 121-124
- https://doi.org/10.1109/swat.1972.28
Abstract
The purpose of this paper is to give an alternative proof to the decidability of the emptiness problem for tree automata, as shown in Rabin4. The proof reduces the emptiness problem for automata on infinite trees to that for automata on finite trees, by showing that any automata definable set of infinite trees must contain a finitely-generable tree.Keywords
This publication has 4 references indexed in Scilit:
- Decidability of Second-Order Theories and Automata on Infinite TreesTransactions of the American Mathematical Society, 1969
- Solving Sequential Conditions by Finite-State StrategiesTransactions of the American Mathematical Society, 1969
- Generalized finite automata theory with an application to a decision problem of second-order logicTheory of Computing Systems, 1968
- Decision problems of finite automata design and related arithmeticsTransactions of the American Mathematical Society, 1961