Equational derivation vs. computation
type: Item
instance of: scholarly article
title: Equational derivation vs. computation
zbMATH Open document ID: 0811.03032
DOI: 10.1016/0168-0072(94)90068-X
author: W. G. Handley
author: Stanley S. Wainer
published in: Annals of Pure and Applied Logic
publication date: 1994-11-27T00:00:00Z
review text: Subrecursive hierarchy classifications are used to compare the complexities of recursive functions according to (i) their derivations in a version of Kleene's equation calculus, and (ii) their computations by term-rewriting. In each case ordinal bounds are assigned, and it turns out that the respective complexity measures are given by (i) a version of the Fast Growing Hierarchy, and (ii) the Slow Growing Hierarchy. Known comparisons between the two hierarchies then provide ordinal tradeoffs between (i) derivation and (ii) computation. Characterizations of some well-known subrecursive classes are also read off.
Mathematics Subject Classification ID: 03D20
zbMATH DE Number: 695870
zbMATH Keywords: ordinal analysis
zbMATH Keywords: subrecursive hierarchies
zbMATH Keywords: fast growing hierarchy
zbMATH Keywords: slow growing hierarchy
zbMATH Keywords: recursive functions
zbMATH Keywords: Kleene's equation calculus
zbMATH Keywords: computations by term-rewriting
zbMATH Keywords: complexity measures
MaRDI profile type: Publication
cites work: An independence result for \((\Pi^ 1_ 1-CA)+BI\)
cites work: Natural well-orderings
cites work: Q3138831
cites work: Q3893911
cites work: The slow-growing and the Graegorczyk hierarchies
cites work: Q3695270
cites work: What's so special about Kruskal's theorem and the ordinal \(\Gamma{}_ 0\)? A survey of some results in proof theory
cites work: Π12-logic, Part 1: Dilators
cites work: Q5629622
cites work: An Approach to a Unified Theory of Automata
cites work: Q5812175
cites work: Q3241197
cites work: Slow growing versus fast growing
cites work: Q4202962
Wikidata QID: Q126407810
full work available at URL: 0168-0072(94)90068-x
OpenAlex ID: W2022895169
description: scientific article; zbMATH DE number 695870