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

Authors:**C.-H. L. 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. L. Ong}, title = {Observational equivalence of 3rd-order Idealized Algol is decidable}, booktitle = {Proceedings of the Seventeenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2002}, year = 2002, editor = {Gordon Plotkin}, month = {July}, location = {Copenhagen, Denmark}, publisher = {IEEE Computer Society Press} }