Parametrization over inductive relations of a bounded number of variables

DOI10.1016/0168-0072(90)90043-2zbMath0705.03019OpenAlexW2059596002MaRDI QIDQ917545

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

complexity classescomplexity measurenumber of variablesclasses of finite structures admitting unbounded inductionsclosure ordinalshalting problemslogic of positive elementary inductionmonotone inductionparametrization theorem for fixed point inductionssaturation of modelsSpector-Gandy Theorem

Mathematics Subject Classification ID

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

Related Items

Hierarchies in transitive closure logic, stratified Datalog and infinitary logic, The dimension of the negation of transitive closure, When is arithmetic possible?, Unnamed Item

Cites Work

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