Elementary arithmetic (Q1772782): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q1084099 |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Stanley S. Wainer / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.apal.2004.10.012 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W4205910551 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A new recursion-theoretic characterization of the polytime functions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fragments of Heyting arithmetic / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3800030 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4823142 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4215632 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5613940 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4499084 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fragments of HA based on \(\Sigma_ 1\)-induction / rank | |||
Normal rank |
Latest revision as of 10:22, 10 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Elementary arithmetic |
scientific article |
Statements
Elementary arithmetic (English)
0 references
21 April 2005
0 references
The paper under review is a contribution to the search for syntactically simple theories, without explicitely imposed bounds on quantifiers, whose provably recursive functions form ``more feasible'' complexity classes. A quite different, alternative treatment of Leivant's results is developed. The characterization is extended to the first level of exponential complexity in the hierarchy between Grzegorczyk's \(E^{2}\) and \(E^{3}\). The emphasis is on cut elimination in ``traditional'' theories based on unary numerals, so complexity in the end is measured in terms of the numerical input itself rather than its binary length.
0 references
syntactically simple theories
0 references
provably recursive functions
0 references
complexity classes
0 references
cut elimination
0 references