Abstract
We prove the correctness of a formalised realisability interpretation of extensions of first-order theories by inductive and coinductive definitions in an untyped $\lambda$-calculus with fixed-points. We illustrate the use of this interpretation for program extraction by some simple examples in the area of exact real number computation and hint at further non-trivial applications in computable analysis.
BibTeX - Entry
@InProceedings{berger:OASIcs:2009:2258,
author = {Ulrich Berger},
title = {{Realisability and Adequacy for (Co)induction}},
booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {978-3-939897-12-5},
ISSN = {2190-6807},
year = {2009},
volume = {11},
editor = {Andrej Bauer and Peter Hertling and Ker-I Ko},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/2258},
URN = {urn:nbn:de:0030-drops-22581},
doi = {10.4230/OASIcs.CCA.2009.2258},
annote = {Keywords: Constructive Analysis, realisability, program extraction, semantics}
}
|
Keywords: |
|
Constructive Analysis, realisability, program extraction, semantics |
|
Collection: |
|
6th International Conference on Computability and Complexity in Analysis (CCA'09) |
|
Issue Date: |
|
2009 |
|
Date of publication: |
|
25.11.2009 |
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)