Similarity and Bisimilarity for Countable Non-Determinism and Higher-Order Functions (Extended Abstract)

Abstract

This paper investigates operationally-based theories of a simply-typed functional programming language with countable non-determinism. The theories are based upon lower, upper, and convex variants of applicative similarity and bisimilarity, and the main result presented here is that these relations are compatible. The differences between the relations are illustrated by simple examples, and their continuity properties are discussed. It is also shown that, in some cases, the addition of countable non-determinism to a programming language with finite non-determinism alters the theory of the language.