Please use this identifier to cite or link to this item: doi:10.22028/D291-25818
Title: Full abstraction for the second order subset of an ALGOL-like language (preliminary report)
Author(s): Sieber, Kurt
Language: English
Year of Publication: 1994
SWD key words: Technische Informatik
Free key words: fully abstract models
DDC notations: 004 Computer science, internet
Publikation type: Report
Abstract: The search for fully abstract models of block structured languages with local variables began in the mid 80s. A series of observationalcongruences in [MeyerS88] revealed the shortcomings of existing models and served as test cases for new ones. The most recently developed models in [OHearnT93, Sieber93] could prove all these test equivalences, but it was not known whether they are fully abstract. In this paper we show that (a slight variant of) the model in [Sieber93] IS fully abstract for the second order subset of an ALGOL-like language (which subsumes all the test equivalences). The general technique for constructing our model is still the same as in [MeyerS88], namely we use `relationally structured locally complete partial orders` with `relation preserving locally continuous functions`. The particular model differs from the one in [MeyerS88] by having the `finest possible relation structure`, an idea which we have developed in [Sieber92] for constructing a fully abstract model for the second order subset of sequential PCF. The full abstraction proof also uses some ideas from [Sieber92], but for its main part we had to develop new techniques in order to cope with the more complicated (in comparison with PCF) setting of an ALGOL-like language.
Link to this record: urn:nbn:de:bsz:291-scidok-3783
Series name: Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes
Series volume: 1994/01
Date of registration: 23-Jun-2005
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
fb14-94-01.pdf254,65 kBAdobe PDFView/Open

Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.