1596:
does not have a normal form, normalization may "grow" some subtrees infinitely, or it may get "stuck in a loop" attempting to produce a result for part of the tree, which produce infinitary trees and meaningless terms respectively. Since the Böhm tree may be infinite the procedure should be
1400:
1813:
1514:
47:
A simple way to read the meaning of a computation is to consider it as a mechanical procedure consisting of a finite number of steps that, when completed, yields a result. In particular, considering the lambda calculus as a
2294:
2110:
1934:
1263:
1066:
403:
970:
886:
471:
308:
1206:
The Böhm-like "tree" for a term may then be obtained as the normal form of the term in this system, possibly in an infinitary "in the limit" sense if the term expands infinitely.
657:
1713:
1203:. The λ⊥-terms are then considered as a rewriting system with these two rules; thanks to the definition of meaningless terms this rewriting system is confluent and normalizing.
613:
1945:
The
Berarducci trees are obtained by considering the λ⊥-terms where the set of meaningless terms consists of the root-active terms. More explicitly, the Berarducci tree BerT(
346:
575:
2205:
2035:
1865:
1175:
934:
The set of root-active terms, i.e. the terms without top normal form or root normal form. Since root-activeness is assumed, this is the smallest set of meaningless terms.
1201:
1561:. Barendregt introduced a notion of an "effective" Böhm tree that is computable, with the only difference being that terms with no head normal form are not marked with
546:
1149:
912:
847:
818:
792:
526:
497:
432:
1979:
1643:
1579:
1252:
1086:
686:
2156:
2176:
2133:
2006:
1836:
1670:
1420:
1106:
990:
766:
746:
726:
706:
269:
249:
225:
1718:
1425:
2835:
2756:
2662:
2531:
2210:
60:
suggestion, say the meaning of a term is its normal form, and that terms without a normal form are meaningless. For example the meanings of
39:
are (potentially infinite) tree-like mathematical objects that capture the "meaning" of a term up to some set of "meaningless" terms.
2040:
2793:
2612:
2379:
1870:
1395:{\displaystyle \mathrm {BT} (M)=\lambda x_{1}.\lambda x_{2}.\ldots \lambda x_{n}.y\mathrm {BT} (M_{1})\ldots \mathrm {BT} (M_{m})}
53:
1003:
2476:
2444:
1605:
The Lévy-Longo trees are obtained by considering the λ⊥-terms where the set of meaningless terms consists of those without
351:
2719:
1214:
The Böhm trees are obtained by considering the λ⊥-terms where the set of meaningless terms consists of those without
52:
system, each beta reduction step is a rewrite step, and once there are no further beta reductions the term is in
147:, hence has a meaning. We thus see that not all non-normalizing terms are equivalent. We would like to say that
2862:
947:
852:
437:
274:
1597:
understood as being applied co-recursively or as taking the limit of an infinite series of approximations.
2688:
2640:
2509:
20:
2429:
618:
2362:
Levy, Jean-Jacques (1975). "An algebraic interpretation of the λβK-calculus and a labelled λ-calculus".
1675:
1606:
929:
83:
2812:
583:
2504:
Kennaway, Richard; van
Oostrom, Vincent; de Vries, Fer-Jan (1996). "Meaningless terms in rewriting".
918:
There are infinitely many sets of meaningless terms, but the ones most common in the literature are:
2645:
313:
2693:
2514:
1558:
551:
1592:
has a normal form, the Böhm tree is finite and has a simple correspondence to the normal form. If
2799:
2706:
2181:
2011:
1841:
1154:
1180:
2831:
2789:
2752:
2728:
2658:
2608:
2527:
2472:
2440:
2375:
1088:. Beta-reduction on this set is defined in the standard way. Given a set of meaningless terms
89:
This naive assignment of meaning is however inadequate for the full lambda calculus. The term
531:
2823:
2779:
2771:
2698:
2650:
2519:
2408:
2367:
1215:
1111:
923:
891:
826:
797:
771:
505:
476:
411:
1964:
1628:
1564:
1237:
1071:
124:
24:
2770:. Studies in Logic and the Foundations of Mathematics. Vol. 90. pp. 1091–1132.
2721:
The Lazy Lambda
Calculus: An Investigation into the Foundations of Functional Programming
2322:
1000:
The set of λ-terms with ⊥ (abbreviated λ⊥-terms) is defined coinductively by the grammar
665:
2138:
2161:
2118:
1991:
1821:
1655:
1405:
1091:
975:
751:
731:
711:
691:
254:
234:
210:
2775:
2856:
2413:
2396:
57:
2803:
2710:
1808:{\displaystyle \mathrm {LLT} (M)=y\mathrm {LLT} (M_{1})\ldots \mathrm {LLT} (M_{m})}
1068:. This corresponds to the standard infinitary lambda calculus plus terms containing
2629:
1509:{\displaystyle \lambda x_{1}.\lambda x_{2}.\ldots \lambda x_{n}.yM_{1}\ldots M_{m}}
82:. This works for any strongly normalizing subset of the lambda calculus, such as a
2827:
2673:
2813:"Decomposing the Lattice of Meaningless Sets in the Infinitary Lambda Calculus"
2702:
2523:
2732:
49:
2397:"Set-theoretical models of λ-calculus: theories, expansions, isomorphisms"
1584:
Note that computing the Böhm tree is similar to finding a normal form for
2822:. Lecture Notes in Computer Science. Vol. 6642. pp. 210–227.
2654:
2508:. Lecture Notes in Computer Science. Vol. 1139. pp. 254–268.
2371:
2289:{\displaystyle \mathrm {BerT} (M)=\mathrm {BerT} (N)\mathrm {BerT} (P)}
2784:
2366:. Lecture Notes in Computer Science. Vol. 37. pp. 147–165.
199:. Hence there are also issues with confluence of normalization.
2105:{\displaystyle \mathrm {BerT} (M)=\lambda x.\mathrm {BerT} (N)}
2586:
2584:
2582:
2766:
Barendregt, Henk P. (1977). "The Type Free Lambda
Calculus".
2545:
2543:
1929:{\displaystyle \mathrm {LLT} (M)=\lambda x.\mathrm {LLT} (N)}
1422:
reduces in a finite number of steps to the head normal form
1557:
Determining whether a term has a head normal form is an
1061:{\displaystyle M=\bot \mid x\mid (\lambda x.M)\mid (MM)}
2213:
2184:
2164:
2141:
2121:
2043:
2014:
1994:
1967:
1873:
1844:
1824:
1721:
1678:
1658:
1631:
1567:
1428:
1408:
1266:
1240:
1183:
1157:
1114:
1094:
1074:
1006:
978:
950:
894:
855:
829:
800:
774:
754:
734:
714:
694:
668:
621:
586:
554:
534:
508:
479:
440:
414:
354:
316:
277:
257:
237:
213:
2747:
Sangiorgi, Davide; Walker, David (16 October 2003).
2639:. LNCS. Vol. 1281. Springer. pp. 604–610.
914:. Some definitions leave this out, but it is useful.
728:
by replacing a set of pairwise disjoint subterms in
398:{\displaystyle N{\stackrel {*}{\to }}(\lambda x.P)Q}
96:
does not have a normal form, and similarly the term
2605:
The Lambda
Calculus : Its Syntax and Semantics
130:, reduces only to itself, whereas the application
2607:. London: College Publications. pp. 219–221.
2288:
2199:
2170:
2150:
2127:
2104:
2029:
2000:
1973:
1928:
1859:
1830:
1807:
1707:
1664:
1637:
1573:
1508:
1414:
1394:
1246:
1195:
1169:
1143:
1100:
1080:
1060:
984:
964:
906:
880:
841:
812:
786:
760:
740:
720:
700:
680:
651:
607:
569:
540:
520:
491:
465:
426:
397:
340:
302:
263:
243:
219:
103:does not have a normal form. But the application
2630:"Finite-state Transducers as Regular Böhm Trees"
2338:
2314:
2590:
2573:
2561:
2549:
2491:
231:Root-activeness: Every root-active term is in
2749:The Pi-Calculus: A Theory of Mobile Processes
2439:. New York: Marcel Dekker. pp. 339–377.
2430:"Infinite λ-calculus and non-sensible models"
8:
2820:Logic, Language, Information and Computation
170:In the infinitary lambda calculus, the term
161:to a term can produce a result but applying
1609:. More explicitly, the Lévy-Longo tree LLT(
1108:, we also define a reduction to bottom: if
16:Mathematical object for the lambda calculus
2471:. Princeton University Press. p. 15.
2318:
2811:Severi, Paula; de Vries, Fer-Jan (2011).
2783:
2692:
2644:
2513:
2412:
2263:
2240:
2214:
2212:
2183:
2163:
2140:
2120:
2079:
2044:
2042:
2013:
1993:
1966:
1906:
1874:
1872:
1843:
1823:
1796:
1778:
1766:
1748:
1722:
1720:
1699:
1686:
1677:
1657:
1630:
1566:
1500:
1487:
1471:
1452:
1436:
1427:
1407:
1383:
1368:
1356:
1341:
1329:
1310:
1294:
1267:
1265:
1239:
1182:
1156:
1127:
1113:
1093:
1073:
1005:
977:
951:
949:
893:
867:
862:
860:
859:
854:
828:
799:
773:
753:
733:
713:
693:
667:
620:
585:
553:
533:
507:
478:
452:
447:
445:
444:
439:
413:
366:
361:
359:
358:
353:
315:
289:
284:
282:
281:
276:
256:
236:
212:
2637:Theoretical Aspects of Computer Software
2354:
2306:
965:{\displaystyle \mathbf {\Omega } \in U}
881:{\displaystyle M{\stackrel {*}{\to }}N}
466:{\displaystyle M{\stackrel {*}{\to }}N}
303:{\displaystyle M{\stackrel {*}{\to }}N}
141:reduces with normal order reduction to
2364:λ-Calculus and Computer Science Theory
1838:reduces to the weak head normal form
1672:reduces to the weak head normal form
7:
1218:. More explicitly, the Böhm tree BT(
502:Closure under substitution: For all
2628:Huet, Gérard; Laulhère, H. (1997).
2334:
2178:does not reduce to any abstraction
972:for every set of meaningless terms
823:Closure under β-expansion. For all
652:{\displaystyle (\lambda x.M)N\in U}
408:Closure under β-reduction: For all
56:. We could thus, naively following
2273:
2270:
2267:
2264:
2250:
2247:
2244:
2241:
2224:
2221:
2218:
2215:
2089:
2086:
2083:
2080:
2054:
2051:
2048:
2045:
1968:
1913:
1910:
1907:
1881:
1878:
1875:
1785:
1782:
1779:
1755:
1752:
1749:
1729:
1726:
1723:
1708:{\displaystyle yM_{1}\ldots M_{m}}
1632:
1568:
1372:
1369:
1345:
1342:
1271:
1268:
1241:
1190:
1164:
1121:
1075:
1013:
14:
227:of meaningless terms as follows:
2635:. In Abadi, M.; Ito, T. (eds.).
2469:The calculi of lambda-conversion
2401:Annals of Pure and Applied Logic
1128:
952:
608:{\displaystyle \lambda x.M\in U}
2718:Ong, C.-H. Luke (31 May 1988).
2506:Algebraic and Logic Programming
2428:Berarducci, Alessandro (1996).
2395:Longo, Giuseppe (August 1983).
2768:Handbook of Mathematical Logic
2751:. Cambridge University Press.
2681:Math. Struct. In Comp. Science
2317:, p. 493), introduced in
2283:
2277:
2260:
2254:
2234:
2228:
2099:
2093:
2064:
2058:
1923:
1917:
1891:
1885:
1802:
1789:
1772:
1759:
1739:
1733:
1389:
1376:
1362:
1349:
1281:
1275:
1187:
1132:
1124:
1118:
1055:
1046:
1040:
1025:
863:
637:
622:
448:
389:
374:
362:
341:{\displaystyle (\lambda x.P)Q}
332:
317:
285:
1:
2776:10.1016/S0049-237X(08)71129-7
2727:(PhD). University of London.
2321:and named after a theorem of
1649:has no weak head normal form.
944:is root-active and therefore
570:{\displaystyle M\sigma \in U}
2828:10.1007/978-3-642-20920-8_22
2603:Barendregt, Henk P. (2012).
2414:10.1016/0168-0072(83)90030-1
2339:Sangiorgi & Walker (2003
2315:Sangiorgi & Walker (2003
1953:can be computed as follows:
1617:can be computed as follows:
1226:can be computed as follows:
2200:{\displaystyle \lambda x.Q}
2030:{\displaystyle \lambda x.N}
1860:{\displaystyle \lambda x.N}
1170:{\displaystyle M\neq \bot }
2879:
2591:Severi & de Vries 2011
2574:Severi & de Vries 2011
2562:Severi & de Vries 2011
2550:Severi & de Vries 2011
2492:Severi & de Vries 2011
1196:{\displaystyle M\to \bot }
662:Indiscernibility: For all
271:is root-active if for all
2703:10.1017/S0960129598002643
928:The set of terms without
922:The set of terms without
203:Sets of meaningless terms
2524:10.1007/3-540-61735-3_17
153:is less meaningful than
2467:Church, Alonzo (1941).
1258:has no head normal form
541:{\displaystyle \sigma }
2290:
2201:
2172:
2152:
2129:
2106:
2031:
2002:
1975:
1930:
1861:
1832:
1809:
1709:
1666:
1639:
1575:
1510:
1416:
1396:
1248:
1197:
1171:
1145:
1144:{\displaystyle M\in U}
1102:
1082:
1062:
986:
966:
908:
907:{\displaystyle M\in U}
882:
843:
842:{\displaystyle N\in U}
814:
813:{\displaystyle N\in U}
788:
787:{\displaystyle M\in U}
762:
742:
722:
702:
682:
653:
609:
571:
542:
522:
521:{\displaystyle M\in U}
493:
492:{\displaystyle N\in U}
467:
428:
427:{\displaystyle M\in U}
399:
342:
304:
265:
245:
221:
21:denotational semantics
2291:
2202:
2173:
2153:
2130:
2107:
2032:
2003:
1976:
1974:{\displaystyle \bot }
1931:
1862:
1833:
1810:
1710:
1667:
1640:
1638:{\displaystyle \bot }
1607:weak head normal form
1576:
1574:{\displaystyle \bot }
1511:
1417:
1397:
1249:
1247:{\displaystyle \bot }
1198:
1172:
1146:
1103:
1083:
1081:{\displaystyle \bot }
1063:
987:
967:
930:weak head normal form
909:
883:
844:
815:
789:
763:
743:
723:
708:can be obtained from
703:
683:
654:
610:
572:
543:
523:
494:
468:
429:
400:
343:
310:there exists a redex
305:
266:
246:
222:
182:, reduces to both to
84:typed lambda calculus
2674:"Regular Böhm Trees"
2672:Gérard Huet (1998).
2211:
2182:
2162:
2139:
2119:
2041:
2012:
1992:
1965:
1871:
1842:
1822:
1719:
1676:
1656:
1629:
1565:
1426:
1406:
1264:
1238:
1181:
1155:
1112:
1092:
1072:
1004:
976:
948:
892:
853:
827:
798:
772:
752:
748:with other terms of
732:
712:
692:
666:
619:
584:
552:
532:
506:
477:
438:
412:
352:
314:
275:
255:
235:
211:
125:standard lambda term
1949:) of a lambda term
1613:) of a lambda term
1559:undecidable problem
1222:) of a lambda term
681:{\displaystyle M,N}
2655:10.1007/BFb0014570
2372:10.1007/BFb0029523
2286:
2197:
2168:
2151:{\displaystyle NP}
2148:
2135:reduces to a term
2125:
2102:
2027:
2008:reduces to a term
1998:
1971:
1926:
1857:
1828:
1805:
1705:
1662:
1635:
1571:
1506:
1412:
1392:
1244:
1193:
1167:
1141:
1098:
1078:
1058:
982:
962:
904:
878:
839:
810:
784:
758:
738:
718:
698:
678:
649:
605:
567:
538:
528:and substitutions
518:
489:
463:
424:
395:
338:
300:
261:
241:
217:
2837:978-3-642-20919-2
2758:978-0-521-54327-9
2664:978-3-540-69530-1
2533:978-3-540-61735-8
2437:Logic and algebra
2319:Barendregt (1977)
2171:{\displaystyle N}
2128:{\displaystyle M}
2001:{\displaystyle M}
1831:{\displaystyle M}
1665:{\displaystyle M}
1415:{\displaystyle M}
1101:{\displaystyle U}
985:{\displaystyle U}
872:
761:{\displaystyle U}
741:{\displaystyle U}
721:{\displaystyle M}
701:{\displaystyle N}
580:Overlap: For all
457:
371:
294:
264:{\displaystyle M}
244:{\displaystyle U}
220:{\displaystyle U}
157:because applying
94:=(λx.x x)(λx.x x)
2870:
2848:
2846:
2844:
2817:
2807:
2787:
2762:
2743:
2741:
2739:
2726:
2714:
2696:
2678:
2668:
2648:
2634:
2619:
2618:
2600:
2594:
2588:
2577:
2571:
2565:
2559:
2553:
2547:
2538:
2537:
2517:
2501:
2495:
2489:
2483:
2482:
2464:
2458:
2457:
2455:
2453:
2434:
2425:
2419:
2418:
2416:
2392:
2386:
2385:
2359:
2342:
2331:
2325:
2311:
2295:
2293:
2292:
2287:
2276:
2253:
2227:
2206:
2204:
2203:
2198:
2177:
2175:
2174:
2169:
2157:
2155:
2154:
2149:
2134:
2132:
2131:
2126:
2111:
2109:
2108:
2103:
2092:
2057:
2036:
2034:
2033:
2028:
2007:
2005:
2004:
1999:
1980:
1978:
1977:
1972:
1941:Berarducci trees
1935:
1933:
1932:
1927:
1916:
1884:
1866:
1864:
1863:
1858:
1837:
1835:
1834:
1829:
1814:
1812:
1811:
1806:
1801:
1800:
1788:
1771:
1770:
1758:
1732:
1714:
1712:
1711:
1706:
1704:
1703:
1691:
1690:
1671:
1669:
1668:
1663:
1644:
1642:
1641:
1636:
1601:Lévy-Longo trees
1580:
1578:
1577:
1572:
1553:
1515:
1513:
1512:
1507:
1505:
1504:
1492:
1491:
1476:
1475:
1457:
1456:
1441:
1440:
1421:
1419:
1418:
1413:
1401:
1399:
1398:
1393:
1388:
1387:
1375:
1361:
1360:
1348:
1334:
1333:
1315:
1314:
1299:
1298:
1274:
1253:
1251:
1250:
1245:
1216:head normal form
1202:
1200:
1199:
1194:
1176:
1174:
1173:
1168:
1150:
1148:
1147:
1142:
1131:
1107:
1105:
1104:
1099:
1087:
1085:
1084:
1079:
1067:
1065:
1064:
1059:
991:
989:
988:
983:
971:
969:
968:
963:
955:
943:
924:head normal form
913:
911:
910:
905:
887:
885:
884:
879:
874:
873:
871:
866:
861:
848:
846:
845:
840:
819:
817:
816:
811:
793:
791:
790:
785:
767:
765:
764:
759:
747:
745:
744:
739:
727:
725:
724:
719:
707:
705:
704:
699:
687:
685:
684:
679:
658:
656:
655:
650:
614:
612:
611:
606:
576:
574:
573:
568:
547:
545:
544:
539:
527:
525:
524:
519:
498:
496:
495:
490:
472:
470:
469:
464:
459:
458:
456:
451:
446:
433:
431:
430:
425:
404:
402:
401:
396:
373:
372:
370:
365:
360:
347:
345:
344:
339:
309:
307:
306:
301:
296:
295:
293:
288:
283:
270:
268:
267:
262:
250:
248:
247:
242:
226:
224:
223:
218:
207:We define a set
198:
192:
181:
173:
166:
160:
156:
152:
146:
140:
129:
122:
116:
102:
95:
81:
75:
66:
37:Berarducci trees
33:Lévy-Longo trees
19:In the study of
2878:
2877:
2873:
2872:
2871:
2869:
2868:
2867:
2863:Lambda calculus
2853:
2852:
2851:
2842:
2840:
2838:
2815:
2810:
2796:
2765:
2759:
2746:
2737:
2735:
2724:
2717:
2676:
2671:
2665:
2646:10.1.1.110.7910
2632:
2627:
2623:
2622:
2615:
2602:
2601:
2597:
2589:
2580:
2572:
2568:
2564:, pp. 4–5.
2560:
2556:
2548:
2541:
2534:
2503:
2502:
2498:
2490:
2486:
2479:
2466:
2465:
2461:
2451:
2449:
2447:
2432:
2427:
2426:
2422:
2394:
2393:
2389:
2382:
2361:
2360:
2356:
2351:
2346:
2345:
2332:
2328:
2312:
2308:
2303:
2209:
2208:
2180:
2179:
2160:
2159:
2137:
2136:
2117:
2116:
2039:
2038:
2010:
2009:
1990:
1989:
1985:is root-active.
1963:
1962:
1943:
1869:
1868:
1840:
1839:
1820:
1819:
1792:
1762:
1717:
1716:
1695:
1682:
1674:
1673:
1654:
1653:
1627:
1626:
1603:
1563:
1562:
1520:
1496:
1483:
1467:
1448:
1432:
1424:
1423:
1404:
1403:
1379:
1352:
1325:
1306:
1290:
1262:
1261:
1236:
1235:
1212:
1179:
1178:
1153:
1152:
1110:
1109:
1090:
1089:
1070:
1069:
1002:
1001:
998:
974:
973:
946:
945:
939:
890:
889:
851:
850:
825:
824:
796:
795:
794:if and only if
770:
769:
750:
749:
730:
729:
710:
709:
690:
689:
664:
663:
617:
616:
582:
581:
550:
549:
530:
529:
504:
503:
475:
474:
436:
435:
410:
409:
350:
349:
312:
311:
273:
272:
253:
252:
233:
232:
209:
208:
205:
194:
183:
175:
171:
162:
158:
154:
148:
142:
131:
127:
118:
104:
97:
90:
77:
68:
61:
45:
25:lambda calculus
17:
12:
11:
5:
2876:
2874:
2866:
2865:
2855:
2854:
2850:
2849:
2836:
2808:
2794:
2763:
2757:
2744:
2715:
2694:10.1.1.123.475
2687:(6): 671–680.
2669:
2663:
2624:
2621:
2620:
2613:
2595:
2578:
2566:
2554:
2539:
2532:
2515:10.1.1.37.3616
2496:
2484:
2477:
2459:
2445:
2420:
2407:(2): 153–188.
2387:
2380:
2353:
2352:
2350:
2347:
2344:
2343:
2341:, p. 511)
2326:
2305:
2304:
2302:
2299:
2298:
2297:
2285:
2282:
2279:
2275:
2272:
2269:
2266:
2262:
2259:
2256:
2252:
2249:
2246:
2243:
2239:
2236:
2233:
2230:
2226:
2223:
2220:
2217:
2196:
2193:
2190:
2187:
2167:
2147:
2144:
2124:
2113:
2101:
2098:
2095:
2091:
2088:
2085:
2082:
2078:
2075:
2072:
2069:
2066:
2063:
2060:
2056:
2053:
2050:
2047:
2026:
2023:
2020:
2017:
1997:
1986:
1970:
1942:
1939:
1938:
1937:
1925:
1922:
1919:
1915:
1912:
1909:
1905:
1902:
1899:
1896:
1893:
1890:
1887:
1883:
1880:
1877:
1856:
1853:
1850:
1847:
1827:
1816:
1804:
1799:
1795:
1791:
1787:
1784:
1781:
1777:
1774:
1769:
1765:
1761:
1757:
1754:
1751:
1747:
1744:
1741:
1738:
1735:
1731:
1728:
1725:
1702:
1698:
1694:
1689:
1685:
1681:
1661:
1650:
1634:
1602:
1599:
1570:
1517:
1516:
1503:
1499:
1495:
1490:
1486:
1482:
1479:
1474:
1470:
1466:
1463:
1460:
1455:
1451:
1447:
1444:
1439:
1435:
1431:
1411:
1391:
1386:
1382:
1378:
1374:
1371:
1367:
1364:
1359:
1355:
1351:
1347:
1344:
1340:
1337:
1332:
1328:
1324:
1321:
1318:
1313:
1309:
1305:
1302:
1297:
1293:
1289:
1286:
1283:
1280:
1277:
1273:
1270:
1259:
1243:
1211:
1208:
1192:
1189:
1186:
1166:
1163:
1160:
1140:
1137:
1134:
1130:
1126:
1123:
1120:
1117:
1097:
1077:
1057:
1054:
1051:
1048:
1045:
1042:
1039:
1036:
1033:
1030:
1027:
1024:
1021:
1018:
1015:
1012:
1009:
997:
994:
981:
961:
958:
954:
936:
935:
932:
926:
916:
915:
903:
900:
897:
877:
870:
865:
858:
838:
835:
832:
821:
809:
806:
803:
783:
780:
777:
757:
737:
717:
697:
677:
674:
671:
660:
648:
645:
642:
639:
636:
633:
630:
627:
624:
604:
601:
598:
595:
592:
589:
578:
566:
563:
560:
557:
537:
517:
514:
511:
500:
488:
485:
482:
462:
455:
450:
443:
423:
420:
417:
406:
394:
391:
388:
385:
382:
379:
376:
369:
364:
357:
337:
334:
331:
328:
325:
322:
319:
299:
292:
287:
280:
260:
240:
216:
204:
201:
44:
41:
15:
13:
10:
9:
6:
4:
3:
2:
2875:
2864:
2861:
2860:
2858:
2839:
2833:
2829:
2825:
2821:
2814:
2809:
2805:
2801:
2797:
2795:9780444863881
2791:
2786:
2781:
2777:
2773:
2769:
2764:
2760:
2754:
2750:
2745:
2734:
2730:
2723:
2722:
2716:
2712:
2708:
2704:
2700:
2695:
2690:
2686:
2682:
2675:
2670:
2666:
2660:
2656:
2652:
2647:
2642:
2638:
2631:
2626:
2625:
2616:
2614:9781848900660
2610:
2606:
2599:
2596:
2592:
2587:
2585:
2583:
2579:
2575:
2570:
2567:
2563:
2558:
2555:
2551:
2546:
2544:
2540:
2535:
2529:
2525:
2521:
2516:
2511:
2507:
2500:
2497:
2493:
2488:
2485:
2480:
2474:
2470:
2463:
2460:
2448:
2442:
2438:
2431:
2424:
2421:
2415:
2410:
2406:
2402:
2398:
2391:
2388:
2383:
2381:3-540-07416-3
2377:
2373:
2369:
2365:
2358:
2355:
2348:
2340:
2336:
2330:
2327:
2324:
2320:
2316:
2310:
2307:
2300:
2280:
2257:
2237:
2231:
2194:
2191:
2188:
2185:
2165:
2145:
2142:
2122:
2114:
2096:
2076:
2073:
2070:
2067:
2061:
2024:
2021:
2018:
2015:
1995:
1987:
1984:
1960:
1956:
1955:
1954:
1952:
1948:
1940:
1920:
1903:
1900:
1897:
1894:
1888:
1854:
1851:
1848:
1845:
1825:
1817:
1797:
1793:
1775:
1767:
1763:
1745:
1742:
1736:
1700:
1696:
1692:
1687:
1683:
1679:
1659:
1651:
1648:
1624:
1620:
1619:
1618:
1616:
1612:
1608:
1600:
1598:
1595:
1591:
1587:
1582:
1560:
1555:
1551:
1547:
1543:
1540:
1536:
1532:
1528:
1524:
1519:For example,
1501:
1497:
1493:
1488:
1484:
1480:
1477:
1472:
1468:
1464:
1461:
1458:
1453:
1449:
1445:
1442:
1437:
1433:
1429:
1409:
1384:
1380:
1365:
1357:
1353:
1338:
1335:
1330:
1326:
1322:
1319:
1316:
1311:
1307:
1303:
1300:
1295:
1291:
1287:
1284:
1278:
1260:
1257:
1233:
1229:
1228:
1227:
1225:
1221:
1217:
1209:
1207:
1204:
1184:
1161:
1158:
1138:
1135:
1115:
1095:
1052:
1049:
1043:
1037:
1034:
1031:
1028:
1022:
1019:
1016:
1010:
1007:
995:
993:
979:
959:
956:
942:
933:
931:
927:
925:
921:
920:
919:
901:
898:
895:
875:
868:
856:
836:
833:
830:
822:
807:
804:
801:
781:
778:
775:
755:
735:
715:
695:
675:
672:
669:
661:
646:
643:
640:
634:
631:
628:
625:
602:
599:
596:
593:
590:
587:
579:
564:
561:
558:
555:
535:
515:
512:
509:
501:
486:
483:
480:
460:
453:
441:
421:
418:
415:
407:
392:
386:
383:
380:
377:
367:
355:
335:
329:
326:
323:
320:
297:
290:
278:
258:
238:
230:
229:
228:
214:
202:
200:
197:
190:
186:
179:
168:
165:
151:
145:
138:
135:
126:
121:
114:
111:
107:
101:
93:
87:
85:
80:
74:
71:
64:
59:
55:
51:
42:
40:
38:
34:
30:
26:
22:
2843:23 September
2841:. Retrieved
2819:
2767:
2748:
2738:23 September
2736:. Retrieved
2720:
2684:
2680:
2636:
2604:
2598:
2593:, p. 6.
2576:, p. 2.
2569:
2557:
2552:, p. 5.
2505:
2499:
2494:, p. 1.
2487:
2468:
2462:
2452:23 September
2450:. Retrieved
2436:
2423:
2404:
2400:
2390:
2363:
2357:
2329:
2323:Corrado Böhm
2309:
1982:
1958:
1950:
1946:
1944:
1646:
1622:
1614:
1610:
1604:
1593:
1589:
1585:
1583:
1556:
1549:
1545:
1541:
1538:
1534:
1530:
1526:
1522:
1518:
1255:
1231:
1223:
1219:
1213:
1205:
999:
940:
937:
917:
206:
195:
188:
184:
177:
169:
163:
149:
143:
136:
133:
123:denotes the
119:
112:
109:
105:
99:
91:
88:
78:
72:
69:
62:
46:
36:
32:
28:
18:
54:normal form
2785:2066/17225
2478:0691083940
2446:0824796063
2349:References
2335:Ong (1988)
2333:coined in
1533:, and BT(λ
1210:Böhm trees
938:Note that
348:such that
43:Motivation
29:Böhm trees
2689:CiteSeerX
2641:CiteSeerX
2510:CiteSeerX
2186:λ
2071:λ
2016:λ
1969:⊥
1898:λ
1846:λ
1776:…
1693:…
1633:⊥
1569:⊥
1494:…
1465:λ
1462:…
1446:λ
1430:λ
1366:…
1323:λ
1320:…
1304:λ
1288:λ
1242:⊥
1191:⊥
1188:→
1165:⊥
1162:≠
1136:∈
1129:Ω
1125:↦
1122:⊥
1076:⊥
1044:∣
1029:λ
1023:∣
1017:∣
1014:⊥
957:∈
953:Ω
899:∈
869:∗
864:→
834:∈
805:∈
779:∈
644:∈
626:λ
600:∈
588:λ
562:∈
559:σ
536:σ
513:∈
484:∈
454:∗
449:→
419:∈
378:λ
368:∗
363:→
321:λ
291:∗
286:→
251:. A term
76:are both
50:rewriting
2857:Category
2804:25828519
2733:31204528
2711:15752309
1525:)=⊥, BT(
996:λ⊥-terms
174:, where
167:cannot.
117:, where
58:Church's
2207:, then
2037:, then
1867:, then
1715:, then
1177:, then
888:, then
768:, then
176:N = λx.
128:λx.λy.x
23:of the
2834:
2802:
2792:
2755:
2731:
2709:
2691:
2661:
2643:
2611:
2530:
2512:
2475:
2443:
2378:
2337:, per
2158:where
191:(...))
98:X=λx.x
65:= λx.x
35:, and
2816:(PDF)
2800:S2CID
2725:(PDF)
2707:S2CID
2677:(PDF)
2633:(PDF)
2433:(PDF)
2301:Notes
1981:, if
1961:) is
1957:BerT(
1645:, if
1625:) is
1588:. If
1402:, if
1254:, if
1234:) is
849:, if
688:, if
473:then
434:, if
2845:2022
2832:ISBN
2790:ISBN
2753:ISBN
2740:2022
2729:OCLC
2659:ISBN
2609:ISBN
2528:ISBN
2473:ISBN
2454:2007
2441:ISBN
2376:ISBN
2313:per
1621:LLT(
1151:and
193:and
180:(xx)
67:and
2824:doi
2780:hdl
2772:doi
2699:doi
2651:doi
2520:doi
2409:doi
2368:doi
2115:If
1988:If
1818:If
1652:If
1544:)=λ
1521:BT(
1230:BT(
172:N N
132:X (
2859::
2830:.
2818:.
2798:.
2788:.
2778:.
2705:.
2697:.
2683:.
2679:.
2657:.
2649:.
2581:^
2542:^
2526:.
2518:.
2435:.
2405:24
2403:.
2399:.
2374:.
1581:.
1554:.
1529:)=
992:.
615:,
548:,
86:.
31:,
27:,
2847:.
2826::
2806:.
2782::
2774::
2761:.
2742:.
2713:.
2701::
2685:8
2667:.
2653::
2617:.
2536:.
2522::
2481:.
2456:.
2417:.
2411::
2384:.
2370::
2296:.
2284:)
2281:P
2278:(
2274:T
2271:r
2268:e
2265:B
2261:)
2258:N
2255:(
2251:T
2248:r
2245:e
2242:B
2238:=
2235:)
2232:M
2229:(
2225:T
2222:r
2219:e
2216:B
2195:Q
2192:.
2189:x
2166:N
2146:P
2143:N
2123:M
2112:.
2100:)
2097:N
2094:(
2090:T
2087:r
2084:e
2081:B
2077:.
2074:x
2068:=
2065:)
2062:M
2059:(
2055:T
2052:r
2049:e
2046:B
2025:N
2022:.
2019:x
1996:M
1983:M
1959:M
1951:M
1947:M
1936:/
1924:)
1921:N
1918:(
1914:T
1911:L
1908:L
1904:.
1901:x
1895:=
1892:)
1889:M
1886:(
1882:T
1879:L
1876:L
1855:N
1852:.
1849:x
1826:M
1815:.
1803:)
1798:m
1794:M
1790:(
1786:T
1783:L
1780:L
1773:)
1768:1
1764:M
1760:(
1756:T
1753:L
1750:L
1746:y
1743:=
1740:)
1737:M
1734:(
1730:T
1727:L
1724:L
1701:m
1697:M
1688:1
1684:M
1680:y
1660:M
1647:M
1623:M
1615:M
1611:M
1594:M
1590:M
1586:M
1552:⊥
1550:x
1548:.
1546:x
1542:Ω
1539:x
1537:.
1535:x
1531:I
1527:I
1523:Ω
1502:m
1498:M
1489:1
1485:M
1481:y
1478:.
1473:n
1469:x
1459:.
1454:2
1450:x
1443:.
1438:1
1434:x
1410:M
1390:)
1385:m
1381:M
1377:(
1373:T
1370:B
1363:)
1358:1
1354:M
1350:(
1346:T
1343:B
1339:y
1336:.
1331:n
1327:x
1317:.
1312:2
1308:x
1301:.
1296:1
1292:x
1285:=
1282:)
1279:M
1276:(
1272:T
1269:B
1256:M
1232:M
1224:M
1220:M
1185:M
1159:M
1139:U
1133:]
1119:[
1116:M
1096:U
1056:)
1053:M
1050:M
1047:(
1041:)
1038:M
1035:.
1032:x
1026:(
1020:x
1011:=
1008:M
980:U
960:U
941:Ω
902:U
896:M
876:N
857:M
837:U
831:N
820:.
808:U
802:N
782:U
776:M
756:U
736:U
716:M
696:N
676:N
673:,
670:M
659:.
647:U
641:N
638:)
635:M
632:.
629:x
623:(
603:U
597:M
594:.
591:x
577:.
565:U
556:M
516:U
510:M
499:.
487:U
481:N
461:N
442:M
422:U
416:M
405:.
393:Q
390:)
387:P
384:.
381:x
375:(
356:N
336:Q
333:)
330:P
327:.
324:x
318:(
298:N
279:M
259:M
239:U
215:U
196:Ω
189:I
187:(
185:I
178:I
164:Ω
159:X
155:X
150:Ω
144:I
139:)
137:I
134:K
120:K
115:)
113:I
110:K
108:(
106:Ω
100:Ω
92:Ω
79:I
73:I
70:I
63:I
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.