Paper: Observational equivalence of 3rd-order Idealized Algol is decidable (at LICS 2002)

Authors: C.-H. Luke Ong

Abstract

We prove that observational equivalence of 3rd-order finitary Idealized Algol (IA) is decidable using Game Semantics. By modelling state explicitly in our games, we show that the denotation of a term M of this fragment of IA (built up from finite base types) is a compactly innocent strategy-with-state i.e. the strategy is generated by a finite view function f_M. Given any such f_M, we construct a real-time deterministic pushdown automata (DPDA) that recognizes the complete plays of the knowing-strategy denotation of M. Since such plays characterize observational equivalence, and there is an algorithm for deciding whether any two DPDAs recognize the same language, we obtain a procedure for deciding observational equivalence of 3rd-order finitary IA. This algorithmic representation of program meanings, which is compositional, provides a foundation for model-checking a wide range of behavioural properties of IA and other cognate programming languages. Another result concerns 2nd-order IA with full recursion: we show that observational equivalence for this fragment is undecidable.

BibTeX

  @InProceedings{Ong-Observationalequiva,
    author = 	 {C.-H. Luke Ong},
    title = 	 {Observational equivalence of 3rd-order Idealized Algol is
    decidable},
    booktitle =  {Proceedings of the Seventeenth Annual IEEE Symposium on Logic in Computer Science (LICS 2002)},
    year =	 {2002},
    month =	 {July}, 
    pages =      {245--256},
    location =   {Copenhagen, Denmark}, 
    publisher =	 {IEEE Computer Society Press}
  }