DocumentCode
2202339
Title
The emptiness problem for automata on infinite trees
Author
Hossley, R. ; Rackoff, C.
fYear
1972
fDate
25-27 Oct. 1972
Firstpage
121
Lastpage
124
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
Automata; Binary trees; Contracts; US Government; Visualization;
fLanguage
English
Publisher
ieee
Conference_Titel
Switching and Automata Theory, 1972., IEEE Conference Record of 13th Annual Symposium on
Conference_Location
USA
ISSN
0272-4847
Type
conf
DOI
10.1109/SWAT.1972.28
Filename
4569703
Link To Document