Spectra and variables

Speaker(s)

Eryk Kopczyński

Affiliation

Uniwersytet Warszawski

Date

April 1, 2015, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

Given a formula \phi of some logic, the spectrum of \phi, denoted spec(\phi), is the set of non-negative integers n such that \phi has a model of cardinality n. The notion of a spectrum has been introduced by Scholz in 1952, along with the main problem: characterize sets of integers which appear as spectra of a given class of formulae. Fagin has shown in his seminal paper in 1974 that a set S is a spectrum of some first order formula \phi iff the set of unary representations of elements of S is in NP. This also shows that the main open problem from spectra theory, called Asser's conjecture -- whether a complement of a spectrum is also a spectrum -- is equivalent to the complexity theoretic problem NEXPTIME=co-NEXPTIME. An interesting question is, what happens when we put restrictions on the vocabulary, formulae, or models involved?

In the previous talk, I have been talking about bounded degree and planar spectra. In this talk, I am going to talk about the following restrictions:

- Variable hierarchy of spectra: Let spec_k be spectra of formulae of
 FO_k logic (using k variables). We show that for k>=2 spec_k
 \subsetneq spec_{2k+2}, hence the variable hierarchy does not collapse.
 We also show how this relates the arity hierarchy of spectra to
 complexity theory.

- We consider only formulae of C^2 logic, that is, using only two
 variables and counting up to some threshold (``there exist at least $k$
 elements $x$ such that \phi(x,y)''). In this case, we show that spectra
 are exactly ultimately periodic sets, and in the more general
 multi-dimensional case where we count the number of elements satisfying
 predicate P_i for i=1,\ldots,k, they are exactly semilinear sets.  This
 shows that Asser's conjecture holds for C^2 logic.

The talk is based on results obtained with Tony Tan.

---