Please use this identifier to cite or link to this item: doi:10.22028/D291-25812
Title: Full abstraction for the second order subset of an ALGOL-like language
Author(s): Sieber, Kurt
Language: English
Year of Publication: 1995
SWD key words: Technische Informatik
Denotationale Semantik
Free key words: denotational semantics
DDC notations: 004 Computer science, internet
Publikation type: Report
Abstract: We present a denotational semantics for an ALGOL-like language ALG, which is fully abstract for the second order subset of ALG. This constitutes the first significant full abstraction result for a block structured language with local variables. As all the published "test equivalences" [13, 8, 23 for Algol-like languages are contained in the second order subset, they can all be validated (easily) in our denotational model. The general technique for our model construction -- namely "relationally structured locally complete partial orders" with "relation preserving locally continuous functions" -- has already been developed in [13], but our particular model differs from the one in [13] in that we now use a larger set of relations. In a certain sense it is the "largest possible" set of relations, an idea which we have successfully used in [32] to obtain a fully abstract model for the second order subset ot the functional language PCF [26]. The overall structure of our full abstraction proof is also taken from [32], but for the single parts of the proof we had to solve considerable new problems which are specific to the imperative (Algol- like) setting.
Link to this record: urn:nbn:de:bsz:291-scidok-3713
Series name: Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes
Series volume: 1995/04
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-95-04.pdf528,14 kBAdobe PDFView/Open

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