Logic in Computer Science (LICS 1992)

Paper: Progress measures, immediate determinacy, and a subset construction for tree automata (at LICS 1992)

Authors: Klarlund, N.

Abstract

Using the concept of a progress measure, a simplified proof is given of M.O. Rabin's (1969) fundamental result that the languages defined by tree automata are closed under complementation. To do this, it is shown that for infinite games based on tree automata, the forgetful determinacy property of Y. Gurevich and L. Harrington (1982) can be strengthened to an immediate determinacy property for the player who is trying to win according to a Rabin acceptance condition. Moreover, a graph-theoretic duality theorem for such acceptance conditions is shown. Also presented is a strengthened version of S. Safra's (1988) determinization construction. Together these results and the determinacy of Borel games yield a straightforward method for complementing tree automata

BibTeX

  @InProceedings{Klarlund-Progressmeasuresimm,
    author = 	 {Klarlund, N.},
    title = 	 {Progress measures, immediate determinacy, and a subset construction for tree automata },
    booktitle =  {Proceedings of the Seventh Annual IEEE Symp. on Logic in Computer Science, {LICS} 1992},
    year =	 1992,
    editor =	 {Andre Scedrov},
    month =	 {June}, 
    pages =      {382--393},
    location =   {Santa Cruz, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }