La facilité compte parmi les notions les plus fines de l'indéfini en λ-calcul. Un terme est dit facile s'il peut être identifié à tout autre terme clos arbitraire sans soulever de contradiction. Introduite en 1975 par Jacopini, elle fait depuis l'objet de recherches qui visent à caractériser la forme des termes faciles. Aujourd'hui, de tous les travaux entrepris il se dégage qu'un tel terme doit posséder une périodicité i.e être β-équivalent à un sous-terme propre de l'un de ses réduits. Ici, la périodicité apparaîtra sous les traits de l'auto-similarité. Sont auto-similaires les termes dont l'arbre de Berarducci réapparaît comme sous-arbre propre à lui-même. La facilité de tels termes demeure un mystère et à ce jour, nous n'en connaissons que peu d'exemples. Le terme Yt Ω3 constitue un exemple typique dont la question de la facilité reste ouverte. Dans cette thèse, nous élargirons la connaissance de l'ensemble des termes m identifiables à Yt Ω3. Nous montrerons que dans un cas critique où λβ +{Yt Ω3 = m} |- m = δ3, sous certaines hypothèses, m est lui-même auto-similaire. Ils s'en suit une description possible de toutes les équations dérivées de {Yt Ω3 = m} sous la forme de classes confinantes.
Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00370440 |
Date | 01 July 2005 |
Creators | Bertini, Yves |
Source Sets | CCSD theses-EN-ligne, France |
Language | French |
Detected Language | French |
Type | PhD thesis |
Page generated in 0.0019 seconds