Fifty years of the spectrum problem: survey and new results

DOI10.2178/BSL.1804020MaRDI QIDQ4902770zbMATH OpenOpenAlexFDO

Authors Arnaud Durand, Neil D. Jones, Malika More, Johann A. Makowsky

Publication date 17 January 2013

Published in The Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0907.5495, https://projecteuclid.org/euclid.bsl/1352802980

zbMATH Keywords

characterization of spectracomplement of a spectrumdescriptive complexityfinite model theory

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) History of mathematical logic and foundations (03-03) Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)

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"unter Asser 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 in terms of recursion theory, resource bounded complexity theory, classification by complexity of the defining sentences, and finally in terms of structural graph theory. Although Scholz' question was answered in various ways, Asser's question remains open. One appendix paraphrases the contents of several early and not easily accesible papers by G. Asser, A. Mostowski, J. Bennett and S. Mo. Another appendix contains a compendium of questions and conjectures which remain open.

Recommendations

• Spectral theory -- 50 years of progress and a conclusion
• Some solutions of the finite spectrum problem and applications
• Some new problems in spectral optimization
• scientific article; zbMATH DE number 1281706
• scientific article; zbMATH DE number 486410
• scientific article; zbMATH DE number 3926889
• Fifty years of eigenvalue perturbation theory
• scientific article; zbMATH DE number 5217628
• On the solution of generalized spectrum allocation problems
• Spectrum and related sets: a survey

Cites work

• A Conjecture Concerning the Spectrum of a Sentence
• A Natural NP-Complete Problem with a Nontrivial Lower Bound
• A spectrum hierarchy
• A uniform method for proving lower bounds on the computational complexity of logical theories
• Algorithmic uses of the Feferman-Vaught theorem
• Bemerkungen zum Spektralproblem
• Classes of languages and linear-bounded automata
• Complexity of Finding Embeddings in a k-Tree
• Complexity of the first-order theory of almost all finite structures
• Computability of Real Numbers by Using a Given Class of Functions in the Set of the Natural Numbers
• Das Repräsentantenproblem im Prädikatenkalkül der ersten Stufe mit Identität
• First-order spectra with one variable
• Graph minors. II. Algorithmic aspects of tree-width
• Handle-rewriting hypergraph grammars
• scientific article; zbMATH DE number 3857078 (Why is no real title available?)
• scientific article; zbMATH DE number 45266 (Why is no real title available?)
• scientific article; zbMATH DE number 194009 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 979011 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 877299 (Why is no real title available?)
• scientific article; zbMATH DE number 3419161 (Why is no real title available?)
• Languages that Capture Complexity Classes
• Monadic generalized spectra
• Nicht konstruktiv beweisbare Sätze der Analysis
• On languages with two variables
• On spectra of sentences of monadic second order logic with counting
• On the complexity of algebraic numbers. I: Expansions in integer bases
• On the interpretation of non-finitist proofs–Part II
• One unary function says less than two in existential second order logic
• Primitive recursive real numbers
• Primitive recursiveness of real numbers under different representations
• Reachability is harder for directed than for undirected finite graphs
• Rudimentary Languages and Second‐Order Logic
• Rudimentary Predicates and Relative Computation
• Rudimentary reductions revisited
• Rudimentary relations and primitive recursion: A toolbox
• Some Remarks on Generalized Spectra
• Space-bounded reducibility among combinatorial problems
• Structural properties of context-free sets of graphs generated by vertex replacement
• Super-exponentials nonprimitive recursive, but rudimentary
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The Spectra of First-Order Sentences and Computational Complexity
• The ultra-weak Ash conjecture and some particular cases
• Turing machines and the spectra of first-order formulas
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Universal quantifiers and time complexity of random access machines
• Upper bounds to the clique width of graphs

Cited in

(24)

• Some thoughts on computational models: from massive human computing to abstract state machines, and beyond
• Partially definable forcing and bounded arithmetic
• Pseudofinite formulae
• Logics of finite Hankel rank
• On the variable hierarchy of first-order spectra
• Some remarks on real numbers induced by first-order spectra
• scientific article; zbMATH DE number 4204309 (Why is no real title available?)
• scientific article; zbMATH DE number 3898846 (Why is no real title available?)
• scientific article; zbMATH DE number 3926889 (Why is no real title available?)
• On the generator problem
• A Conjecture Concerning the Spectrum of a Sentence
• Andrzej Mostowski and the notion of a model
• A note on first-order spectra with binary relations
• scientific article; zbMATH DE number 2121574 (Why is no real title available?)
• Axiomatizing rectangular grids with no extra non-unary relations
• Spectra and satisfiability for logics with successor and a unary function
• Regular graphs and the spectra of two-variable logic with counting
• Two variable logic with ultimately periodic counting
• A Short Note on the Early History of the Spectrum Problem and Finite Model Theory
• Two variable logic with ultimately periodic counting
• Hardness of monadic second-order formulae over succinct graphs
• The logics for the complexity classes with limited non-determinism
• My writing
• On Horn spectra

This page was built for publication: Fifty years of the spectrum problem: survey and new results

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4902770)