×

On the variable hierarchy of first-order spectra. (English) Zbl 1354.03040


MSC:

03C13 Model theory of finite structures
03C07 Basic properties of first-order languages and structures
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] S. Arora and B. Barak. 2009. Computational Complexity: A Modern Approach. Cambridge University Press. · Zbl 1193.68112 · doi:10.1017/CBO9780511804090
[2] G. Asser. 1955. Das repräsentenproblem in prädikatenkalkül der ersten Stufe mit identität. Zeitschrift für mathematische Logik und Grundlagen der Mathematik 1, 252–263.
[3] J. Chen, X. Huang, I. A. Kanj, and G. Xia. 2004. Linear FPT reductions and computational lower bounds. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing. 212–221. · Zbl 1192.68313 · doi:10.1145/1007352.1007391
[4] J. Chen, X. Huang, I. A. Kanj, and G. Xia. 2006. Strong computational lower bounds via parameterized complexity. Journal of Computer and System Sciences 72, 8, 1346–1367. · Zbl 1119.68092 · doi:10.1016/j.jcss.2006.04.007
[5] S. Cook. 1973. A hierarchy for nondeterministic time complexity. Journal of Computer and System Sciences 7, 4, 343–353. · Zbl 0278.68042 · doi:10.1016/S0022-0000(73)80028-5
[6] A. Durand, N. D. Jones, J. A. Makowsky, and M. More. 2012. Fifty years of the spectrum problem: Survey and new results. Bulletin of Symbolic Logic 18, 4, 505–553. · Zbl 1309.03014 · doi:10.2178/bsl.1804020
[7] R. Fagin. 1973. Contributions to the Model Theory of Finite Structures. Ph.D. Dissertation. University of California, Berkeley.
[8] R. Fagin. 1974. Generalized first-order spectra and polynomial-time recognizable sets. In Proceedings of SIAM-AMS Complexity of Computation. 27–41. · Zbl 0303.68035
[9] R. Fagin. 1975. A spectrum hierarchy. Zeitschrift für mathematische Logik und Grundlagen der Mathematik 21, 123–134.
[10] R. Fagin. 1993. Finite-model theory: A personal perspective. Theoretical Computer Science 116, 1–2, 3–31. · Zbl 0788.03037 · doi:10.1016/0304-3975(93)90218-I
[11] E. Grandjean. 1984. The spectra of first-order sentences and computational complexity. SIAM Journal on Computing 13, 2, 356–373. · Zbl 0535.03014 · doi:10.1137/0213025
[12] E. Grandjean. 1985. Universal quantifiers and time complexity of random access machines. Mathematical Systems Theory 18, 2, 171–187. · Zbl 0578.03022 · doi:10.1007/BF01699468
[13] E. Grandjean. 1990. First-order spectra with one variable. Journal of Computer and System Sciences 40, 2, 136–153. · Zbl 0694.68034 · doi:10.1016/0022-0000(90)90009-A
[14] E. Grandjean and F. Olive. 2004. Graph properties checkable in linear time in the number of vertices. Journal of Computer and System Sciences 68, 3, 546–597. · Zbl 1069.68079 · doi:10.1016/j.jcss.2003.09.002
[15] N. Immerman. 1999. Descriptive Complexity. Springer. · Zbl 0918.68031 · doi:10.1007/978-1-4612-0539-5
[16] R. Impagliazzo and R. Paturi. 1999. Complexity of k-SAT. In Proceedings of the IEEE Conference on Computational Complexity. · Zbl 0990.68079 · doi:10.1109/CCC.1999.766282
[17] N. Jones and A. Selman. 1974. Turing machines and the spectra of first-order formulas. Journal of Symbolic Logic 39, 139–150. · Zbl 0288.02021 · doi:10.2307/2272354
[18] E. Kopczyński and T. Tan. 2015. Regular graphs and the spectra of two-variable logic with counting. To appear in SIAM Journal on Computing.
[19] J. Lynch. 1982. Complexity classes and theories of finite models. Mathematical Systems Theory 15, 2, 127–144. · Zbl 0484.03020
[20] C. H. Papadimitriou. 1994. Computational Complexity. Addison-Wesley. · Zbl 0833.68049
[21] P. Pudlák. 1975. The observational predicate calculus and complexity of computations. Commentationes Mathematicae Universitatis Carolinae 16, 395–398.
[22] H. Scholz. 1952. Ein ungelöstes problem in der symbolischen logic. Journal of Symbolic Logic 17, 160.
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.