Computing with Böhm tress

• Autorzy: David, R.
• Języki publikacji: EN

Abstrakty

EN

This paper develops a general technique to analyze the head reduction of a term in a context. This technique is used to give a direct proof of the theorem of Hyland and Wadsworth : two l-terms that have the same Böhm trees, up to (possibly infinite) h-equivalence, are operationally equivalent. It is also used to prove a conjecture of R. Kerth : Every unsolvable l-term has a decoration. This syntactical result is motivated by (and gives the solution to) a semantical problem.

Słowa kluczowe

EN

lambda calculus; Böhm trees; head reduction; operational equivalence; decoration

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2001
• Tom: Vol. 45, nr 1,2
• Strony: 53-77
• Opis fizyczny: bibliogr. 13 poz.

Twórcy

autor

David, R.

• Laboratoire de Maths. Campus Scientifique F-73376 Le Bourget du Lac., France,