×

zbMATH — the first resource for mathematics

Complexity classes and theories of finite models. (English) Zbl 0484.03020

MSC:
03D15 Complexity of computation (including implicit computational complexity)
03C13 Model theory of finite structures
03D10 Turing machines and related notions
03B25 Decidability of theories and sets of sentences
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] G. Asser, Das Repräsentantenproblem im Prädikatenkalkül der ersten Stufe mit Identität,Z. Math. Logik Grundlagen Math. 1, 252–263, 1955. · Zbl 0066.25702 · doi:10.1002/malq.19550010403
[2] J. R. Büchi, Weak second-order arithmetic and finite automata,Z. Math. Logik Grundlagen Math. 6, 66–92, 1960. · Zbl 0103.24705 · doi:10.1002/malq.19600060105
[3] S. A. Cook, The complexity of theorem-proving procedures,Proc. Third Annual ACM Symp. on Theory of Computing, 151–158, 1971. · Zbl 0253.68020
[4] S. A. Cook, A hierarchy for nondeterministic time complexity,J. Comp. Sys. Sci. 7, 343–353, 1973. · Zbl 0278.68042 · doi:10.1016/S0022-0000(73)80028-5
[5] A. Ehrenfeucht, An application of games to the completeness problem for formalized theories,Fund. Math. 49, 129–141, 1961. · Zbl 0096.24303
[6] C. C. Elgot, Decision problems of finite-automata design and related arithmetics,Trans. AMS 98, 21–51, 1961. · Zbl 0111.01102 · doi:10.1090/S0002-9947-1961-0139530-9
[7] R. Fagin, Generalized first-order spectra and polynomial-time recognizable sets,Complexity of Computation, R. M. Karp, ed., AMS, Providence, 43–73, 1974. · Zbl 0303.68035
[8] R. Fagin, Monadic generalized spectra,Z. Math. Logic Grundlagen Math. 21, 89–96, 1975. · Zbl 0317.02054 · doi:10.1002/malq.19750210112
[9] M. R. Garey and D. S. Johnson,Computers and Intractability, W. H. Freeman and Co., San Francisco, 1979.
[10] J. E. Hopcroft and J. D. Ullman,Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, Mass., 1979. · Zbl 0426.68001
[11] N. Immerman, Length of predicate calculus formulas as a new complexity measure,Proc. 20th Annual Symp. on Foundations of Computer Science, 337–347, 1979.
[12] N. D. Jones and A. L. Selman, Turing machines and the spectra of first-order formulas with equality,J. Symbolic Logic 39, 139–150, 1974. · Zbl 0288.02021 · doi:10.2307/2272354
[13] R. M. Karp, Reducibility among combinatorial problems,Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, eds., Plenum Press, New York, 85–104, 1972.
[14] H. R. Lewis, Complexity of solvable cases of the decision problem for the predicate calculus,Proc. 19th Annual Symp. on Foundations of Computer Science, 35–47, 1978.
[15] J. F. Lynch, Almost sure theories,Ann. Math. Logic 18, 91–135, 1980. · Zbl 0433.03020 · doi:10.1016/0003-4843(80)90014-5
[16] J. F. Lynch, On sets of relations definable by addition, to appear inJ. Symbolic Logic. · Zbl 0504.03013
[17] J. D. Monk,Mathematical Logic, Springer-Verlag, New York, 1976.
[18] R. W. Ritchie, Classes of predictably computable functions,Trans. AMS 106, 139–173, 1963. · Zbl 0107.01001 · doi:10.1090/S0002-9947-1963-0158822-2
[19] H. Scholz, Problem # 1,J. Symbolic Logic 17, 160, 1952.
[20] L. J. Stockmeyer, The polynomial-time hierarchy,Theoretical Computer Science 3, 1–22, 1977. · Zbl 0353.02024 · doi:10.1016/0304-3975(76)90061-X
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.