Bulletin of Symbolic Logic 18 (4):505-553 (2012)
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||categorize this paper)|
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
Theories of Arithmetics in Finite Models.M. Krynicki & K. Zdanowski - 2005 - Journal of Symbolic Logic 70 (1):1-28.
On Spectra of Sentences of Monadic Second Order Logic with Counting.E. Fischer & J. A. Makowsky - 2004 - Journal of Symbolic Logic 69 (3):617-640.
A Survey of Some Recent Results on Spectrum Exchangeability in Polyadic Inductive Logic.J. Landes, J. B. Paris & A. Vencovská - 2011 - Synthese 181 (1):19 - 47.
The Härtig Quantifier: A Survey.Heinrich Herre, Michał Krynicki, Alexandr Pinus & Jouko Väänänen - 1991 - Journal of Symbolic Logic 56 (4):1153-1183.
Betterness, Spectrum Cases and the Challenge to Transitivity in Axiology.Oscar Horta - 2011 - Diacritica 25:125-137.
Spectra of Formulae with Henkin Quantifiers.Joanna Golinska-Pilarek & Konrad Zdanowski - 2003 - In A. Rojszczak, J. Cachro & G. Kurczewski (eds.), Philosophical Dimensions of Logic and Science. Kluwer Academic Publishers.
The Cofinality Spectrum of the Infinite Symmetric Group.Saharon Shelah & Simon Thomas - 1997 - Journal of Symbolic Logic 62 (3):902-916.
On the Decision Problem for Two-Variable First-Order Logic.Erich Grädel, Phokion G. Kolaitis & Moshe Y. Vardi - 1997 - Bulletin of Symbolic Logic 3 (1):53-69.
Popper's Open Society After Fifty Years: The Continuing Relevance of Karl Popper.I. C. Jarvie & Sandra Pralong (eds.) - 1999 - Routledge.
Spectrum Inversion Without a Difference in Representation is Impossible.Jeff Speaks - 2011 - Philosophical Studies 156 (3):339-361.
Philosophy of Mind.John Campbell - 2003 - In Peter Clark & Katherine Hawley (eds.), Philosophy of Science Today. Oxford University Press. pp. 131.
Computational Complexity of Some Ramsey Quantifiers in Finite Models.Marcin Mostowski & Jakub Szymanik - 2007 - Bulletin of Symbolic Logic 13:281--282.
Added to index2012-11-14
Total downloads14 ( #331,377 of 2,164,599 )
Recent downloads (6 months)1 ( #347,948 of 2,164,599 )
How can I increase my downloads?