The Emptiness and Complementation Problems for Automata on Infinite Trees

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 Rabin's.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1973
Accession Number
AD0756248

Entities

People

  • Charles Weill Rackoff

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Human Systems

DTIC Thesaurus Topics

  • Abstracts
  • Automata
  • Commerce
  • Construction
  • Department Of Defense
  • Electrical Engineering
  • Engineering
  • Machines
  • Massachusetts
  • Mathematics
  • Military Research
  • Notation
  • Numbers
  • Security
  • Sequences
  • Theses
  • Three Dimensional

Fields of Study

  • Mathematics

Readers

  • Forest Ecology
  • Mathematical Modeling and Probability Theory.