Parametrization over inductive relations of a bounded number of variables

DOI10.1016/0168-0072(90)90043-2MaRDI QIDQ917545zbMATH OpenOpenAlexFDO

Authors Gregory Loren McColm

Publication date 1990

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0168-0072(90)90043-2

zbMATH Keywords

classes of finite structures admitting unbounded inductionsclosure ordinalscomplexity classescomplexity measurehalting problemslogic of positive elementary inductionmonotone inductionnumber of variablesparametrization theorem for fixed point inductionssaturation of modelsSpector-Gandy Theorem

Mathematics Subject Classification ID

Models with special properties (saturated, rigid, etc.) (03C50) Computable structure theory, computable model theory (03C57) Complexity of computation (including implicit computational complexity) (03D15) Abstract and axiomatic computability and recursion theory (03D75)

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.

Recommendations

• On parameter free induction schemas
• Inductive definitions over finite structures
• scientific article; zbMATH DE number 4075046
• Parameter-Free Universal Induction
• scientific article; zbMATH DE number 1088194

Cites work

• A Machine-Independent Theory of the Complexity of Recursive Functions
• A Note on Function Quantification
• Abstract First Order Computability. I
• An application of games to the completeness problem for formalized theories
• Computational Complexity and the Existence of Complexity Gaps
• Elementary induction on abstract structures
• Hierarchies of number-theoretic predicates
• scientific article; zbMATH DE number 3885853 (Why is no real title available?)
• scientific article; zbMATH DE number 3966062 (Why is no real title available?)
• scientific article; zbMATH DE number 3250555 (Why is no real title available?)
• scientific article; zbMATH DE number 3329887 (Why is no real title available?)
• Hyperarithmetical quantifiers
• Model theory
• On Moschovakis closure ordinals
• On the Computational Complexity of Algorithms
• On the Forms of the Predicates in the Theory of Constructive Ordinals (Second Paper)
• Relational queries computable in polynomial time
• Some applications of the notions of forcing and generic sets
• Upper and lower bounds for first order expressibility

Cited in

(4)

• Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
• scientific article; zbMATH DE number 1286037 (Why is no real title available?)
• The dimension of the negation of transitive closure
• When is arithmetic possible?

This page was built for publication: Parametrization over inductive relations of a bounded number of variables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q917545)