Paper: Coinductive Techniques for Operational Equivalence of Interaction Nets (at LICS 1998)

Authors: Maribel Fernández Ian Mackie

Abstract

In this paper we study a notion of operational equivalence for interaction nets, following the recent success of applying methods based on bisimulation to functional and object oriented programming languages. We set up notions of contextual equivalence and bisimilarity and show that they coincide. A coinduction principle then gives a simple and robust way of showing when two interaction nets are contextually equivalent. We include several examples to demonstrate the usefulness of the approach, in particular for optimizing interaction nets

BibTeX

  @InProceedings{FernndezMackie-CoinductiveTechniqu,
    author = 	 {Maribel Fernández and Ian Mackie},
    title = 	 {Coinductive Techniques for Operational Equivalence of Interaction Nets},
    booktitle =  {Proceedings of the Thirteenth Annual IEEE Symposium on Logic in Computer Science (LICS 1998)},
    year =	 {1998},
    month =	 {June}, 
    pages =      {321--332 },
    location =   {Indianapolis, IN, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }