Paper: On Program Equivalence in Languages with Ground-Type References (at LICS 2003)

Authors: Andrzej S. Murawski

Abstract

Using game semantics we prove that program equivalence is undecidable in finitary Idealized Algol with active expressions as well as in its call-by-value counterpart. It is also shown that strategies corresponding to Idealized Algol terms of respectively second, third and higher orders define exactly regular, context-free and recursively enumerable languages.

BibTeX

  @InProceedings{Murawski-OnProgramEquivalenc,
    author = 	 {Andrzej S. Murawski},
    title = 	 {On Program Equivalence in Languages with Ground-Type References},
    booktitle =  {Proceedings of the Eighteenth Annual IEEE Symposium on Logic in Computer Science (LICS 2003)},
    year =	 {2003},
    month =	 {June}, 
    pages =      {108--117},
    location =   {Ottawa, Canada}, 
    publisher =	 {IEEE Computer Society Press}
  }