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)|
|Through your library||Configure|
Similar books and articles
M. 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.
J. Landes, J. B. Paris & A. Vencovská (forthcoming). A Survey of Some Recent Results on Spectrum Exchangeability in Polyadic Inductive Logic. Synthese.
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.
I. C. Jarvie & Sandra Pralong (eds.) (1999/2003). Popper's Open Society After Fifty Years: The Continuing Relevance of Karl Popper. Routledge.
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.
Sorry, there are not enough data points to plot this chart.
Added to index2012-11-14
Total downloads1 ( #275,053 of 549,697 )
Recent downloads (6 months)1 ( #63,425 of 549,697 )
How can I increase my downloads?