The Emptiness Problem for Automata on Infinite Trees

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1972
Accession Number
AD0747250

Entities

People

  • Charles Rackoff
  • Robert Hossley

Organizations

  • Massachusetts Institute of Technology

Tags

DTIC Thesaurus Topics

  • Alphabets
  • Automata
  • Classification
  • Construction
  • Contracts
  • Department Of Defense
  • Machines
  • Massachusetts
  • Military Research
  • Notation
  • Security
  • Sequences
  • Trees (Data Structures)

Fields of Study

  • Mathematics

Readers

  • Mathematical Modeling and Probability Theory.