Logical relations

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

  • EnglishLogical relations

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Logical relations are a proof method employed in programming language semantics to show that two denotational semantics are equivalent. To describe the process, let us denote the two semantics by [\![\cdot]\!]_i , where i\in\{1,2\} . For each type A , there is a particular associated relation \sim between [\![A]\!]_1 and [\![A]\!]_2 . This relation is defined such that for each program phrase M , the two denotations are related: [\![M]\!]_1 \sim [\![M]\!]_2 . Another property of this relation is that related denotations for ground types are equivalent in some sense, usually equal. The conclusion is then that both denotations exhibit equivalent behavior on ground terms, hence are equivalent.

Logical relations are a proof method employed in programming language semantics to show that two denotational semantics are equivalent. To describe the process, let us denote the two semantics by [\![\cdot]\!]_i , where i\in\{1,2\} . For each type A , there is a particular associated relation \sim between [\![A]\!]_1 and [\![A]\!]_2 . This relation is defined such that for each program phrase M , the two denotations are related: [\![M]\!]_1 \sim [\![M]\!]_2 . Another property of this relation is that related denotations for ground types are equivalent in some sense, usually equal. The conclusion is then that both denotations exhibit equivalent behavior on ground terms, hence are equivalent.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1227806151 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001227806151 · captured 1717790955.0 · version history

Cite this page as: encyclopegia.org, “Logical relations”, snapshot enwiki-001227806151. https://encyclopegia.org/a/logical-relations

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.