Parametrization over inductive relations of a bounded number of variables (Q917545)
From MaRDI portal
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
