License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.10351.6
URN: urn:nbn:de:0030-drops-28067
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2806/
Go to the corresponding Portal

Pitts, Andrew M.

Step-Indexed Biorthogonality: a Tutorial Example

pdf-format:
10351.PittsAndrew.Paper.2806.pdf (0.5 MB)

Abstract

The purpose of this note is to illustrate the use of step-indexing combined with biorthogonality to construct syntactical logical relations. It walks through the details of a syntactically simple, yet non-trivial example: a proof of the "CIU Theorem'' for contextual equivalence in the untyped call-by-value $lambda$-calculus with recursively defined functions.

BibTeX - Entry

@InProceedings{pitts:DagSemProc.10351.6,
  author =	{Pitts, Andrew M.},
  title =	{{Step-Indexed Biorthogonality: a Tutorial Example}},
  booktitle =	{Modelling, Controlling and Reasoning About State},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10351},
  editor =	{Amal Ahmed and Nick Benton and Lars Birkedal and Martin Hofmann},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2010/2806},
  URN =		{urn:nbn:de:0030-drops-28067},
  doi =		{10.4230/DagSemProc.10351.6},
  annote =	{Keywords: Biorthogonality, logical relations, operational semantics, step-indexing}
}

Keywords: Biorthogonality, logical relations, operational semantics, step-indexing
Collection: 10351 - Modelling, Controlling and Reasoning About State
Issue Date: 2010
Date of publication: 04.11.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI