Parametrization over inductive relations of a bounded number of variables (Q917545): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
| Property / author | |||
| Property / author: Gregory Loren McColm / rank | |||
Normal rank | |||
| Property / reviewed by | |||
| Property / reviewed by: Gregory Loren McColm / rank | |||
Normal rank | |||
Revision as of 17:35, 16 February 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Parametrization over inductive relations of a bounded number of variables |
scientific article |
Statements
Parametrization over inductive relations of a bounded number of variables (English)
0 references
1990
0 references
This paper introduces and applies a version of the Parametrization Theorem for (positive) fixedpoint inductions - of a bounded number of variables. First, the ``number of variables'' measure of complexity is proved nontrivial, on classes of finite structures admitting unbounded inductions, and a conjecture on such classes is proposed. The closure ordinals and saturation of models are examined, and the paper concludes with a glance at the Spector-Gandy Theorem.
0 references
monotone induction
0 references
complexity measure
0 references
halting problems
0 references
complexity classes
0 references
logic of positive elementary induction
0 references
parametrization theorem for fixed point inductions
0 references
number of variables
0 references
classes of finite structures admitting unbounded inductions
0 references
closure ordinals
0 references
saturation of models
0 references
Spector-Gandy Theorem
0 references
