Logic in Computer Science (LICS 1989)

Paper: On substitutional recursion over non-well-founded sets (at LICS 1989)

Authors: Fernando, R.T.P.

Abstract

A class of recursive definitions is isolated, which encompasses all applications of nonwellfounded sets known to the author. These definitions are based on a result referred to in the literature as the substitution lemma, and accordingly are called substitutional recursive definitions (SRDs). A theory of fixed points of SRDs is developed in a number of directions, leading to a consideration of effective aspects of nonwellfounded sets. The novelty of the author's approach is that he gets at these fixed points without explicitly referring to the operators. Instead, he constructs systems of equations from the specification, replacing the variables by indeterminates for which he then solves. Over nonwellfounded sets, this approach to fixed points, which can be seen as a refinement of the usual iterative methods for inductive (and coinductive) definitions, is quite fruitful, yielding detailed information about fixed points

BibTeX

  @InProceedings{Fernando-Onsubstitutionalrec,
    author = 	 {Fernando, R.T.P.},
    title = 	 {On substitutional recursion over non-well-founded sets},
    booktitle =  {Proceedings of the Fourth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1989},
    year =	 1989,
    editor =	 {Rohit Parikh},
    month =	 {June}, 
    pages =      {273--282},
    location =   {Pacific Grove, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }