Implementation of data types by algebraic methods
type: Item
instance of: scholarly article
title: Implementation of data types by algebraic methods
zbMATH Open document ID: 0537.68026
DOI: 10.1016/0022-0000(83)90045-4
author: Edward K. Blum
author: Francesco Parisi-Presicce
published in: Journal of Computer and System Sciences
publication date: 1983-01-01T00:00:00Z
review text: This paper presents a precise definition of implementation of data types, which are taken to be many-sorted algebras of a given signature (sorts and operations). No particular presentation (e.g. equational) of the data types is assumed but each element of the type is required to be reachable from the given operations. For each operation \(w_ B\) of the \(\Omega\)- algebra B to be implemented, this notion of implementation calls for the construction of an operation \(f_ w\) on the implementing algebra A and the explicit definition of an \(\Omega\)-homomorphism T from F(A) (the \(\Omega\)-subalgebra of A generated by the simulators \(f_ w)\) onto B. The surjectivity of T insures that every element of B can be represented by elements of A. This representation can be multiple as T is not required to be an isomorphism and this implies, in the case of equational presentation of the algebras A and B, that F(A) need not satisfy the axioms defining B. Unlike other approaches, the operations of the two algebras A and B are kept separate and only the operations of A are allowed in the generalized Gödel-Herbrand-Kleene schemes used to define the simulators. Sufficient conditions are given for such a scheme to define a (possibly partial) function using substitution and replacements rules. The notions are illustrated with two examples of implementations of stacks and symbol-tables, dealing with the cases of polynomial and recursively-defined simulators, respectively. Similarities with the approach by H. Ehrig, H.-J. Kreowski and P. Padawitz are analyzed and comparisons with other approaches are mentioned.
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68N01
Mathematics Subject Classification ID: 08A99
Mathematics Subject Classification ID: 03C05
zbMATH DE Number: 3854399
zbMATH Keywords: simulators
zbMATH Keywords: polynomial terms
zbMATH Keywords: recursive schemes
MaRDI profile type: Publication
full work available at URL: 0022-0000(83)90045-4
OpenAlex ID: W2082083998
cites work: The algebraic specification of abstract data types
cites work: Abstract data types and software validation
cites work: Q3923582
cites work: Initial Algebra Semantics and Continuous Algebras
cites work: Relative complexity of algebras
cites work: A generalization of the homomorphism concept
cites work: Q3208066
cites work: Extensions and implementations of abstract data type specifications
cites work: On the Theory of Specification, Implementation, and Parametrization of Abstract Data Types
cites work: Q4160385
cites work: Complexity of algebraic implementations for abstract data types
cites work: Towards a theory of semantics and compilers for programming languages
cites work: Q5572358
cites work: Q5515373
cites work: Q4362900
cites work: Q4164787
cites work: Q4199504
cites work: Q3906461
cites work: Q3965556
cites work: Q4091917
cites work: Q3877027
cites work: Unique fixed points vs. least fixed points
cites work: Recursion-closed algebraic theories
cites work: Program schemes, recursion schemes, and formal languages
cites work: Q4176939
cites work: On some classes of interpretations
cites work: Q5685626
cites work: Q4766569
cites work: IO and OI. II
cites work: A generalized approach to formal languages
cites work: The existence and construction of free iterative theories
cites work: Regular trees and the free iterative theory
cites work: Q3738547
cites work: Inductive methods for proving properties of programs
cites work: Q5812175
cites work: Q5573961
cites work: Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
cites work: Continuous Data Types
description: scientific article; zbMATH DE number 3854399