Logic in Computer Science (LICS 2003)

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 Symp. on Logic in Computer Science, {LICS} 2003},
    year =	 2003,
    editor =	 {Phokion G. Kolaitis},
    month =	 {June}, 
    pages =      {108--},
    location =   {Ottawa, Canada}, 
    publisher =	 {IEEE Computer Society Press}
  }