Fifty years of the spectrum problem: survey and new results
Bulletin of Symbolic Logic 18 (4):505-553 (2012)
| 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 | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | No categories specified (fix it) | |||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,709 |
| External links |
  Try with proxy. Try with proxy. |
| Through your library | Configure |
Similar books and articlesM. Krynicki & K. Zdanowski (2005). Theories of Arithmetics in Finite Models. Journal of Symbolic Logic 70 (1):1-28.
William G. Lycan (1973). Inverted Spectrum. Ratio 15 (July):315-9.
E. Fischer & J. A. Makowsky (2004). On Spectra of Sentences of Monadic Second Order Logic with Counting. Journal of Symbolic Logic 69 (3):617-640.
O. Finkel & J. P. Ressayre (1996). Stretchings. Journal of Symbolic Logic 61 (2):563-585.
Heinrich Herre, Michał Krynicki, Alexandr Pinus & Jouko Väänänen (1991). The Härtig Quantifier: A Survey. Journal of Symbolic Logic 56 (4):1153-1183.
Oscar Horta (2011). Betterness, Spectrum Cases and the Challenge to Transitivity in Axiology. Diacritica 25:125-137.
David J. Cole (1990). Functionalism and Inverted Spectra. Synthese 82 (2):207-22.
Joanna Golinska-Pilarek & Konrad Zdanowski (2003). Spectra of Formulae with Henkin Quantifiers. In A. Rojszczak, J. Cachro & G. Kurczewski (eds.), Philosophical Dimensions of Logic and Science. Kluwer Academic Publishers.
Saharon Shelah & Simon Thomas (1997). The Cofinality Spectrum of the Infinite Symmetric Group. Journal of Symbolic Logic 62 (3):902-916.
Erich Grädel, Phokion G. Kolaitis & Moshe Y. Vardi (1997). On the Decision Problem for Two-Variable First-Order Logic. Bulletin of Symbolic Logic 3 (1):53-69.
Jeff Speaks (2011). Spectrum Inversion Without a Difference in Representation is Impossible. Philosophical Studies 156 (3):339-361.
Marcin Mostowski & Jakub Szymanik (2007). Computational Complexity of Some Ramsey Quantifiers in Finite Models. The Bulletin of Symbolic Logic 13:281--282.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2012-11-14Total downloads1 ( #275,053 of 549,697 )Recent downloads (6 months)1 ( #63,425 of 549,697 )How can I increase my downloads? |
My notes
Discussion
