helm/www/lambdadelta/specification.html

   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" xmlns:ld="http://lambdadelta.info/" dir="ltr" lang="en-us"><head><meta http-equiv="Content-Language" content="en-us"/><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/><meta http-equiv="Content-Style-Type" content="text/css"/><meta name="author" content="Ferruccio Guidi"/><meta name="description" content="\lambda\delta home page"/><title>\lambda\delta home page</title><link rel="stylesheet" type="text/css" href="http://lambdadelta.info/css/ld_web.css"/><link rel="stylesheet" type="text/css" href="http://lambdadelta.info/css/lddl.css"/><link rel="stylesheet" type="text/css" href="http://lambdadelta.info/css/xhtbl.css"/><link rel="shortcut icon" href="http://lambdadelta.info/images/crux_16.ico"/></head><body lang="en-US"><div class="spacer"><a href="http://lambdadelta.info/"><img class="icon32" alt="[\lambda\delta home]" title="\lambda\delta home" src="http://lambdadelta.info/images/crux_32.png"/></a></div><div class="head1">The Formal Systems of the λδ (\lambda\delta) Family</div><div class="spacer"><img class="rule" alt="[Spacer]" title="\lambda\delta rainbow rule" src="http://lambdadelta.info/images/rainbow.png"/></div><div class="spacer"><br/></div><div class="text"><table cellpadding="4" cellspacing="0"><tbody><tr><td class="snns capitalize italic sky"><a href="http://lambdadelta.info/home.html">home</a></td><td class="snns capitalize italic magenta"><a href="http://lambdadelta.info/news.html">news</a></td><td class="snns capitalize italic white"><a href="http://lambdadelta.info/specification.html">specification</a></td><td class="snnn capitalize italic white"><br/></td><td class="snnn capitalize italic white"><br/></td><td class="snns capitalize italic orange"><a href="http://lambdadelta.info/documentation.html">documentation</a></td><td class="snns capitalize italic green"><a href="http://lambdadelta.info/implementation.html">implementation</a></td><td class="ssnn capitalize italic green"><br/></td></tr><tr><td class="snns capitalize sky"><a href="http://lambdadelta.info/home.html#foreword">foreword</a></td><td class="snns capitalize magenta"><a href="http://lambdadelta.info/news.html#milestones">milestones</a></td><td class="snns capitalize white"><a href="http://lambdadelta.info/specification.html#v2">version 2</a></td><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><td class="snnn capitalize white"><br/></td><td class="snns capitalize orange"><a href="http://lambdadelta.info/documentation.html#v2">version 2</a></td><td class="snns capitalize green"><a href="http://lambdadelta.info/implementation.html#helena">helena</a></td><td class="ssnn capitalize green"><a href="http://lambdadelta.info/osn/">Open Symbolic Notation (OSN)</a></td></tr><tr><td class="snss capitalize sky"><a href="http://lambdadelta.info/home.html#citations">citations</a></td><td class="snss capitalize magenta"><a href="http://lambdadelta.info/news.html#visibility">visibility</a></td><td class="snss capitalize white"><a href="http://lambdadelta.info/specification.html#v1">version 1</a></td><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><td class="snsn capitalize white">(<a href="http://lambdadelta.info/static/matita/lambdadelta/">static HELM directory</a>)</td><td class="snss capitalize orange"><a href="http://lambdadelta.info/documentation.html#v1">version 1</a></td><td class="snss capitalize green"><a href="http://lambdadelta.info/implementation.html#lddl">library</a></td><td class="sssn capitalize green">(<a href="http://lambdadelta.info/static/lddl/">static LDDL directory</a>)</td></tr></tbody></table></div><div class="head2dx" id="specifications">Computer-checked formal specifications <img class="icon37" alt="[butterfly]" title="\lambda\delta butterfly" src="http://lambdadelta.info/images/b15.png"/></div><div class="text">
   4       The systems of the λδ family are developed as machine-checked digital specifications,
   5       and are listed in the next table, which includes the major milestones.
   6    </div><div class="text">
   7       The life cycle of a specification consists of four periods.
   8       <span class="emph alpha">Alpha:</span>
   9       the definitions are designed and the major propositions are proved,
  10       then the calculus is announced with a presentation.
  11       <span class="emph beta">Beta:</span>
  12       major changes and additions may occur before the calculus is released on paper.
  13       <span class="emph gamma">Gamma:</span>
  14       subsequent improvements occur until the specification is completed or superseded,
  15       while major changes and additions are announced and reported on paper.
  16       <span class="emph delta">Delta:</span>
  17       after its conclusion, the specification is modified just for maintenance.
  18    </div><div class="text"><table cellpadding="4" cellspacing="0"><tbody><tr><td class="snns top capitalize italic gray">version</td><td class="snnn top capitalize italic gray">name</td><td class="snnn top capitalize italic gray">stage</td><td class="snnn top capitalize italic gray">developed with</td><td class="snnn top capitalize italic gray">started</td><td class="snnn top capitalize italic gray">announced</td><td class="snnn top capitalize italic gray">released</td><td class="snnn top capitalize italic gray">concluded</td><td class="ssnn top capitalize italic gray">references</td></tr><tr><td class="snns top yellow"><a href="http://lambdadelta.info/specification.html#v3">Version 3</a></td><td class="snnn top yellow">"basic_3"</td><td class="snnn top yellow"/><td class="snnn top yellow"/><td class="snnn top yellow"/><td class="snnn top yellow"/><td class="snnn top yellow"/><td class="snnn top yellow"/><td class="ssnn top yellow"><a href="http://lambdadelta.info/documentation#ldJ3a">J3a</a></td></tr><tr><td class="snns top orange"><a href="http://lambdadelta.info/specification.html#v2">Version 2</a></td><td class="snnn top orange">"basic_2"</td><td class="snns top orange">"A2"</td><td class="snnn top orange"><a href="http://matita.cs.unibo.it/">Matita 0.99.3</a></td><td class="snnn top orange">October 2015</td><td class="snnn top orange"/><td class="snnn top orange"/><td class="snnn top orange"/><td class="ssnn top orange"/></tr><tr><td class="nnns top orange"><br/></td><td class="nnnn top orange"><br/></td><td class="snns top orange">"A1"</td><td class="snnn top orange"><a href="http://matita.cs.unibo.it/">Matita 0.99.2</a></td><td class="snnn top orange">April 2011</td><td class="snnn top orange">June 2014</td><td class="snnn top orange">October 2014</td><td class="snnn top orange">August 2015</td><td class="ssnn top orange"><a href="http://lambdadelta.info/documentation#ldV2a">V2a</a><a href="http://lambdadelta.info/documentation#ldR2c">R2c</a></td></tr><tr><td class="snns top orange">Abandoned</td><td class="snnn top orange"/><td class="snnn top orange"/><td class="snnn top orange"><a href="http://coq.inria.fr/">Coq 7.3.1</a></td><td class="snnn top orange">March 2008</td><td class="snnn top orange"/><td class="snnn top orange"/><td class="snnn top orange">February 2011</td><td class="ssnn top orange"/></tr><tr><td class="snss top red"><a href="http://lambdadelta.info/specification.html#v1">Version 1</a></td><td class="snsn top red">"basic_1"</td><td class="snsn top red"/><td class="snsn top red"><a href="http://coq.inria.fr/">Coq 7.3.1</a></td><td class="snsn top red">May 2004</td><td class="snsn top red">December 2005</td><td class="snsn top red">November 2006</td><td class="snsn top red">May 2008</td><td class="sssn top red"><a href="http://lambdadelta.info/documentation#ldV1a">V1a</a><a href="http://lambdadelta.info/documentation#ldJ1a">J1a</a></td></tr></tbody></table></div><div class="text">
  19      Informational pages on the specifications are provided.
  20    </div><ul id="notice1"><li><span class="emph alpha">Notice on displayed numerical acounts:</span>
  21       nodes are counted according to the "intrinsic complexity measure"
  22       [F. Guidi: "Procedural Representation of CIC Proof Terms"
  23       Journal of Automated Reasoning 44(1-2), Springer (February 2010), pp. 53-78].
  24    </li></ul><ul id="notice2"><li><span class="emph alpha">Notice on displayed logical structures:</span>
  25       from the logical standpoint, the source scripts are grouped in "planes"
  26       and these are grouped in "components";
  27       the notation for the relations or functions
  28       introduced in each script, is shown in parentheses (? are placeholders).
  29    </li></ul><!-- VERSION 3 =========================================================== --><div class="head3sn" id="v3"><img class="icon37" alt="[butterfly]" title="\lambda\delta butterfly" src="http://lambdadelta.info/images/b8.png"/> λδ version 3 (proposed)</div><div class="text">
  30       The formal specification of λδ version 3
  31       is forthcoming.
  32    </div><!-- VERSION 2 =========================================================== --><div class="head3sn" id="v2"><img class="icon37" alt="[butterfly]" title="\lambda\delta butterfly" src="http://lambdadelta.info/images/b4.png"/> λδ version 2 (active)</div><div class="text">
  33       The formal specification of λδ version 2
  34       is available in the following formats:
  35    </div><ul id="source2"><li><div class="text"><a href="http://lambdadelta.info/download/lambdadelta_2A1.tar.gz">lambdadelta_2A1 for Matita 0.99.2</a>
  36          (revised <span class="emph gamma">2014-10</span>).
  37          Source scripts.
  38          <a href="http://lambdadelta.info/documentation.html#ldR2c">Documentation (R2c)</a>.
  39       </div><div class="text">
  40          The scripts are grouped in directories, first by part, then by component.
  41       </div><div class="text"><span class="emph alpha">Notice:</span>
  42          the scripts are checked by the latest version of Matita from
  43          <a href="http://matita.cs.unibo.it/download.shtml">HELM Subversion repository</a>
  44          at path &lt;trunk/matita/&gt;.
  45       </div></li></ul><div class="text">
  46       Informational pages on the parts of the specification:
  47       <a href="http://lambdadelta.info/ground_2.html">Background</a>,
  48       <a href="http://lambdadelta.info/basic_2.html">Core</a>,
  49       <a href="http://lambdadelta.info/apps_2.html">Applications</a>.
  50    </div><!-- VERSION 1 =========================================================== --><div class="head3sn" id="v1"><img class="icon37" alt="[butterfly]" title="\lambda\delta butterfly" src="http://lambdadelta.info/images/b6.png"/> λδ version 1 (superseded)</div><div class="text">
  51       The formal specification of λδ version 1
  52       is available in the following formats:
  53    </div><ul id="source1"><li><div class="text"><a href="http://lambdadelta.info/download/lambdadelta_1.tar.gz">lambdadelta_1 for Coq 7.3.1</a>
  54          (revised <span class="emph delta">2015-09</span>).
  55          Source scripts.
  56          <a href="http://lambdadelta.info/documentation.html#ldJ1a">Documentation (J1a)</a>.
  57          <ul><li class=""><span class="emph delta">2015 January 15.</span>
  58             17 new lemmas and former lemma "eq_nat_dec" renamed as "nat_dec_neg".
  59          </li></ul></div><div class="text">
  60          The scripts are grouped in directories, one for each part.
  61       </div></li></ul><ul id="static1"><li><a href="http://lambdadelta.info/static/matita/lambdadelta/">lambdadelta_1 for Matita 0.5</a>
  62       (revised <span class="emph delta">2011-09</span>).
  63       Static HTML pages generated by the <a href="http://helm.cs.unibo.it/">HELM</a> rendering engine.
  64       <ul><li class=""><a href="http://lambdadelta.info/static/matita/lambdadelta/basic_1/pr3/pr3/pr3_confluence.con.html">
  65             Confluence of reduction</a>
  66          (Church-Rosser property).
  67       </li><li class=""><a href="http://lambdadelta.info/static/matita/lambdadelta/basic_1/ty3/props/ty3_correct.con.html">
  68             Correctness of types</a>.
  69       </li><li class=""><a href="http://lambdadelta.info/static/matita/lambdadelta/basic_1/ty3/props/ty3_unique.con.html">
  70             Uniqueness of types up to conversion</a>.
  71       </li><li class=""><a href="http://lambdadelta.info/static/matita/lambdadelta/basic_1/ty3/pr3/ty3_sred_pr3.con.html">
  72             Subject reduction of the type assignment</a>.
  73       </li><li class=""><a href="http://lambdadelta.info/static/matita/lambdadelta/basic_1/ty3/arity_props/ty3_sn3.con.html">
  74             Strong normalization of the typed terms</a>.
  75       </li><li class=""><a href="http://lambdadelta.info/static/matita/lambdadelta/basic_1/ty3/dec/ty3_inference.con.html">
  76             Decidability of the type inference problem</a>.
  77       </li></ul></li></ul><ul id="dynamic1"><li><a href="http://mowgli.cs.unibo.it:58080/apply?keys=RT&amp;xmluri=http://helm.cs.unibo.it/helm//html/folder/index.html&amp;prop.media-type=text/html&amp;param.thmedia-type=text/html&amp;param.thkeys=T1%2CT2%2CL%2CE&amp;param.embedkeys=d_c%2CTC1%2CHC2%2CL&amp;param.thencoding=UTF-8&amp;prop.encoding=UTF-8&amp;prop.doctype-public=-//W3C//DTD%20XHTML%201.0%20Transitional//EN&amp;param.doctype-public=-//W3C//DTD%20XHTML%201.0%20Transitional//EN&amp;param.encoding=UTF-8&amp;param.media-type=text/html&amp;param.keys=d_c%2CC1%2CHC2%2CL&amp;profile=default&amp;param.profile=default&amp;param.CICURI=theory:/matita/lambdadelta/">
  78          lambdadelta_1 for Matita 0.5</a>
  79       (revised <span class="emph delta">2011-09</span>).
  80       <a href="http://helm.cs.unibo.it/">HELM</a> directory.
  81       <span class="emph alpha">Notice: the HELM rendering engine is offline.</span></li></ul><div class="text">
  82       Informational pages on the parts of the specification:
  83       <a href="http://lambdadelta.info/ground_1.html">Background</a>,
  84       <a href="http://lambdadelta.info/basic_1.html">Core</a>.
  85    </div><div class="spacer"><img class="rule" alt="[Spacer]" title="\lambda\delta rainbow rule" src="http://lambdadelta.info/images/rainbow.png"/></div><div class="spacer"><br/></div><div class="spacer"><a href="http://validator.w3.org/check?uri=referer"><img class="w3c" alt="[Valid XHTML 1.1]" title="Valid XHTML 1.1" src="http://www.w3.org/Icons/valid-xhtml11-blue"/></a><a href="http://jigsaw.w3.org/css-validator/check/referer"><img class="w3c" alt="[Valid CSS level 2]" title="Valid CSS level 2" src="http://www.w3.org/Icons/valid-css2-blue"/></a><a href="http://www.w3.org/XML/"><img class="w3c" alt="[Generated from XML via XSL]" title="Generated from XML via XSL" src="http://lambdadelta.info/images/xml_xsl2.png"/></a><a href="http://www.w3.org/Graphics/PNG/"><img class="w3c" alt="[PNG used here]" title="PNG used here" src="http://lambdadelta.info/images/PNGnow2.png"/></a><a href="http://www.anybrowser.org/campaign/"><img class="w3c" alt="[Viewable with any browser]" title="Viewable with any browser" src="http://www.anybrowser.org/campaign/bvgraphics/abtfile.png"/></a></div><div class="spacer"><br/></div><div class="spacer">Last update: Thu, 09 Mar 2017 13:38:16 +0100</div></body></html>