# zbMATH — the first resource for mathematics

Upper and lower bounds for first order expressibility. (English) Zbl 0503.68032

##### MSC:
 68Q25 Analysis of algorithms and problem complexity 03D15 Complexity of computation (including implicit computational complexity) 68Q05 Models of computation (Turing machines, etc.) (MSC2010)
Full Text:
##### References:
 [1] Aho, A.; Hopcroft, J.; Ullman, J., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, Mass [2] Blass, A.; Harary, F., Properties of almost all graphs and complexes, J. graph theory, 3, 225-240, (1979) · Zbl 0418.05050 [3] Chandra, S.; Stockmeyer, L., Alternation, (), 98-108 [4] Compton, K., () [5] Ehrenfeucht, A., An application of games to the completeness problem for formalized theories, Fund. math., 49, 129-141, (1961) · Zbl 0096.24303 [6] Enderton, H., A mathematical introduction to logic, (1972), Academic Press New York · Zbl 0298.02002 [7] Fagin, R., Generalized first-order spectra and polynomial-time recognizable sets, (), 43-73 [8] Fagin, R., Probabilities on finite models, J. symbol logic, 41, No. 1, 50-58, (1976) · Zbl 0341.02044 [9] Fischer, M.; Rabin, M., Super-exponential complexity of Presburger arithmetic, (), 27-41 [10] Fraisse, R., Sur LES classifications des systems de relations, Publ. sci. univ. alger, 1, (1954) [11] Hartmanis, J.; Immerman, N.; Mahaney, S., One-way log tape reductions, (), 65-72 [12] Immerman, N., Length of predicate calculus formulas as a new complexity measure, (), 33747 [13] Immerman, N., First order expressibility as a new complexity measure, () [14] Immerman, N., Upper and lower bounds for first order expressibility, (), 74-82 [15] {\scN. Immerman}, Number of quantifiers is better than number of tape cells, J. Comput. System Sci., in press. · Zbl 0486.03019 [16] Kozen, D., On parallelism in Turing machines, (), 89-97 [17] Lynch, J., Almost sure theories, Ann. math. logic, 18, 91-135, (1980) · Zbl 0433.03020 [18] Reif, J., Universal games of incomplete information, (), 288-308 [19] Ruzzo, W., Tree-size bounded alternation, (), 352-359 [20] Ruzzo, W., On uniform circuit complexity, (), 312-318 [21] Savitch, W., Maze recognizing automata and nondeterministic tape complexity, J. comput. system sci., 7, 389-403, (1973) · Zbl 0273.02022 [22] Sudborough, L., On the tape complexity of deterministic CFL’s, J. assoc. comput. Mach., No. 3, 405-414, (1978) · Zbl 0379.68054
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.