Parametrization over inductive relations of a bounded number of variables
type: Item
instance of: scholarly article
title: Parametrization over inductive relations of a bounded number of variables
zbMATH Open document ID: 0705.03019
DOI: 10.1016/0168-0072(90)90043-2
published in: Annals of Pure and Applied Logic
publication date: 1990-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03C57
Mathematics Subject Classification ID: 03D75
Mathematics Subject Classification ID: 03C50
zbMATH DE Number: 4156421
zbMATH Keywords: monotone induction
zbMATH Keywords: complexity measure
zbMATH Keywords: halting problems
zbMATH Keywords: complexity classes
zbMATH Keywords: logic of positive elementary induction
zbMATH Keywords: parametrization theorem for fixed point inductions
zbMATH Keywords: number of variables
zbMATH Keywords: classes of finite structures admitting unbounded inductions
zbMATH Keywords: closure ordinals
zbMATH Keywords: saturation of models
zbMATH Keywords: Spector-Gandy Theorem
author: Gregory Loren McColm
reviewed by: Gregory Loren McColm
MaRDI profile type: Publication
full work available at URL: 0168-0072(90)90043-2
OpenAlex ID: W2059596002
cites work: A Note on Function Quantification
cites work: On Moschovakis closure ordinals
cites work: A Machine-Independent Theory of the Complexity of Recursive Functions
cites work: Computational Complexity and the Existence of Complexity Gaps
cites work: Model theory
cites work: Q3220545
cites work: An application of games to the completeness problem for formalized theories
cites work: Some applications of the notions of forcing and generic sets
cites work: Q5537368
cites work: On the Computational Complexity of Algorithms
cites work: Upper and lower bounds for first order expressibility
cites work: Relational queries computable in polynomial time
cites work: On the Forms of the Predicates in the Theory of Constructive Ordinals (Second Paper)
cites work: Hierarchies of number-theoretic predicates
cites work: Q5607980
cites work: Abstract First Order Computability. I
cites work: Elementary induction on abstract structures
cites work: Q3734395
cites work: Hyperarithmetical quantifiers
description: scientific article; zbMATH DE number 4156421