×

Parametrization over inductive relations of a bounded number of variables. (English) Zbl 0705.03019

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.
Reviewer: G.L.McColm

MSC:

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

References:

[1] Addison, J. W.; Kleene, S. C., A note on function quantification, Proc. AMS, 8, 1002-1006 (1957) · Zbl 0084.24901
[2] Aho, A.; Ullman, J., Universality of data retrieval languages, Proc. 6th ACM Symposium of Programming Languages, 110-120 (1979)
[3] Barwise, J., On Moschovakis closure ordinals, J. Symbolic Logic, 42, 2, 289-296 (1977) · Zbl 0367.02021
[4] Blum, M., A machine-independent theory of the complexity of recursive functions, J. ACM, 14, 2, 322-336 (1967) · Zbl 0155.01503
[5] Borodin, A., Computational complexity and the existence of complexity gaps, J. ACM, 19, 1, 158-174 (1972) · Zbl 0261.68024
[6] Chang, C.; Keisler, H. J., Model Theory (1973), North-Holland: North-Holland Amsterdam · Zbl 0276.02032
[7] Ebbinghaus, H. D.; Flum, J.; Thomas, W., Mathematical Logic (1984), Springer: Springer Berlin · Zbl 0556.03001
[8] Ehrenfeucht, A., An application of games to the completeness problem for formalized theories, Fund. Math., 49, 129-141 (1961) · Zbl 0096.24303
[9] Fagin, R., Generalized first-order spectra and polynomial-time recognizable sets, (Karp, R., SIAM-AMS Proc., 7 (1974)), 27-41, Complexity of Computation
[10] Feferman, S., Some applications of forcing and generic sets, Fund. Math., 56, 325-345 (1965) · Zbl 0129.26401
[11] Fraisse, R., Sur les classifications des systémes de relations, No. I (1954), Publications Sci. de I’Université D’Algér
[12] Gandy, R., Proof of Mostowski’s conjecture, Bull. Acad. Polon. Sci. Ser. Sci. Math. Astron. Phys., 8, 571-575 (1960) · Zbl 0156.01101
[13] Gandy, R., (General recursive functionals of finite type and hierarchies of functionals, 35 (1967), Ann. Fac. Sci. Univ. Clermont-Ferrand), 5-24
[14] Hartmanis, J.; Stearns, R. E., On the computational complexity of algorithms, Trans. AMS, 117, 285-306 (1965) · Zbl 0131.15404
[15] Immerman, N., Upper and lower bounds for first-order expressibility, J. Comp. Syst. Sci., 25, 76-98 (1982) · Zbl 0503.68032
[16] Immerman, N., Relational queries computable in polynomial time, Information and Control, 68, 86-104 (1986) · Zbl 0612.68086
[17] Immerman, N.; Kozen, D., Definability with bounded number of bound variables, (IEEE) Logic in Computer Science (1987)
[18] Kechris, A.; Moschovakis, Y., Recursion in higher types, (Barwise, J., Handbook of Mathematical Logic (1977), North-Holland: North-Holland Amsterdam), 681-738
[19] Kleene, S., On the forms of the predicates in the theory of constructive ordinals, Amer. J. Math., 77, 405-428 (1955) · Zbl 0067.25203
[20] Kleene, S., Hierarchies of number-theoretic predicates, Bull. AMS, 61, 193-213 (1955) · Zbl 0066.25901
[21] Keisler, H., Finite approximations of infinitely long formulas, (Addison, J., The Theory of Models (1965), North-Holland: North-Holland Amsterdam), 158-169 · Zbl 0207.29802
[22] McColm, G., Simple and simultaneous recursive fixed points, PhD Thesis (1986), UCLA
[23] G. McColm, When is arithmetic possible? Ann. Pure Appl. Logic, to appear.; G. McColm, When is arithmetic possible? Ann. Pure Appl. Logic, to appear.
[24] Moschovakis, Y., Abstract firts order computability II, Trans. AMS, 138, 465-504 (1969) · Zbl 0218.02038
[25] Moschovakis, Y., Elementary Induction on Abstract Structures (1974), North-Holland: North-Holland Amsterdam · Zbl 0307.02003
[26] Y. Moschovakis, Abstract recursion as a foundation for the theory of algorithms, in: M. Richter , eds., Computation and Proof Theory, Lecture Notes in Math. 1104 (Springer, Berlin, 289-364).; Y. Moschovakis, Abstract recursion as a foundation for the theory of algorithms, in: M. Richter , eds., Computation and Proof Theory, Lecture Notes in Math. 1104 (Springer, Berlin, 289-364).
[27] Sepctor, C., Hyperarithmetical quantifiers, Fund. Math., 48, 313-320 (1960) · Zbl 0098.24301
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.