Non-deterministic data types: Models and implementations
type: Item
instance of: scholarly article
title: Non-deterministic data types: Models and implementations
zbMATH Open document ID: 0564.68013
DOI: 10.1007/BF00263649
author: Tobias Nipkow
published in: Acta Informatica
publication date: 1986-01-01T00:00:00Z
review text: The model theoretic basis for (abstract) data types is generalized from algebras to multi-algebras in order to cope with non-deterministic operations. A programming oriented definition and a model theoretic criterion (called simulation) for implementation of data types are given. To justify the criterion w.r.t. the definition, an abstract framework linking denotational semantics of programming languages and model theory of data types is set up. A set of constraints on a programming language semantics are derived which guarantee that simulation implies implementation. It is argued that any language supporting data abstraction does fulfill these constraints. As an example a simple but expressive language L is defined and it is formally proved that L does conform to these restrictions.
Mathematics Subject Classification ID: 68P05
zbMATH DE Number: 3900136
zbMATH Keywords: multi-algebras
zbMATH Keywords: non-deterministic operations
zbMATH Keywords: implementation of data types
zbMATH Keywords: denotational semantics of programming languages
zbMATH Keywords: model theory of data types
MaRDI profile type: Publication
cites work: Q4746778
cites work: Q4744218
cites work: Q3912057
cites work: Partial abstract types
cites work: Partial algebras-survey of a unifying approach towards a two-valued model theory for partial algebras
cites work: Q3667921
cites work: Q3677164
cites work: Q3662610
cites work: Q4144755
cites work: Q3947104
cites work: Algebraic laws for nondeterminism and concurrency
cites work: Proof of correctness of data representations
cites work: Q3859249
cites work: A calculus of communicating systems
cites work: Q3906397
cites work: Q3907077
cites work: Q3725523
cites work: Q3677153
cites work: Q3666260
cites work: Behavioural correctness of data representations
cites work: Q5537599
Recommended article: Q4858905
Recommended article: Q3816965
Recommended article: Q3341863
Recommended article: Encapsulating non-determinacy in an abstract data type with determinate semantics
Recommended article: On Models of a Nondeterministic Computation
Recommended article: Deterministic and nondeterministic computation, and horn programs, on abstract data types
Recommended article: Non-deterministic structures of computation
Recommended article: Q4992399
Recommended article: Q3323252
description: scientific article; zbMATH DE number 3900136