Logic in Computer Science (LICS 2001)

Paper: A Continuum of Theories of Lambda Calculus without Semantics (at LICS 2001)

Authors: Antonino Salibra

Abstract

In this paper we give a topological proof of the following result: There exist 2^{\aleph_0} lambda theories of the untyped lambda calculus without a model in any semantics based on Scott's view of models as partially ordered sets and of functions as monotonic functions. As a consequence of this result, we positively solve the conjecture, stated by Bastonero-Gouy [6, 7] and by Berline [10], that the strongly stable semantics is incomplete.

BibTeX

  @InProceedings{Salibra-AContinuumofTheorie,
    author = 	 {Antonino Salibra},
    title = 	 {A Continuum of Theories of Lambda Calculus without Semantics},
    booktitle =  {Proceedings of the Sixteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2001},
    year =	 2001,
    editor =	 {Joseph Halpern},
    month =	 {June}, 
    pages =      {334--346},
    location =   {Boston, MA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }