Parametrization over inductive relations of a bounded number of variables (Q917545)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4156421
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Parametrization over inductive relations of a bounded number of variables |
scientific article; zbMATH DE number 4156421 |
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
0.7291176915168762
0 references
0.7081461548805237
0 references
0.7005055546760559
0 references
