DEA 01/02
DEA 13/11/01
Résumé: cours du 13/11/01
cours précédent ........ cours suivant..........tous les cours
Contenu du cours: Sémantique de Böhm.
Termes totalement indéfinis. Omega-règles, Omega-réduction,
approximation directe. La relation "moins défini que".
Arbres de Böhm finis. Idéaux dans l'ensemble des arbres de
Böhm finis. Arbres de Böhm infinis. Sémantique de Böhm.
Si M et N sont beta-interconvertibles, alors BT(M)=BT(N).
Exercices.
Trouver deux termes totalement indéfinis non beta-interconvertibles.
Trouver une infinité de termes totalement indéfinis deux
à deux non beta-interconvertibles.
Montrer que si la taille des réduits $M'$ de $M$ est bornée,
alors BT(M) est fini.
Trouver $M$ qui n'a pas le même arbre de B. que $lam x. M x$. Trouver
deux termes clos eta-interconvertibles dont les arbres de B. diffèrent.
Trouver une infinité de termes deux
à deux eta-interconvertibles, et dont les arbres de B. sont deux à
deux distincts.
Est-ce que, si $r$ est standard et $s/r$ est vide, alors $r/s$ est
standard?
Est-ce que, si $r$ est normale et $s/r$ est vide, alors $r/s$ est
normale?
(*)Est-ce que tout arbre (infini) est de la forme BT(M)?
On pose $S= lam x. f(xx)$, $Y= lam f. S S$ et $Z= Y (lam x y. y (x
y))$. Est-ce que $Y$ et $Z$ sont interconvertibles? Dessiner leurs arbres de B.
cours précédent ........ cours suivant..........tous les cours
Andre.HIRSCHOWITZ
Last modified: Nov 8