Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-05T08:42:29.220Z Has data issue: false hasContentIssue false
  • English
  • Français

Fifty years of the spectrum problem: survey and new results

Published online by Cambridge University Press:  05 September 2014

Arnaud Durand ,
Neil D. Jones ,
Johann A. Makowsky  and
Malika More
Arnaud Durand
Affiliation:
IMJ – Projet Logique, Université Paris Diderot, Paris 7, France E-mail: [email protected]
Neil D. Jones
Affiliation:
DIKU, University of Copenhagen, Denmark E-mail: [email protected]
Johann A. Makowsky
Affiliation:
Faculty of Computer Science, Technion, Haifa, Israel E-mail: [email protected]
Malika More
Affiliation:
Univ Clermont 1, Laic, France E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In 1952, Heinrich Scholz published a question in The Journal of Symbolic Logic asking for a characterization of spectra, i.e., sets of natural numbers that are the cardinalities of finite models of first order sentences. Günter Asser in turn asked whether the complement of a spectrum is always a spectrum. These innocent questions turned out to be seminal for the development of finite model theory and descriptive complexity. In this paper we survey developments over the last 50-odd years pertaining to the spectrum problem. Our presentation follows conceptual developments rather than the chronological order. Originally a number theoretic problem, it has been approached by means of recursion theory, resource bounded complexity theory, classification by complexity of the defining sentences, and finally by means of structural graph theory. Although Scholz' question was answered in various ways, Asser's question remains open.

