Name
Abstract | ||
|---|---|---|
The spectrum of a first-order logic sentence is the set of natural numbers that are cardinalities of its finite models. In this article, we study the hierarchy of first-order spectra based on the number of variables. It has been conjectured that it collapses to three variables. We show the opposite: it forms an infinite hierarchy. However, despite the fact that more variables can express more spectra, we show that to establish whether the class of first-order spectra is closed under complement, it is sufficient to consider sentences using only three variables and binary relations. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1145/2733376 | ACM Trans. Comput. Log. |
Keywords | Field | DocType |
Theory,First-order spectra,bounded number of variables,nondeterministic exponential time | Discrete mathematics,Combinatorics,Natural number,First order,Binary relation,Cardinality,Spectral line,Hierarchy,Sentence,Mathematics | Journal |
Volume | Issue | ISSN |
16 | Issue-in-Progress | 1529-3785 |
Citations | PageRank | References |
0 | 0.34 | 14 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eryk Kopczynski | 1 | 64 | 9.68 |
| Tony Tan | 2 | 53 | 8.01 |