Fifty years of the spectrum problem: survey and new results (Q4902770): Difference between revisions

@@ Property / author @@
-Johann A. Makowsky
@@ Property / author: Johann A. Makowsky / rank @@
-Normal rank
@@ Property / author @@
+Johann A. Makowsky
@@ Property / author: Johann A. Makowsky / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2065706312
@@ Property / OpenAlex ID: W2065706312 / rank @@
+Normal rank
@@ Property / arXiv ID @@
+.5495
@@ Property / arXiv ID: 0907.5495 / rank @@
+Normal rank
@@ Property / cites work @@
+Handle-rewriting hypergraph grammars
@@ Property / cites work: Handle-rewriting hypergraph grammars / rank @@
+Normal rank
@@ Property / cites work @@
+Structural properties of context-free sets of graphs generated by vertex replacement
+Normal rank
@@ Property / cites work @@
+The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
+Normal rank
@@ Property / cites work @@
+On languages with two variables
@@ Property / cites work: On languages with two variables / rank @@
+Normal rank
@@ Property / cites work @@
+Rudimentary Languages and Second‐Order Logic
@@ Property / cites work: Rudimentary Languages and Second‐Order Logic / rank @@
+Normal rank
@@ Property / cites work @@
+Algorithmic uses of the Feferman-Vaught theorem
@@ Property / cites work: Algorithmic uses of the Feferman-Vaught theorem / rank @@
+Normal rank
@@ Property / cites work @@
+A uniform method for proving lower bounds on the computational complexity of logical theories
+Normal rank
@@ Property / cites work @@
+Rudimentary Predicates and Relative Computation
@@ Property / cites work: Rudimentary Predicates and Relative Computation / rank @@
+Normal rank
@@ Property / cites work @@
+Q3995745
@@ Property / cites work: Q3995745 / rank @@
+Normal rank
@@ Property / cites work @@
+Primitive Recursiveness of Real Numbers under Different Representations
+Normal rank
@@ Property / cites work @@
+Primitive recursive real numbers
@@ Property / cites work: Primitive recursive real numbers / rank @@
+Normal rank
@@ Property / cites work @@
+The ultra-weak Ash conjecture and some particular cases
+Normal rank
@@ Property / cites work @@
+Some Remarks on Generalized Spectra
@@ Property / cites work: Some Remarks on Generalized Spectra / rank @@
+Normal rank
@@ Property / cites work @@
+Super-exponentials nonprimitive recursive, but rudimentary
+Normal rank
@@ Property / cites work @@
+One unary function says less than two in existential second order logic
+Normal rank
@@ Property / cites work @@
+Classes of languages and linear-bounded automata
@@ Property / cites work: Classes of languages and linear-bounded automata / rank @@
+Normal rank
@@ Property / cites work @@
+On the interpretation of non-finitist proofs–Part II
+Normal rank
@@ Property / cites work @@
+Turing machines and the spectra of first-order formulas
+Normal rank
@@ Property / cites work @@
+First-order spectra with one variable
@@ Property / cites work: First-order spectra with one variable / rank @@
+Normal rank
@@ Property / cites work @@
+A Natural NP-Complete Problem with a Nontrivial Lower Bound
+Normal rank
@@ Property / cites work @@
+Universal quantifiers and time complexity of random access machines
+Normal rank
@@ Property / cites work @@
+The Spectra of First-Order Sentences and Computational Complexity
+Normal rank
@@ Property / cites work @@
+Complexity of the first-order theory of almost all finite structures
+Normal rank
@@ Property / cites work @@
+Q4040797
@@ Property / cites work: Q4040797 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4714446
@@ Property / cites work: Q4714446 / rank @@
+Normal rank
@@ Property / cites work @@
+On spectra of sentences of monadic second order logic with counting
+Normal rank
@@ Property / cites work @@
+A spectrum hierarchy
@@ Property / cites work: A spectrum hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Monadic generalized spectra
@@ Property / cites work: Monadic generalized spectra / rank @@
+Normal rank
@@ Property / cites work @@
+Q3325707
@@ Property / cites work: Q3325707 / rank @@
+Normal rank
@@ Property / cites work @@
+Rudimentary relations and primitive recursion: A toolbox
+Normal rank
@@ Property / cites work @@
+Bemerkungen zum Spektralproblem
@@ Property / cites work: Bemerkungen zum Spektralproblem / rank @@
+Normal rank
@@ Property / cites work @@
+Graph minors. II. Algorithmic aspects of tree-width
+Normal rank
@@ Property / cites work @@
+Q4877295
@@ Property / cites work: Q4877295 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4332930
@@ Property / cites work: Q4332930 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4198075
@@ Property / cites work: Q4198075 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5682013
@@ Property / cites work: Q5682013 / rank @@
+Normal rank
@@ Property / cites work @@
+Upper bounds to the clique width of graphs
@@ Property / cites work: Upper bounds to the clique width of graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Nicht konstruktiv beweisbare Sätze der Analysis
@@ Property / cites work: Nicht konstruktiv beweisbare Sätze der Analysis / rank @@
+Normal rank
@@ Property / cites work @@
+Computability of Real Numbers by Using a Given Class of Functions in the Set of the Natural Numbers
+Normal rank
@@ Property / cites work @@
+Das Repräsentantenproblem im Prädikatenkalkül der ersten Stufe mit Identität
+Normal rank
@@ Property / cites work @@
+A Conjecture Concerning the Spectrum of a Sentence
+Normal rank
@@ Property / cites work @@
+Complexity of Finding Embeddings in a <i>k</i>-Tree
+Normal rank
@@ Property / cites work @@
+Space-bounded reducibility among combinatorial problems
+Normal rank
@@ Property / cites work @@
+Rudimentary reductions revisited
@@ Property / cites work: Rudimentary reductions revisited / rank @@
+Normal rank
@@ Property / cites work @@
+Reachability is harder for directed than for undirected finite graphs
+Normal rank
@@ Property / cites work @@
+Q4227581
@@ Property / cites work: Q4227581 / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of algebraic numbers. I: Expansions in integer bases
+Normal rank
@@ Property / cites work @@
+Languages that Capture Complexity Classes
@@ Property / cites work: Languages that Capture Complexity Classes / rank @@
+Normal rank
@@ Property / cites work @@
+Uniform constant-depth threshold circuits for division and iterated multiplication.
+Normal rank