Type
Articles
Information
Bulletin of Symbolic Logic , Volume 18 , Issue 4 , December 2012 , pp. 505 - 553
Copyright
Copyright © Association for Symbolic Logic 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Adamczewski, B. and Bugeaud, Y., On the complexity of algebraic numbers I: Expansion in integer bases, Annals of Mathematics, vol. 165 (2007), pp. 547–565.Google Scholar
[2] Ajtai, M. and Fagin, R., Reachability is harder for directed than for undirected finite graphs, The Journal of Symbolic Logic, vol. 55 (1990), no. 1, pp. 113–150.Google Scholar
[3] Allender, E. and Gore, V., Rudimentary reductions revisited, Information Processing Letters, vol. 40 (1991), no. 2, pp. 89–95.Google Scholar
[4] Arnborg, S., Corneil, D. G., and Proskurowski, A., Complexity of finding embedding in a k–tree, SIAM. Journal on Algebraic Discrete Methods, vol. 8 (1987), pp. 277–284.Google Scholar
[5] Ash, C. J., A conjecture concerning the spectrum of a sentence, Mathematical Logic Quartely, vol. 40 (1994), pp. 393–397.Google Scholar
[6] Asser, G., Das Repräsentenproblem in Prädikatenkalkül der ersten Stufe mit Identität, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 1 (1955), pp. 252–263.Google Scholar
[7] Bennett, J. H., On spectra, Ph.D. thesis, Princeton University, Princeton, New Jersey, USA, 1962.Google Scholar
[8] Bodlaender, H., A tourist guide through tree width, Acta Cybernetica, vol. 11 (1993), pp. 1–23.Google Scholar
[9] Bodlaender, H., A partial k-arboretum of graphs with bounded tree width (tutorial), Theoretical Computer Science, vol. 208 (1998), pp. 1–45.Google Scholar
[10] Börger, E., Spektralproblem and completeness of logical decision problems, Logic and machines: Decision problems and complexity, proceedings of the symposium “Rekursive Kombinatorik” (Börger, E., Hasenjaeger, G., and Rödding, D., editors), Lecture Notes in Computer Science, vol. 171, Springer, 1984, pp. 333–356.Google Scholar
[11] Calude, C., Super-exponentials nonprimitive recursive, but rudimentary., Information Processing Letters, vol. 25 (1987), no. 5, pp. 311–316.Google Scholar
[12] Chateau, A., Utilisation des destinées pour la décision et sa complexité dans le cas de formules à profondeur de quantification bornée sur des structures logiques finies et infinies, Ph.D. thesis, Université d'Auvergne, 2003.Google Scholar
[13] Chateau, A. and More, M., The ultraweak Ash conjecture and some particular cases, Mathematical Logic Quarterly, vol. 52 (2006), no. 1, pp. 4–13.Google Scholar
[14] Chen, Q., Su, K., and Zheng, X., Primitive recursive real numbers, Mathematical Logic Quarterly, vol. 53 (2007), no. 4–5, pp. 365–380.Google Scholar
[15] Chen, Q., Primitive recursiveness of real numbers under different representations, Electronic Notes in Theoretical Computer Science, vol. 167 (2007), pp. 303–324.Google Scholar
[16] Christen, C. A., Spektralproblem und Komplexitätstheorie, Ph.D. thesis, Eidgenössische Technische Hochschule (ETH), Zürich, Switzerland, 1974.Google Scholar
[17] Christen, C. A., Spektralproblem und Komplexitätstheorie, Komplexität von Entscheidungsproblemen: ein Seminar (Specker, E. and Strassen, V., editors), Lecture Notes in Computer Science, vol. 43, Springer, 1976, pp. 102–126.Google Scholar
[18] Cobham, A., On the Hartmanis–Stearns problem for a class of tag machine, IEEE Conference Record of 1968 Ninth Annual Symposium on Switching and Automata Theory, Schenectady, New York, IEEE Computer Society Press, 1968, pp. 51–60.Google Scholar
[19] Compton, K. J. and Henson, C. W., A uniform method for proving lower bounds on the computational complexity of logical theories, Annals of Pure and Applied Logic, vol. 48 (1990), pp. 1–79.Google Scholar
[20] Courcelle, B., The monadic second–order logic of graphs I: Recognizable sets of finite graphs, Information and Computation, vol. 85 (1990), pp. 12–75.Google Scholar
[21] Courcelle, B., Structural properties of context-free sets of graphs generated by vertex replacement. Information and Computation, vol. 116 (1995), pp. 275–293.Google Scholar
[22] Courcelle, B., Engelfriet, J., and Rozenberg, G., Handle-rewriting hypergraph grammars, Journal of Computer and System Sciences, vol. 46 (1993), pp. 218–270.CrossRefGoogle Scholar
[23] Courcelle, B. and Olariu, S., Upper bounds to the clique–width of graphs, Discrete Applied Mathematics, vol. 101 (2000), pp. 77–114.Google Scholar
[24] Csillag, P., Eine Bemerkung zur Auflösung der eingeschachtelten Rekursion, Acta Universitatis Szegediensis, Acta Scientiarum Mathematicarum, vol. 11 (1947), pp. 169–173 (German).Google Scholar
[25] Curry, H. B., Review of[85], MR0086766 (19,240c).Google Scholar
[26] Dahlhaus, E., Combinatorial and logical properties of reductions to some complete problems in NP and NL, Ph.D. thesis, Technische Universität Berlin, Germany, 1982.Google Scholar
[27] Diestel, R., Graph theory, Graduate Texts in Mathematics, Springer, 1996.Google Scholar
[28] Durand, A., Hiérarchies de définissabilité logique au second ordre, Ph.D. thesis, Université de Caen, Caen, France, 1996.Google Scholar
[29] Durand, A., Fagin, R., and Loescher, B., Spectra with only unary function symbols, Computer Science Logic, CSL'97 (Nielsen, M. and Thomas, W., editors), Lecture Notes in Computer Science, vol. 1414, Springer, 1998, pp. 189–202.Google Scholar
[30] Durand, A. and Ranaivoson, S., First-order spectra with one binary predicate, Theoretical Computer Science, vol. 160 (1996), no. 1&2, pp. 189–202.Google Scholar
[31] Ebbinghaus, H.-D. and Flum, J., Finite model theory, Perspectives in Mathematical Logic, Springer, 1995.Google Scholar
[32] Ehrenfeucht, A., An application of games to the completeness problem for formalized theories, Fundamenta Mathematicae, vol. 49 (1961), pp. 129–141.Google Scholar
[33] Ershov, Y., Lavrov, I., Taimanov, A., and Taitslin, M., Elementary theories, Russian Mathematical Surveys, vol. 20 (1965), pp. 35–105.Google Scholar
[34] Esbelin, H.-A. and More, M., Rudimentary relations and primitive recursion: a toolbox, Theoretical Computer Science, vol. 193 (1998), no. 1–2, pp. 129–148.Google Scholar
[35] Fagin, R., Contributions to the model theory of finite structures, Ph.D. thesis. University of California, Berkeley, California, 1973.Google Scholar
[36] Fagin, R., Generalized first-order spectra and polynomial-time recognizable sets. Complexity of computation (Proceedings of the SIAM–AMS Symposium on Applied Mathematics, New York, 1973) (Karp, R. M., editor), vol. 7, American Mathematical Society, Providence, RI, 1974, pp. 43–73.Google Scholar
[37] Fagin, R., Monadic generalized spectra, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 21 (1975), pp. 89–96.Google Scholar
[38] Fagin, R., A spectrum hierarchy, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 21 (1975), pp. 123–134.Google Scholar
[39] Fagin, R., Finite-model theory - a personal perspective, Theoretical Computer Science, (1993), no. 116, pp. 3–31.Google Scholar
[40] Feder, T. and Vardi, M., The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory, SIAM Journal on Computing, vol. 28 (1999), pp. 57–104.Google Scholar
[41] Fischer, E. and Makowsky, J. A., On spectra of sentences of monadic second order logic with counting, The Journal of Symbolic Logic, vol. 69 (2004), no. 3, pp. 617–640.Google Scholar
[42] Fraïssé, R., Sur quelques classifications des systèmes de relations, Publications Scientifiques de l'Université d'Alger, Série A, vol. 1 (1954), pp. 35–182.Google Scholar
[43] Friedman, H., Primitive recursive reals, http://www.es.nyu.edu/pipermail/fom/2006–April/010452.html, April 2006.Google Scholar
[44] Gécseg, F. and Steinby, M., Tree languages, Handbook of formal languages, vol. 3: Beyond words (Rozenberg, G. and Salomaa, A., editors), Springer Verlag, Berlin, 1997, pp. 1–68.Google Scholar
[45] Glebskiǐ, J. V., Kogan, D. I., Liogon'kiǐ, M. I., and Talanov, V. A., Volume and fraction of satisfiability of formulas of the lower predicate calculus, Otdelenie Matematiki, Mekhaniki i Kibernetiki Akademii Nauk Ukrainskoǐ SSR. Kibernetika. (1969), no. 2, pp. 17–27.Google Scholar
[46] Grädel, E., Kolaitis, R, and Vardi, M., On the decision problem for two-variable first-order logic, this Bulletin, vol. 3 (1997), pp. 53–69.Google Scholar
[47] Graham, R. L., Knuth, D. E., and Patashnik, O., Concrete mathematics. A foundation for computer science, Addison Wesley, Reading, Massachusetts, 1989.Google Scholar
[48] Grandjean, É., Complexity of the first-order theory of almost all finite structures. Information and Control, vol. 57 (1983), no. 2&3, pp. 180–204.Google Scholar
[49] Grandjean, É., The spectra of first-order sentences and computational complexity. SIAM Journal on Computing, vol. 13 (1984), no. 2, pp. 356–373.Google Scholar
[50] Grandjean, É., Universal quantifiers and time complexity of random access machines, Logic and machines: Decision problems and complexity, Proceedings of the symposium “Rekursive Kombinatorik” (Börger, E., Hasenjaeger, G., and Rödding, D., editors), Lecture Notes in Computer Science, vol. 171, Springer, 1984, pp. 366–379.Google Scholar
[51] Grandjean, É., Universal quantifiers and time complexity of random access machines, Mathematical Systems Theory, vol. 18 (1985), no. 2, pp. 171–187.Google Scholar
[52] Grandjean, É., First-order spectra with one variable, Computation theory and logic, In memory of Dieter Rödding (Börger, E., editor), Lecture Notes in Computer Science, vol. 270, Springer, 1987, pp. 166–180.Google Scholar
[53] Grandjean, É., A natural NP-complete problem with a nontrivial lower bound, SIAM Journal on Computing, vol. 17 (1988), no. 4, pp. 786–809.Google Scholar
[54] Grandjean, É., First-order spectra with one variable, Journal of Computer and System Sciences, vol. 40 (1990), no. 2, pp. 136–153.Google Scholar
[55] Grzegorczyk, A., Some classes of recursive functions, Rosprawy Matematyczne, vol. 4 (1953), pp. 1–46.Google Scholar
[56] Gurevich, Y. and Shelah, S., Spectra of monadic second-order formulas with one unary function, 18th IEEE Symposium on Logic in Computer Science (LICS 2003), IEEE Computer Society, Los Alamitos, California, USA, 2003, pp. 291–300.Google Scholar
[57] Hájek, P., On logics of discovery, Mathematical Foundations of Computer Science 1975 (Becvár, J., editor), Lecture Notes in Computer Science, vol. 32, Springer, 1975, pp. 30–45.Google Scholar
[58] Harary, F. and Palmer, E. M., Graphical enumeration, Academic Press, 1973.Google Scholar
[59] Harrison, M. A., Introduction to formal language theory, Addison Wesley, 1978.Google Scholar
[60] Harrow, K., Sub-elementary classes of functions and relations, Ph.D. thesis, New York University, 1973.Google Scholar
[61] Hartmanis, J. and Stearns, R. E., On the complexity of algorithms, Transactions of the American Mathematical Society, vol. 117 (1965), pp. 285–306.Google Scholar
[62] Hesse, W., Allender, E., and Barrington, D. A. Mix, Uniform constant-depth threshold circuits for division and iterated multiplication, Journal of Computer and System Sciences, vol. 65 (2002), no. 4, pp. 695–716.Google Scholar
[63] Hodges, W., Model theory, Encyclopedia of Mathematics and its Applications, vol.42, Cambridge University Press, 1993.Google Scholar
[64] Hunter, A., Spectrum hierarchies and subdiagonal functions, 18th International Symposium on Logic in Computer Science (LICS'03), IEEE Press, 2003, pp. 281–290.Google Scholar
[65] Hunter, A., Limiting cases for spectrum closure results, Australasian Journal of Logic, vol. 2 (2004), pp. 70–90.Google Scholar
[66] Immerman, N. D., Languages that capture complexity classes, SIAM Journal on Computing, vol. 16 (1987), no. 4, pp. 760–778.Google Scholar
[67] Immerman, N. D., Descriptive complexity, Graduate Texts in Computer Science, Springer, 1999.Google Scholar
[68] Johnson, T., Robertson, N., Seymour, P., and Thomas, R., Directed tree–width, Journal of Combinatorial Theory, Serie B, vol. 81 (2001), no. 1, pp. 138–154.Google Scholar
[69] Jones, N. D., Space-bounded reducibility among combinatorial problems, Journal of Computer and System Sciences, vol. 11 (1975), no. 1, pp. 68–85.Google Scholar
[70] Jones, N. D. and Selman, A. L., Turing machines and the spectra of first-order formulas with equality, Conference Record, Fourth Annual ACM Symposium on Theory of Computing, ACM Press, New York, NY, USA, 1972, pp. 157–167.Google Scholar
[71] Jones, N. D., Turing machines and the spectra of first-order formulas, The Journal of Symbolic Logic, vol. 39 (1974), pp. 139–150.Google Scholar
[72] Kalmár, L., Egyszerü példa eldönthetetlen aritmetikai problémàra. (Ein einfaches Beispiel für ein unentscheidbares arithmetisches Problem), Mate és Fizikai Lapok, vol. 50 (1943), pp. 1–23.Google Scholar
[73] Kreisel, G., On the interpretation of non-finitist proofs. II. Interpretation of number theory. Applications, The Journal of Symbolic Logic, vol. 17 (1952), no. 2, pp. 43–58.Google Scholar
[74] Kuroda, S.-Y., Classes of languages and linear-bounded automata, Information and Control, vol. 7 (1964), no. 2, pp. 207–223.Google Scholar
[75] Libkin, L., Elements of finite model theory, Texts in Theoretical Computer Science, Springer, 2004.Google Scholar
[76] Loescher, B., One unary function says less than two in existential second order logic, Information Processing Letters, vol. 61 (1997), no. 2, pp. 69–75.Google Scholar
[77] Lovász, L. and Gács, P., Some remarks on generalized spectra, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 23 (1977), pp. 547–554.Google Scholar
[78] Löwenheim, L., Über Möglichkeiten im Relativkalkül, Mathematische Annalen, vol. 76 (1915), no. 4, pp. 447–470.Google Scholar
[79] Lynch, J. F., Complexity classes and theories of finite models, Mathematical Systems Theory, vol. 15 (1982), no. 2, pp. 127–144.Google Scholar
[80] Makowsky, J. A., Algorithmic uses of the Feferman–Vaught theorem, Annals of Pure and Applied Logic, vol. 126.1–3 (2004), pp. 159–213.Google Scholar
[81] Miller, J., Statement of result on primitive recursive reals, E-mail communication.Google Scholar
[82] Mo, S., The solution of Scholz problems, Chinese Annals of Mathematics, Series A, vol. 12 (1991), no. 1, pp. 89–97.Google Scholar
[83] More, M. and Olive, F., Rudimentary languages and second order logic, Mathematical Logic Quarterly, vol. 43 (1997), pp. 419–426.Google Scholar
[84] Mortimer, M., On languages with two variables, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 21 (1975), pp. 135–140.Google Scholar
[85] Mostowski, A., Concerning a problem of H. Scholz, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 12 (1956), pp. 210–214.CrossRefGoogle Scholar
[86] Myhill, J., Linear bounded automata, Technical Note 60–165, Wright-Patterson Air Force Base, Wright Air Development Division, Ohio, 1960.Google Scholar
[87] Nepomnjaščiǐ, V. A., Rudimentary predicates and Turing computations, Doklady Akademii Nauk SSSR, vol. 195 (1970), pp. 282–284.Google Scholar
[88] Nepomnjaščiǐ, V. A., Examples of predicates inexpressible by s-rudimentary formulas, Kibernetika (Kiev), vol. 2 (1978), pp. 44–46, Russian, English summary.Google Scholar
[89] Olive, F., A conjunctive logical characterization of nondeterministic linear time, Computer Science Logic, CSL'97 (Nielsen, M. and Thomas, W., editors), Lecture Notes in Computer Science, vol. 1414, Springer, 1998, pp. 360–372.Google Scholar
[90] Otto, M., Bounded variable logics and counting—A study in finite models, vol. 9, Springer-Verlag, 1997.Google Scholar
[91] Pudlák, P., The observational predicate calculus and complexity of computations, Commentationes Mathematicae Universitatis Carolinae, vol. 16 (1975), pp. 395–398.Google Scholar
[92] Rabin, M. O., A simple method for undecidability proofs and some applications, Logic, methodology and philosophy of science II (Hillel, Y. Bar, editor), Studies in Logic, North Holland, 1965, pp. 58–68.Google Scholar
[93] Ribenboim, P., The book of prime number records, second ed., Springer, 1989.Google Scholar
[94] Ritchie, R. W., Classes of recursive functions of predictable complexity, Ph.D. thesis, Princeton University, 1960.Google Scholar
[95] Ritchie, R. W., Classes of predictably computable functions, Transactions of the American Mathematical Society, vol. 106 (1963), pp. 139–173.Google Scholar
[96] Robertson, N. and Seymour, P. D., Graph minors. II. Algorithmic aspects of tree–width, Journal of Algorithms, vol. 7 (1986), pp. 309–322.Google Scholar
[97] Robinson, A., Review of [6], MR0077468 (17,1038c).Google Scholar
[98] Rödding, D. and Schwichtenberg, H., Bemerkungen zum Spektralproblem, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 18 (1972), pp. 1–12.Google Scholar
[99] Rose, H. E., Subrecursion. Functions and hierarchies, Oxford Logic Guides, vol. 9, Oxford, Clarendon Press, 1984.Google Scholar
[100] Scholz, H., Ein ungelöstes Problem in der symbolischen Logik, The Journal of Symbolic Logic, vol. 17 (1952), p. 160.Google Scholar
[101] Skordev, D., Computability of real numbers by using a given class of functions in the set of natural numbers, Mathematical Logic Quarterly, vol. 48 (2002), no. Suppl.1, pp. 91–106.Google Scholar
[102] Skordev, D., On the subrecursive computability of several famous constants, Journal of Universal Computer Science, vol. 14 (2008), no. 6, pp. 861–875.Google Scholar
[103] Smullyan, R. M., Theory of formal systems, Annals of Mathematical Studies, vol. 47, Princeton University Press, Princeton, New Jersey, 1961.Google Scholar
[104] Specker, E., Nicht konstruktiv beweisbare Sätze in der Analysis, The Journal of Symbolic Logic, vol. 14 (1949), pp. 145–158.Google Scholar
[105] Tarski, A., Contribution to the theory of models, I,II, Indagationes Mathematicae, vol. 16 (1954), pp. 572–588.Google Scholar
[106] Tarski, A., Mostowski, A., and Robinson, R. M., Undecidable theories, North-Holland Publishing Company, 1953.Google Scholar
[107] Trakhtenbrot, B. A., Impossibility of an algorithm for the decision problem in finite classes, Doklady Akademii Nauk SSSR, vol. 70 (1950), pp. 569–572.Google Scholar
[108] Turing, A. M., On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, vol. 42 (1936), no. 2, pp. 230–265.Google Scholar
[109] Vardi, M., The complexity of relational query languages, STOC'82, ACM, 1982, pp. 137–146.Google Scholar
[110] Wilf, H. S., Generatingfunctionology, Academic Press, 1990.Google Scholar
[111] Woods, A. R., Some problems in logic and number theory and their connections, Ph.D. thesis, University of Manchester, 1981.Google Scholar
[112] Wrathall, C., Rudimentary predicates and relative computation, SIAM Journal on Computing, vol. 7 (1978), no. 2, pp. 194–209.Google Scholar
Supplementary material: PDF

Durand Supplementary Material

Appendix

Download Durand Supplementary Material(PDF)
PDF 160.1 KB