Parametrization over inductive relations of a bounded number of variables

DOI10.1016/0168-0072(90)90043-2zbMath0705.03019MaRDI 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 classes; complexity measure; number of variables; classes of finite structures admitting unbounded inductions; closure ordinals; halting problems; logic of positive elementary induction; monotone induction; parametrization theorem for fixed point inductions; saturation of models; Spector-Gandy Theorem

Mathematics Subject Classification ID

03D15: Complexity of computation (including implicit computational complexity)

03C50: Models with special properties (saturated, rigid, etc.)

03C57: Computable structure theory, computable model theory

03D75: Abstract and axiomatic computability and recursion theory

Related Items

The dimension of the negation of transitive closure, When is arithmetic possible?, Hierarchies in transitive closure logic, stratified Datalog and infinitary logic, 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