Accession Number:

AD0756248

Title:

The Emptiness and Complementation Problems for Automata on Infinite Trees

Descriptive Note:

Master's thesis

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE PROJECT MAC

Personal Author(s):

Report Date:

1973-01-01

Pagination or Media Count:

47.0

Abstract:

In a previous paper Rabin defined Automata on Infinite Trees, and the body of that paper is concerned with proving two theorems about these automata. The result the author considers in the report states that there exists an effective procedure to determine, given an automaton on infinite trees, whether or not it accepts anything at all. An alternative proof is presented which reduces the emptiness problem for automata on infinite trees to that for automata on finite trees. This proof is much simpler than Rabins.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE