Logic in Computer Science (LICS 1988)

Paper: Fixed points vs. infinite generation (at LICS 1988)

Authors: Damian Niwinski

Abstract

The author characterizes Rabin definability (see M.O. Rabin, 1969) of properties of infinite trees of fixed-point definitions based on the basic operations of a standard powerset algebra of trees and involving the least and greatest fixed-point operators as well as the finite union operator and functional composition. A strict connection is established between a hierarchy resulting from alternating the least and greatest fixed-point operators and the hierarchy induced by Rabin indices of automata. The characterization result is actually proved on a more general level, namely, for arbitrary powerset algebra, where the concept of Rabin automaton is replaced by the more general concept of infinite grammar

BibTeX

  @InProceedings{Niwinski-Fixedpointsvsinfini,
    author = 	 {Damian Niwinski},
    title = 	 {Fixed points vs. infinite generation},
    booktitle =  {Proceedings of the Third Annual IEEE Symp. on Logic in Computer Science, {LICS} 1988},
    year =	 1988,
    editor =	 {Yuri Gurevich},
    month =	 {July}, 
    pages =      {402--409},
    location =   {Edinburgh, Scotland, UK}, 
    publisher =	 {IEEE Computer Society Press}
  }