Fifty years of the spectrum problem: survey and new results
From MaRDI portal
Publication:4902770
DOI10.2178/bsl.1804020zbMath1309.03014arXiv0907.5495OpenAlexW2065706312MaRDI QIDQ4902770
Malika More, Neil D. Jones, Arnaud Durand, 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
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)
Related Items
Some remarks on real numbers induced by first-order spectra, Logics of Finite Hankel Rank, On the Variable Hierarchy of First-Order Spectra, Spectra and satisfiability for logics with successor and a unary function, Pseudofinite formulae, Andrzej Mostowski and the Notion of a Model, Partially definable forcing and bounded arithmetic, Axiomatizing Rectangular Grids with no Extra Non-unary Relations, Regular Graphs and the Spectra of Two-Variable Logic with Counting, Unnamed Item, Some thoughts on computational models: from massive human computing to abstract state machines, and beyond
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- One unary function says less than two in existential second order logic
- Algorithmic uses of the Feferman-Vaught theorem
- First-order spectra with one variable
- A uniform method for proving lower bounds on the computational complexity of logical theories
- Super-exponentials nonprimitive recursive, but rudimentary
- Rudimentary relations and primitive recursion: A toolbox
- Rudimentary reductions revisited
- Space-bounded reducibility among combinatorial problems
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Structural properties of context-free sets of graphs generated by vertex replacement
- Upper bounds to the clique width of graphs
- Handle-rewriting hypergraph grammars
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- On the complexity of algebraic numbers. I: Expansions in integer bases
- Das Repräsentantenproblem im Prädikatenkalkül der ersten Stufe mit Identität
- The Spectra of First-Order Sentences and Computational Complexity
- Complexity of the first-order theory of almost all finite structures
- The ultra-weak Ash conjecture and some particular cases
- Reachability is harder for directed than for undirected finite graphs
- Universal quantifiers and time complexity of random access machines
- Graph minors. II. Algorithmic aspects of tree-width
- Complexity of Finding Embeddings in a k-Tree
- Languages that Capture Complexity Classes
- A Natural NP-Complete Problem with a Nontrivial Lower Bound
- A spectrum hierarchy
- Monadic generalized spectra
- On languages with two variables
- Rudimentary Predicates and Relative Computation
- Some Remarks on Generalized Spectra
- A Conjecture Concerning the Spectrum of a Sentence
- Rudimentary Languages and Second‐Order Logic
- Turing machines and the spectra of first-order formulas
- Computability of Real Numbers by Using a Given Class of Functions in the Set of the Natural Numbers
- Primitive Recursiveness of Real Numbers under Different Representations
- Primitive recursive real numbers
- On spectra of sentences of monadic second order logic with counting
- Classes of languages and linear-bounded automata
- Bemerkungen zum Spektralproblem
- Nicht konstruktiv beweisbare Sätze der Analysis
- On the interpretation of non-finitist proofs–Part II
