Partial evaluation and \(\omega\)-completeness of algebraic specifications
type: Item
instance of: scholarly article
title: Partial evaluation and \(\omega\)-completeness of algebraic specifications
zbMATH Open document ID: 0606.68017
DOI: 10.1016/0304-3975(86)90173-8
author: J. Heering
published in: Theoretical Computer Science
publication date: 1986-01-01T00:00:00Z
review text: Suppose P(x,y) is a program with two arguments, whose first argument has a known value c, but whose second argument is not yet known. Partial evaluation of P(c,y) results (or rather: should result) in a specialized residual program \(P_ c(y)\) in which 'as much as possible' has been computed on the basis of c. In the literature on partial evaluation this is often more or less loosely expressed by saying that partial evaluation amounts to 'making maximal use of incomplete information'. In this paper a precise meaning is given to this notion in the context of equational logic, initial algebra specification and term rewriting systems. If maximal propagation of incomplete information is to be achieved within this context, as a first step it is necessary to add equations to the algebraic specification in question until it is \(\omega\)-complete (if ever). The basic properties of \(\omega\)-complete specifications are discussed and some examples of \(\omega\)-complete specifications as well as of specifications that do not have a finite \(\omega\)-complete enrichment are given.
Mathematics Subject Classification ID: 68Q60
zbMATH DE Number: 3980462
zbMATH Keywords: partial evaluation
zbMATH Keywords: equational logic
zbMATH Keywords: initial algebra specification
zbMATH Keywords: term rewriting systems
zbMATH Keywords: incomplete information
MaRDI profile type: Publication
full work available at URL: 0304-3975(86)90173-8
OpenAlex ID: W2037081226
cites work: The lambda calculus, its syntax and semantics
cites work: Q3667921
cites work: Q3853107
cites work: Initial and Final Algebra Semantics for Data Type Specifications: Two Characterization Theorems
cites work: Q4115143
cites work: Mixed computation: potential applications and problems for study
cites work: The Logic of Equality
cites work: Proofs by induction in equational theories with constructors
cites work: Identities in Two-Valued Calculi
cites work: Identities in Finite Algebras
cites work: Q3687683
cites work: Q3347863
cites work: The λ-calculus is ω-incomplete
cites work: Q3853703
description: scientific article; zbMATH DE number 3980462