Thursday, November 08, 2007

König's Lemma

How do you show that a simulation preserves non-termination? I think you could probably use coinduction, but I'm not very familiar with coinductive arguments. I just learned about a useful result called König's Lemma, which I think allows you to use a simple induction.

Let's say we have a simulation relation e′ ~ e ("e′ simulates e") and a proof that for any step in a specification semantics:
e1 → e2
we have related terms e1′ ~ e1 and e2′ ~ e2 such that
e1′ →+ e2
It's easy to show by induction that if the specification semantics converges to a value then the implementation semantics converges to a related value. If the specification semantics diverges, i.e. has an infinite reduction sequence, then we'd like to show the implementation diverges too.

König's Lemma states that for any finitely branching tree, if there exists a path of length n from the root for any n, then there exists an infinite path from the root. Consider the tree of possible reduction sequences from a term, where branches indicate points of non-determinism in the semantics. If every point of non-determinism has only a finite number of alternative reductions, then the tree is finitely branching.

So now consider a diverging term e in the specification semantics. For any finite prefix of the infinite reduction sequence, we can easily show by induction that there is a reduction sequence in the implementation semantics of equal or greater length. Since the computation tree of the implementation term is finitely branching, König's Lemma provides an infinite reduction of the implementation.


Anonymous said...

i didn't know how to contact you, so i'm posting a message on your blog-- hope that's ok. i've been wanting to know how to write "timshel" in hebrew, and i was wondering how you found out how to write it. is that the word you have in hebrew in the lefthand corner of your home page?
you can e-mail me at

Arnar Birgisson said...

Hi Dave,

Google reader cunningly recommended your blog to me. It was a bit frightening how spot on it was :o)

Here is a small similar useage of the König's lemma: