1 <?xml version="1.0" encoding="UTF-8"?>
2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
3 <html xmlns="http://www.w3.org/1999/xhtml" dir="ltr" lang="en-us">
5 <meta http-equiv="Content-Language" content="en-us" />
6 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
7 <meta http-equiv="Content-Style-Type" content="text/css" />
8 <meta name="author" content="Ferruccio Guidi" />
9 <meta name="description" content="\lambda\delta home page" />
10 <title>\lambda\delta home page</title>
11 <link rel="stylesheet" type="text/css" href="http://lambdadelta.info/css/ld_web.css" />
12 <link rel="stylesheet" type="text/css" href="http://lambdadelta.info/css/lddl.css" />
13 <link rel="stylesheet" type="text/css" href="http://lambdadelta.info/css/xhtbl.css" />
14 <link rel="shortcut icon" href="http://lambdadelta.info/images/crux_16.ico" />
18 <a href="http://lambdadelta.info/">
19 <img class="icon32" alt="[\lambda\delta home]" title="\lambda\delta home" src="http://lambdadelta.info/images/crux_32.png" />
22 <div class="head1">cic:/matita/lambdadelta/basic_2/ (core λδ version 2)</div>
24 <img class="rule" alt="[Spacer]" title="\lambda\delta rainbow rule" src="http://lambdadelta.info/images/rainbow.png" />
26 <div xmlns:ld="http://lambdadelta.info/" class="spacer">
29 <div xmlns:ld="http://lambdadelta.info/" class="text">
30 <table cellpadding="4" cellspacing="0">
33 <td class="snns capitalize italic sky">
34 <a href="http://lambdadelta.info/home.html">home</a>
36 <td class="snns capitalize italic magenta">
37 <a href="http://lambdadelta.info/news.html">news</a>
39 <td class="snns capitalize italic white">
40 <a href="http://lambdadelta.info/specification.html">specification</a>
42 <td class="snnn capitalize italic white">
45 <td class="snnn capitalize italic white">
48 <td class="snns capitalize italic orange">
49 <a href="http://lambdadelta.info/documentation.html">documentation</a>
51 <td class="snns capitalize italic green">
52 <a href="http://lambdadelta.info/implementation.html">implementation</a>
54 <td class="ssnn capitalize italic green">
59 <td class="snns capitalize sky">
60 <a href="http://lambdadelta.info/home.html#foreword">foreword</a>
62 <td class="snns capitalize magenta">
63 <a href="http://lambdadelta.info/news.html#milestones">milestones</a>
65 <td class="snns capitalize white">
66 <a href="http://lambdadelta.info/specification.html#v2">version 2</a>
68 <td class="snnn capitalize white">(<a href="http://lambdadelta.info/ground_2.html">background</a> - <a href="http://lambdadelta.info/basic_2.html">core</a> - <a href="http://lambdadelta.info/apps_2.html">applications</a>)</td>
69 <td class="snnn capitalize white">
72 <td class="snns capitalize orange">
73 <a href="http://lambdadelta.info/documentation.html#v2">version 2</a>
75 <td class="snns capitalize green">
76 <a href="http://lambdadelta.info/implementation.html#helena">helena</a>
78 <td class="ssnn capitalize green">
79 <a href="http://lambdadelta.info/osn/">Open Symbolic Notation (OSN)</a>
83 <td class="snss capitalize sky">
84 <a href="http://lambdadelta.info/home.html#citations">citations</a>
86 <td class="snss capitalize magenta">
87 <a href="http://lambdadelta.info/news.html#visibility">visibility</a>
89 <td class="snss capitalize white">
90 <a href="http://lambdadelta.info/specification.html#v1">version 1</a>
92 <td class="snsn capitalize white">(<a href="http://lambdadelta.info/ground_1.html">background</a> - <a href="http://lambdadelta.info/basic_1.html">core</a>)</td>
93 <td class="snsn capitalize white">(<a href="http://lambdadelta.info/static/matita/lambdadelta/">static HELM directory</a>)</td>
94 <td class="snss capitalize orange">
95 <a href="http://lambdadelta.info/documentation.html#v1">version 1</a>
97 <td class="snss capitalize green">
98 <a href="http://lambdadelta.info/implementation.html#lddl">library</a>
100 <td class="sssn capitalize green">(<a href="http://lambdadelta.info/static/lddl/">static LDDL directory</a>)</td>
106 <section>System's Syntax and Behavior</section>
107 <body>This is a summary of the "block structure"
108 of the System's syntactic items and reductions.
110 <table name="basic_2_blk"/>
111 <body>* In terms only.
112 ** In terms and local environments only.
113 *** In global environments only.
114 **** Sort level k in terms only.
117 <div xmlns:ld="http://lambdadelta.info/" class="head2dx" id="summary">Summary of the Specification <img class="icon37" alt="[butterfly]" title="\lambda\delta butterfly" src="http://lambdadelta.info/images/b4.png" />
119 <div xmlns:ld="http://lambdadelta.info/" class="text">Here is a numerical account of the specification's contents
122 <div xmlns:ld="http://lambdadelta.info/" class="text">
123 <table cellpadding="4" cellspacing="0">
126 <td class="snns capitalize italic gray">category</td>
127 <td class="snns italic gray">objects</td>
128 <td class="snnn right italic gray">
131 <td class="snnn italic gray">
134 <td class="snnn right italic gray">
137 <td class="snnn italic gray">
140 <td class="ssnn right italic gray">
145 <td class="snns capitalize italic cyan">sizes</td>
146 <td class="snns italic cyan">files</td>
147 <td class="snnn right italic cyan">150</td>
148 <td class="snns italic cyan">characters</td>
149 <td class="snnn right italic cyan">128505</td>
150 <td class="snns italic cyan">nodes</td>
151 <td class="ssnn right italic cyan">646562</td>
154 <td class="snns capitalize italic green">propositions</td>
155 <td class="snns italic green">theorems</td>
156 <td class="snnn right italic green">45</td>
157 <td class="snns italic green">lemmas</td>
158 <td class="snnn right italic green">476</td>
159 <td class="snns italic green">total</td>
160 <td class="ssnn right italic green">521</td>
163 <td class="snss capitalize italic yellow">concepts</td>
164 <td class="snss italic yellow">declared</td>
165 <td class="snsn right italic yellow">23</td>
166 <td class="snss italic yellow">defined</td>
167 <td class="snsn right italic yellow">37</td>
168 <td class="snss italic yellow">total</td>
169 <td class="sssn right italic yellow">60</td>
174 <div xmlns:ld="http://lambdadelta.info/" class="head3sn" id="B">Stage "B"</div>
175 <ul xmlns:ld="http://lambdadelta.info/">
177 <span class="emph alpha">Ongoing.</span>
178 Context-sensitive subject equivalence
179 for native type assignment.
182 <div xmlns:ld="http://lambdadelta.info/" class="head3sn" id="A2">Stage "A2": "Extending the Applicability Condition"</div>
183 <ul xmlns:ld="http://lambdadelta.info/">
185 <span class="emph alpha">2016 April 16.</span>
186 Grammatical component reconstructed:
187 grammar, relocation, s_transition, s_computation, static
188 (anniversary milestone).
191 <ul xmlns:ld="http://lambdadelta.info/">
193 <span class="emph alpha">2016 March 25.</span>
194 Relocation with reference transforming maps (rtmap).
197 <ul xmlns:ld="http://lambdadelta.info/">
199 <span class="emph alpha">2015 October 9.</span>
200 λδ version 2A2 is started.
203 <div xmlns:ld="http://lambdadelta.info/" class="head3sn" id="A1">Stage "A1": "Extending the Applicability Condition"</div>
204 <ul xmlns:ld="http://lambdadelta.info/">
206 <span class="emph delta">2015 August 27.</span>
207 λδ version 2A1 appears too complex and is dismissed.
210 <ul xmlns:ld="http://lambdadelta.info/">
212 <span class="emph gamma">2014 October 28.</span>
213 λδ version 2A1 is released.
216 <ul xmlns:ld="http://lambdadelta.info/">
218 <span class="emph beta">2014 September 9.</span>
219 Iterated static type assignment defined (more elegantly)
220 as a primitive notion.
223 <ul xmlns:ld="http://lambdadelta.info/">
225 <span class="emph beta">2014 June 18.</span>
226 Preservation of stratified native validity
227 for context-sensitive computation on terms.
230 <ul xmlns:ld="http://lambdadelta.info/">
232 <span class="emph alpha">2014 June 9.</span>
233 Strong qrst-normalization
234 for simply typed terms.
237 <ul xmlns:ld="http://lambdadelta.info/">
239 <span class="emph alpha">2014 April 16.</span>
240 Lazy equivalence on local environments
241 added as q-step to rst-computation on closures
242 (anniversary milestone).
245 <ul xmlns:ld="http://lambdadelta.info/">
247 <span class="emph alpha">2014 January 20.</span>
248 Parametrized slicing of local environments
249 comprises both versions of this operation
250 (one from basic_1, the other used in basic_2 till now).
253 <ul xmlns:ld="http://lambdadelta.info/">
255 <span class="emph alpha">2013 August 7.</span>
256 Passive support for global environments.
259 <ul xmlns:ld="http://lambdadelta.info/">
261 <span class="emph alpha">2013 July 27.</span>
262 Reaxiomatized β-reductum as in rt-reduction.
265 <ul xmlns:ld="http://lambdadelta.info/">
267 <span class="emph alpha">2013 July 20.</span>
268 Context-sensitive strong rt-normalization
269 for simply typed terms.
272 <ul xmlns:ld="http://lambdadelta.info/">
274 <span class="emph alpha">2013 April 16.</span>
275 Reaxiomatized substitution and reduction
276 commute with respect to subclosure
277 (anniversary milestone).
280 <ul xmlns:ld="http://lambdadelta.info/">
282 <span class="emph alpha">2013 March 16.</span>
283 Mutual recursive preservation of stratified native validity
284 for rst-computation on closures.
287 <ul xmlns:ld="http://lambdadelta.info/">
289 <span class="emph alpha">2012 October 16.</span>
290 Confluence for context-free parallel reduction on closures.
293 <ul xmlns:ld="http://lambdadelta.info/">
295 <span class="emph alpha">2012 July 26.</span>
296 Term binders polarized to control ζ-reduction (not released).
299 <ul xmlns:ld="http://lambdadelta.info/">
301 <span class="emph alpha">2012 April 16.</span>
302 Context-sensitive subject equivalence
303 for atomic arity assignment
304 (anniversary milestone).
307 <ul xmlns:ld="http://lambdadelta.info/">
309 <span class="emph alpha">2012 March 15.</span>
310 Context-sensitive strong normalization
311 for simply typed terms.
314 <ul xmlns:ld="http://lambdadelta.info/">
316 <span class="emph alpha">2012 January 27.</span>
317 Support for abstract candidates of reducibility.
320 <ul xmlns:ld="http://lambdadelta.info/">
322 <span class="emph alpha">2011 September 21.</span>
323 Confluence for context-sensitive parallel reduction on terms.
326 <ul xmlns:ld="http://lambdadelta.info/">
328 <span class="emph alpha">2011 September 6.</span>
329 Confluence for context-free parallel reduction on terms.
332 <ul xmlns:ld="http://lambdadelta.info/">
334 <span class="emph alpha">2011 April 17.</span>
335 λδ version 2 is started.
338 <div xmlns:ld="http://lambdadelta.info/" class="head2dx" id="structure">Logical Structure of the Specification <img class="icon37" alt="[butterfly]" title="\lambda\delta butterfly" src="http://lambdadelta.info/images/b4.png" />
340 <div xmlns:ld="http://lambdadelta.info/" class="text">This table reports the specification's components and their planes.
342 <div xmlns:ld="http://lambdadelta.info/" class="text">
343 <table cellpadding="4" cellspacing="0">
346 <td class="snns top capitalize italic gray">component</td>
347 <td class="snns top italic gray">plane</td>
348 <td class="snns top gray">files</td>
349 <td class="snnn top gray">
352 <td class="snnn top gray">
355 <td class="ssnn top gray">
360 <td class="snns top capitalize italic water">rt-transition</td>
361 <td class="snns top italic water">uncounted context-sensitive rt-transition</td>
362 <td class="snns top water">lfpx ( ⦃?,?⦄ ⊢ ⬈[?,?] ? )</td>
363 <td class="snnn top water">lfpx_length lfpx_drops lfpx_fqup</td>
364 <td class="snnn top water">
367 <td class="ssnn top water">
372 <td class="nnns top capitalize italic water">
375 <td class="nnns top italic water">
378 <td class="snns top water">cpx ( ⦃?,?⦄ ⊢ ? ⬈[?] ? )</td>
379 <td class="snnn top water">cpx_simple cpx_drops cpx_lsubr</td>
380 <td class="snnn top water">
383 <td class="ssnn top water">
388 <td class="nnns top capitalize italic water">
391 <td class="snns top italic water">counted context-sensitive rt-transition</td>
392 <td class="snns top water">cpg ( ⦃?,?⦄ ⊢ ? ⬈[?,?] ? )</td>
393 <td class="snnn top water">cpg_simple cpg_drops cpg_lsubr</td>
394 <td class="snnn top water">
397 <td class="ssnn top water">
402 <td class="snns top capitalize italic green">static typing</td>
403 <td class="snns top italic green">parameters</td>
404 <td class="snns top green">sh</td>
405 <td class="snnn top green">sd</td>
406 <td class="snnn top green">
409 <td class="ssnn top green">
414 <td class="nnns top capitalize italic green">
417 <td class="snns top italic green">restricted ref. for atomic arity assignment</td>
418 <td class="snns top green">lsuba ( ? ⊢ ? ⫃⁝ ? )</td>
419 <td class="snnn top green">lsuba_drops lsuba_lsubr lsuba_aaa lsuba_lsuba</td>
420 <td class="snnn top green">
423 <td class="ssnn top green">
428 <td class="nnns top capitalize italic green">
431 <td class="snns top italic green">atomic arity assignment</td>
432 <td class="snns top green">aaa ( ⦃?,?⦄ ⊢ ? ⁝ ? )</td>
433 <td class="snnn top green">aaa_drops aaa_fqus aaa_lfeq aaa_aaa</td>
434 <td class="snnn top green">
437 <td class="ssnn top green">
442 <td class="nnns top capitalize italic green">
445 <td class="snns top italic green">restricted ref. for local env.</td>
446 <td class="snns top green">lsubr ( ? ⫃ ? )</td>
447 <td class="snnn top green">lsubr_length lsubr_drops lsubr_lsubr</td>
448 <td class="snnn top green">
451 <td class="ssnn top green">
456 <td class="nnns top capitalize italic green">
459 <td class="snns top italic green">equivalence for closures on referred entries</td>
460 <td class="snns top green">ffeq ( ⦃?,?,?⦄ ≡ ⦃?,?,?⦄ )</td>
461 <td class="snnn top green">ffeq_freq</td>
462 <td class="snnn top green">
465 <td class="ssnn top green">
470 <td class="nnns top capitalize italic green">
473 <td class="snns top italic green">equivalence for local environments on referred entries</td>
474 <td class="snns top green">lfeq ( ? ≡[?] ? )</td>
475 <td class="snnn top green">lfeq_length lfeq_lreq lfeq_fqup lfeq_lfeq</td>
476 <td class="snnn top green">
479 <td class="ssnn top green">
484 <td class="nnns top capitalize italic green">
487 <td class="snns top italic green">generic extension on referred entries</td>
488 <td class="snns top green">lfxs ( ? ⦻*[?,?] ? )</td>
489 <td class="snnn top green">lfxs_length lfxs_drops lfxs_fqup lfxs_lfxs</td>
490 <td class="snnn top green">
493 <td class="ssnn top green">
498 <td class="nnns top capitalize italic green">
501 <td class="snns top italic green">context-sensitive free variables</td>
502 <td class="snns top green">frees ( ? ⊢ 𝐅*⦃?⦄ ≡ ? )</td>
503 <td class="snnn top green">frees_weight frees_lreq frees_drops frees_frees</td>
504 <td class="snnn top green">
507 <td class="ssnn top green">
512 <td class="snns top capitalize italic grass">s-computation</td>
513 <td class="snns top italic grass">iterated structural successor for closures</td>
514 <td class="snns top grass">fqus ( ⦃?,?,?⦄ ⊐* ⦃?,?,?⦄ )</td>
515 <td class="snnn top grass">fqus_weight fqus_drops fqus_fqup fqus_fqus</td>
516 <td class="snnn top grass">
519 <td class="ssnn top grass">
524 <td class="nnns top capitalize italic grass">
527 <td class="nnns top italic grass">
530 <td class="snns top grass">fqup ( ⦃?,?,?⦄ ⊐+ ⦃?,?,?⦄ )</td>
531 <td class="snnn top grass">fqup_weight fqup_drops fqup_fqup</td>
532 <td class="snnn top grass">
535 <td class="ssnn top grass">
540 <td class="snns top capitalize italic yellow">s-transition</td>
541 <td class="snns top italic yellow">structural successor for closures</td>
542 <td class="snns top yellow">fquq ( ⦃?,?,?⦄ ⊐⸮ ⦃?,?,?⦄ )</td>
543 <td class="snnn top yellow">fquq_length fquq_weight</td>
544 <td class="snnn top yellow">
547 <td class="ssnn top yellow">
552 <td class="nnns top capitalize italic yellow">
555 <td class="nnns top italic yellow">
558 <td class="snns top yellow">fqu ( ⦃?,?,?⦄ ⊐ ⦃?,?,?⦄ )</td>
559 <td class="snnn top yellow">fqu_length fqu_weight</td>
560 <td class="snnn top yellow">
563 <td class="ssnn top yellow">
568 <td class="snns top capitalize italic orange">relocation</td>
569 <td class="snns top italic orange">generic slicing for local environments</td>
570 <td class="snns top orange">drops_vector ( ⬇*[?,?] ? ≡ ? ) ( ⬇*[?] ? ≡ ? )</td>
571 <td class="snnn top orange">
574 <td class="snnn top orange">
577 <td class="ssnn top orange">
582 <td class="nnns top capitalize italic orange">
585 <td class="nnns top italic orange">
588 <td class="snns top orange">drops ( ⬇*[?,?] ? ≡ ? ) ( ⬇*[?] ? ≡ ? )</td>
589 <td class="snnn top orange">drops_lstar drops_weight drops_length drops_ceq drops_lexs drops_lreq drops_drops</td>
590 <td class="snnn top orange">
593 <td class="ssnn top orange">
598 <td class="nnns top capitalize italic orange">
601 <td class="snns top italic orange">generic relocation for terms</td>
602 <td class="snns top orange">lifts_vector ( ⬆*[?] ? ≡ ? )</td>
603 <td class="snnn top orange">lifts_lifts_vector</td>
604 <td class="snnn top orange">
607 <td class="ssnn top orange">
612 <td class="nnns top capitalize italic orange">
615 <td class="nnns top italic orange">
618 <td class="snns top orange">lifts ( ⬆*[?] ? ≡ ? )</td>
619 <td class="snnn top orange">lifts_simple lifts_weight lifts_lifts</td>
620 <td class="snnn top orange">
623 <td class="ssnn top orange">
628 <td class="nnns top capitalize italic orange">
631 <td class="snns top italic orange">ranged equivalence for local environments</td>
632 <td class="snns top orange">lreq ( ? ≡[?] ? )</td>
633 <td class="snnn top orange">lreq_length lreq_lreq</td>
634 <td class="snnn top orange">
637 <td class="ssnn top orange">
642 <td class="nnns top capitalize italic orange">
645 <td class="snns top italic orange">generic entrywise extension</td>
646 <td class="snns top orange">lexs ( ? ⦻*[?,?,?] ? )</td>
647 <td class="snnn top orange">lexs_length lexs_lexs</td>
648 <td class="snnn top orange">
651 <td class="ssnn top orange">
656 <td class="snns top capitalize italic red">grammar</td>
657 <td class="snns top italic red">append for local environments</td>
658 <td class="snns top red">append ( ? @@ ? )</td>
659 <td class="snnn top red">append_length</td>
660 <td class="snnn top red">
663 <td class="ssnn top red">
668 <td class="nnns top capitalize italic red">
671 <td class="snns top italic red">context-sensitive equivalences for terms</td>
672 <td class="snns top red">ceq</td>
673 <td class="snnn top red">ceq_ceq</td>
674 <td class="snnn top red">
677 <td class="ssnn top red">
682 <td class="nnns top capitalize italic red">
685 <td class="snns top italic red">same top term structure</td>
686 <td class="snns top red">tsts ( ? ≂ ? )</td>
687 <td class="snnn top red">tsts_tsts tsts_vector</td>
688 <td class="snnn top red">
691 <td class="ssnn top red">
696 <td class="nnns top capitalize italic red">
699 <td class="snns top italic red">closures</td>
700 <td class="snns top red">cl_weight ( ♯{?,?,?} )</td>
701 <td class="snnn top red">cl_restricted_weight ( ♯{?,?} )</td>
702 <td class="snnn top red">
705 <td class="ssnn top red">
710 <td class="nnns top capitalize italic red">
713 <td class="snns top italic red">internal syntax</td>
714 <td class="snns top red">genv</td>
715 <td class="snnn top red">
718 <td class="snnn top red">
721 <td class="ssnn top red">
726 <td class="nnns top capitalize italic red">
729 <td class="nnns top italic red">
732 <td class="snns top red">lenv</td>
733 <td class="snnn top red">lenv_weight ( ♯{?} )</td>
734 <td class="snnn top red">lenv_length ( |?| )</td>
735 <td class="ssnn top red">
740 <td class="nnns top capitalize italic red">
743 <td class="nnns top italic red">
746 <td class="snns top red">term</td>
747 <td class="snnn top red">term_weight ( ♯{?} )</td>
748 <td class="snnn top red">term_simple ( 𝐒⦃?⦄ )</td>
749 <td class="ssnn top red">term_vector ( Ⓐ?.? )</td>
752 <td class="nnns top capitalize italic red">
755 <td class="nnns top italic red">
758 <td class="snns top red">item</td>
759 <td class="snnn top red">
762 <td class="snnn top red">
765 <td class="ssnn top red">
770 <td class="nnss top capitalize italic red">
773 <td class="snss top italic red">external syntax</td>
774 <td class="snss top red">aarity</td>
775 <td class="snsn top red">
778 <td class="snsn top red">
781 <td class="sssn top red">
789 <img class="rule" alt="[Spacer]" title="\lambda\delta rainbow rule" src="http://lambdadelta.info/images/rainbow.png" />
791 <div xmlns:ld="http://lambdadelta.info/" class="spacer">
794 <div xmlns:ld="http://lambdadelta.info/" class="spacer">
795 <a href="http://validator.w3.org/check?uri=referer">
796 <img class="w3c" alt="[Valid XHTML 1.1]" title="Valid XHTML 1.1" src="http://www.w3.org/Icons/valid-xhtml11-blue" />
798 <a href="http://jigsaw.w3.org/css-validator/check/referer">
799 <img class="w3c" alt="[Valid CSS level 2]" title="Valid CSS level 2" src="http://www.w3.org/Icons/valid-css2-blue" />
801 <a href="http://www.w3.org/XML/">
802 <img class="w3c" alt="[Generated from XML via XSL]" title="Generated from XML via XSL" src="http://lambdadelta.info/images/xml_xsl2.png" />
804 <a href="http://www.w3.org/Graphics/PNG/">
805 <img class="w3c" alt="[PNG used here]" title="PNG used here" src="http://lambdadelta.info/images/PNGnow2.png" />
807 <a href="http://www.anybrowser.org/campaign/">
808 <img class="w3c" alt="[Viewable with any browser]" title="Viewable with any browser" src="http://www.anybrowser.org/campaign/bvgraphics/abtfile.png" />
811 <div xmlns:ld="http://lambdadelta.info/" class="spacer">
814 <div xmlns:ld="http://lambdadelta.info/" class="spacer">Last update: Fri, 22 Jul 2016 19:34:08 +0200</div>