@article{10.1145/2733376,
    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.},
    Address = {New York, NY, USA},
    Author = {Kopczy\'{n}ski, Eryk and Tan, Tony},
    File = {On the variable hierarchy of first-order spectra - 1403.2225.pdf},
    ISSN = {1529-3785},
    Journal = {ACM Trans. Comput. Logic},
    Keywords = {bounded number of variables, First-order spectra, nondeterministic exponential time},
    Month = {April},
    Number = {2},
    Publisher = {Association for Computing Machinery},
    Title = {On the Variable Hierarchy of First-Order Spectra},
    URL = {https://doi.org/10.1145/2733376},
    Volume = {16},
    Year = {2015},
    articleno = {17},
    bdsk-url-1 = {https://doi.org/10.1145/2733376},
    date-added = {2021-09-07 15:19:30 +0200},
    date-modified = {2021-09-07 15:19:30 +0200},
    issue_date = {March 2015},
    numpages = {12},
    doi = {10.1145/2733376}
}

@article{10.1145/2733376, 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.}, Address = {New York, NY, USA}, Author = {Kopczy\'{n}ski, Eryk and Tan, Tony}, File = {On the variable hierarchy of first-order spectra - 1403.2225.pdf}, ISSN = {1529-3785}, Journal = {ACM Trans. Comput. Logic}, Keywords = {bounded number of variables, First-order spectra, nondeterministic exponential time}, Month = {April}, Number = {2}, Publisher = {Association for Computing Machinery}, Title = {On the Variable Hierarchy of First-Order Spectra}, URL = {https://doi.org/10.1145/2733376}, Volume = {16}, Year = {2015}, articleno = {17}, bdsk-url-1 = {https://doi.org/10.1145/2733376}, date-added = {2021-09-07 15:19:30 +0200}, date-modified = {2021-09-07 15:19:30 +0200}, issue_date = {March 2015}, numpages = {12}, doi = {10.1145/2733376} }