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

**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 Symposium on Logic in Computer Science (LICS 1988)}, year = {1988}, month = {July}, pages = {402--409}, location = {Edinburgh, Scotland, UK}, publisher = {IEEE Computer Society Press} }