Logic in Computer Science (LICS 1997)

Paper: Discrimination by Parallel Observers (at LICS 1997)

Authors: Mariangiola Dezani-Ciancaglini Jerzy Tiuryn Pawel Urzyczyn

Abstract

The main result of the paper is a proof of the following equivalence: two pure lambda terms are observationally equivalent in the lazy concurrent lambda calculus iff they have the same Levy-Longo trees. It follows that contextual equivalence coincides with behavioural equivalence (bisimulation) as considered by Sangiorgi. Another consequence is that the discriminating power of concurrent lambda contexts is the same as that of Boudol-Laneve's contexts with multiplicities.

BibTeX

  @InProceedings{DezaniCiancagliniTi-DiscriminationbyPar,
    author = 	 {Mariangiola Dezani-Ciancaglini and Jerzy Tiuryn and Pawel Urzyczyn},
    title = 	 {Discrimination by Parallel Observers},
    booktitle =  {Proceedings of the Twelfth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1997},
    year =	 1997,
    editor =	 {Glynn Winskel},
    month =	 {June}, 
    pages =      {396--407},
    location =   {Warsaw, Poland}, 
    publisher =	 {IEEE Computer Society Press}
  }