A recursive second order initial algebra specification of primitive recursion
type: Item
instance of: scholarly article
title: A recursive second order initial algebra specification of primitive recursion
zbMATH Open document ID: 0818.68113
DOI: 10.1007/BF01178510
author: Karl Meinke
published in: Acta Informatica
publication date: 1994-11-23T00:00:00Z
review text: Theoretical results on the scope and limits of first order algebraic specifications can be used to show that certain natural algebras have no recursively enumerable equational specification under first order initial algebra semantics. A well known example is the algebra \({\mathcal P} {\mathcal R}\) of primitive recursive functions over the natural numbers. In this paper we show that \({\mathcal P} {\mathcal R}\) has a recursive equational specification under second order initial algebra semantics. It follows that higher order initial algebra specifications are strictly more powerful than first order initial algebra specifications.
Mathematics Subject Classification ID: 68Q65
Mathematics Subject Classification ID: 08A70
zbMATH DE Number: 694998
zbMATH Keywords: algebraic specifications
MaRDI profile type: Publication
cites work: Q3854601
cites work: Initial and Final Algebra Semantics for Data Type Specifications: Two Characterization Theorems
cites work: Algebraic specifications of computable and semicomputable data types
cites work: Q3687683
cites work: CONSTRUCTIVE ALGEBRAS I
cites work: Universal algebra in higher types
cites work: Q3809236
cites work: Computable Algebra, General Theory and Theory of Computable Fields
cites work: Q4385539
Recommended article: On the Algebraic Structure of Primitive Recursive Functions
Recommended article: Q2778868
Recommended article: Primitive program algebras. II
Recommended article: Q3677754
Recommended article: Towards an algebraic theory of recursion
Recommended article: Primitive recursion for higher-order abstract syntax
Recommended article: Q3024905
Recommended article: Q4331776
Recommended article: A Proof-Theoretic Account of Primitive Recursion and Primitive Iteration
Recommended article: Classes of algebras of primitive recursive functions
description: scientific article; zbMATH DE number 694998