No Cover Image

Journal article 1597 views

A domain model characterising strong normalisation

Ulrich Berger

Annals of Pure and Applied Logic, Volume: 156, Issue: 1, Pages: 39 - 50

Swansea University Author: Ulrich Berger

Full text not available from this repository: check for access using links below.

Check full text

DOI (Published version): 10.1016/j.apal.2008.06.005

Abstract

Building on previous work by Coquand and Spiwack we construct a strict domain-theoretic model for the untyped lambda-calculus with pattern matching and term rewriting which has the property that a term is strongly normalising if its value is not bottom. There are no disjointness or confluence condit...

Full description

Published in: Annals of Pure and Applied Logic
ISSN: 0168-0072
Published: 2008
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa128
first_indexed 2013-07-23T11:46:47Z
last_indexed 2018-02-09T04:26:57Z
id cronfa128
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2015-10-14T15:41:25.6862278</datestamp><bib-version>v2</bib-version><id>128</id><entry>2012-02-23</entry><title>A domain model characterising strong normalisation</title><swanseaauthors><author><sid>61199ae25042a5e629c5398c4a40a4f5</sid><firstname>Ulrich</firstname><surname>Berger</surname><name>Ulrich Berger</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2012-02-23</date><abstract>Building on previous work by Coquand and Spiwack we construct a strict domain-theoretic model for the untyped lambda-calculus with pattern matching and term rewriting which has the property that a term is strongly normalising if its value is not bottom. There are no disjointness or confluence conditions imposed on the rewrite rules, and under a mild but necessary condition completeness of the method is proven. As an application, we prove strong normalisation for barrecursion in higher types combined with polymorphism and non-deterministic choice.</abstract><type>Journal Article</type><journal>Annals of Pure and Applied Logic</journal><volume>156</volume><journalNumber>1</journalNumber><paginationStart>39</paginationStart><paginationEnd>50</paginationEnd><publisher/><issnPrint>0168-0072</issnPrint><issnElectronic/><keywords>lambda-calculus, term rewriting, normalisation, domain theory</keywords><publishedDay>26</publishedDay><publishedMonth>7</publishedMonth><publishedYear>2008</publishedYear><publishedDate>2008-07-26</publishedDate><doi>10.1016/j.apal.2008.06.005</doi><url/><notes/><college>COLLEGE NANME</college><CollegeCode>COLLEGE CODE</CollegeCode><institution>Swansea University</institution><apcterm/><lastEdited>2015-10-14T15:41:25.6862278</lastEdited><Created>2012-02-23T17:01:55.0000000</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>Ulrich</firstname><surname>Berger</surname><order>1</order></author></authors><documents/><OutputDurs/></rfc1807>
spelling 2015-10-14T15:41:25.6862278 v2 128 2012-02-23 A domain model characterising strong normalisation 61199ae25042a5e629c5398c4a40a4f5 Ulrich Berger Ulrich Berger true false 2012-02-23 Building on previous work by Coquand and Spiwack we construct a strict domain-theoretic model for the untyped lambda-calculus with pattern matching and term rewriting which has the property that a term is strongly normalising if its value is not bottom. There are no disjointness or confluence conditions imposed on the rewrite rules, and under a mild but necessary condition completeness of the method is proven. As an application, we prove strong normalisation for barrecursion in higher types combined with polymorphism and non-deterministic choice. Journal Article Annals of Pure and Applied Logic 156 1 39 50 0168-0072 lambda-calculus, term rewriting, normalisation, domain theory 26 7 2008 2008-07-26 10.1016/j.apal.2008.06.005 COLLEGE NANME COLLEGE CODE Swansea University 2015-10-14T15:41:25.6862278 2012-02-23T17:01:55.0000000 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Ulrich Berger 1
title A domain model characterising strong normalisation
spellingShingle A domain model characterising strong normalisation
Ulrich Berger
title_short A domain model characterising strong normalisation
title_full A domain model characterising strong normalisation
title_fullStr A domain model characterising strong normalisation
title_full_unstemmed A domain model characterising strong normalisation
title_sort A domain model characterising strong normalisation
author_id_str_mv 61199ae25042a5e629c5398c4a40a4f5
author_id_fullname_str_mv 61199ae25042a5e629c5398c4a40a4f5_***_Ulrich Berger
author Ulrich Berger
author2 Ulrich Berger
format Journal article
container_title Annals of Pure and Applied Logic
container_volume 156
container_issue 1
container_start_page 39
publishDate 2008
institution Swansea University
issn 0168-0072
doi_str_mv 10.1016/j.apal.2008.06.005
college_str Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
document_store_str 0
active_str 0
description Building on previous work by Coquand and Spiwack we construct a strict domain-theoretic model for the untyped lambda-calculus with pattern matching and term rewriting which has the property that a term is strongly normalising if its value is not bottom. There are no disjointness or confluence conditions imposed on the rewrite rules, and under a mild but necessary condition completeness of the method is proven. As an application, we prove strong normalisation for barrecursion in higher types combined with polymorphism and non-deterministic choice.
published_date 2008-07-26T03:02:35Z
_version_ 1851360496032153600
score 11.089572

Similar Items