Equational derivation vs. computation (Q1338198): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / cites work | |||
Property / cites work: An independence result for \((\Pi^ 1_ 1-CA)+BI\) / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Natural well-orderings / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3138831 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3893911 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The slow-growing and the Graegorczyk hierarchies / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3695270 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: What's so special about Kruskal's theorem and the ordinal \(\Gamma{}_ 0\)? A survey of some results in proof theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Π12-logic, Part 1: Dilators / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5629622 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An Approach to a Unified Theory of Automata / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5812175 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3241197 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Slow growing versus fast growing / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4202962 / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q126407810 / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0168-0072(94)90068-x / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2022895169 / rank | |||
Normal rank |
Latest revision as of 09:29, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Equational derivation vs. computation |
scientific article |
Statements
Equational derivation vs. computation (English)
0 references
27 November 1994
0 references
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.
0 references
ordinal analysis
0 references
subrecursive hierarchies
0 references
fast growing hierarchy
0 references
slow growing hierarchy
0 references
recursive functions
0 references
Kleene's equation calculus
0 references
computations by term-rewriting
0 references
complexity measures
0 references
0 references