MIT Libraries logoDSpace@MIT

MIT
View Item 
  • DSpace@MIT Home
  • Computer Science and Artificial Intelligence Lab (CSAIL)
  • LCS Publications
  • LCS Technical Reports (1974 - 2003)
  • View Item
  • DSpace@MIT Home
  • Computer Science and Artificial Intelligence Lab (CSAIL)
  • LCS Publications
  • LCS Technical Reports (1974 - 2003)
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

The Emptiness and Complementation Problems for Automata on Infinite Trees

Author(s)
Rackoff, Charles Weill
Thumbnail
DownloadMIT-LCS-TR-106.pdf (1.400Mb)
Advisor
Rogers, Hartley
Metadata
Show full item record
Abstract
In [6] Rabin defines Automata on Infinite Trees, and the body of that paper is concerned with proving two theorems about these automata. The result we consider in the first chapter says that there exists an effective procedure to determine, given an automaton on infinite trees, whether or not it accepts anything at all. We present a new decision procedure which is much simpler than Rabin's since we do not use an induction argument as he does.
Date issued
1973-01
URI
https://hdl.handle.net/1721.1/149416
Series/Report no.
MIT-LCS-TR-106MAC-TR-106

Collections
  • LCS Technical Reports (1974 - 2003)
  • MAC Technical Reports (1963 - 1974)

Browse

All of DSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

My Account

Login

Statistics

OA StatisticsStatistics by CountryStatistics by Department
MIT Libraries
PrivacyPermissionsAccessibilityContact us
MIT
Content created by the MIT Libraries, CC BY-NC unless otherwise noted. Notify us about copyright concerns.