Accession Number:

AD0747250

Title:

The Emptiness Problem for Automata on Infinite Trees

Descriptive Note:

Technical memo

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE PROJECT MAC

Personal Author(s):

Report Date:

1972-01-01

Pagination or Media Count:

19.0

Abstract:

The purpose of the paper is to give an alternative proof to the decidability of the emptiness problem for tree automata, as shown in another paper. 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.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE