The Spectrum Problem Workshop

CSL'05 Satellite Workshop
Sunday August 21st, 2005
Oxford, UK




Presentation
 Registration
 Program (new!)


Workshop location : Fitzjames Room 1, Merton College

New : list of talks and abstracts !!!


Presentation

The spectrum of a first-order sentence is the set of cardinalities of its finite models. Since the early 50s, several important questions about spectra have been asked and remain to a great extent unsolved.  One of the most famous of them, known as Asser's question, asks whether the complement of the spectrum of a sentence is always a spectrum and has been proved equivalent to the NE = coNE question.  Several other long lasting open questions about spectra eventually proved to correspond to fundamental complexity theoretic problems and most of the results proved so far develop from the connection with complexity theory and are among problems at the origin of descriptive complexity and finite model theory.

Fifty years after Asser’s question, we intend this workshop as an expository and prospective meeting, setting out the open problems and known results in a historical perspective and exploring current research trends.


List of speakers:

Registration

If you wish to attend the workshop please send an email to the organizers (replace "_at_" by @ in email addresses)

 Official registration will be made through the CSL'05 website.

Program

9:45 Opening

10:00 - 11:10 Janos Makowsky, "50 years of the spectrum problem"

11:10 - 11:40 Coffee

11:40 - 00:20 Neil Jones, "Some remarks on the spectrum problem"

00:20 - 01:00 Mor Doron, "Weakly Decomposable Classes and Their Spectra"

Lunch

02:30 - 03:10 Aaron Hunter, "Closure Results for First-Order Spectra: The Model Theoretic Approach"

03:10 - 03:50 Annie Chateau, "The Ultra-Weak Ash Conjecture is Equivalent to the Spectrum Conjecture, and Some Relative Results"

03:50 - 04:20 Tea

04:20 - 05:15 Neil Immerman, "Recent Progress in Descriptive Complexity"

End of the workshop



Talks : titles and abstracts


Annie Chateau
Title:  The Ultra-Weak Ash Conjecture is Equivalent to the Spectrum Conjecture, and Some Relative Results
Abstract: In 1994, Christopher J. Ash introduced a family of functions $N_{\sigma, k}$, which count the number of non $k$-equivalent classes of
$\sigma$-structures of size $n$. He proved that, if those functions are eventually constant, then theSpectrum conjecture holds. We present a new condition, called "ultra-weak Ash conjecture", which is exactly equivalent to the Spectrum conjecture. In this context, we describe some particular cases that are either "easy" or equivalent to the plain Spectrum conjecture.


Mor Doron
Title : Weakly Decomposable Classes and Their Spectra.
Abstract : A class $K$ of relational structures is said to by weakly $k$-decomposable if for every $m$ there exists $n$ such that every structure in $K$ of size at least $n$ is the union of two structures of size at least $m$ with intersection of size at most $k$. I will outline a proof by S. Shelah that the MSO spectrum of a weakly $k$-decomposable class can not contain large gaps. I will state some open questions concerning the MSO spectra of weakly $k$-decomposable classes, one of which is: Are such spectra necessarily eventually periodic?


Aaron Hunter
Title: Closure Results for First-Order Spectra: The Model Theoretic Approach
Abstract: We say that a class Q of spectra is closed under f if f(S) is in Q whenever S is in Q.  In this talk, we will survey some existing closure results for natural classes of spectra.  We will see that strong closure results have been obtained for functions that are assympotically larger than the identity, but similar results are more difficult to obtain for sub-diagonal functions.  We focus primarily on results that have been obtained through explicit transformations on finite structures.  We suggest that this approach is particularly well suited for studying closure results, because many interesting classes of spectra do not admit simple complexity theoretic characterizations.


Neil Immerman
Title: Recent Progress in Descriptive Complexity
Abstract: The Spectrum Problem and its characterization in terms of complexity  by Jones and Selman, and independently by Fagin, was the beginning of finite model theory and descriptive complexity.  In this talk, I will discuss the current scene in descriptive complexity including perspectives on the long-standing open problems as well as current problems and applications including dynamic complexity and static analysis.


Neil Jones
Title: Some remarks on the spectrum problem
Abstract: Scholz posed in 1952 the problem of characterising the class of spectra (of formulas in first-order logic with equality), and there soon after came interesting related questions by Asser, Bennett, Mostowski, etc. In the early 1970s Alan Selman and I discovered an exact characterisation of  spectra.
The problem interested me because of its similarity to the "LBA problem" then widely studied in theoretical computer science. Spectra had properties very similar to the context-sensitive languages, and I began with the hypothesis that they were the same class. The correct answer turned out to be different,  that spectra equal NEXPTIME. This result was in a way a product of its time, since this characterisation of "the spectrum problem" would not have been naturally expressible prior to the development in the late 1960s by Harmanis, Stearns and others of time- and space-bounded complexity classes.

Since then a wide range of research has been done in finite model theory, datalog, programming languages and "implicit complexity", to name a few closely related topics. From my  computer science background a natural next question was: what is the expressive power of various subrecursive programming languages on finite input data structures? This brings up questions of the effects of imposing limits on both stored data, and on control structures. The talk will conclude with an array of results (many obtained by others), point out some regularities, and a tantalising fact (in my opinion) that is still not satisfactorily understood: that primitive recursion as a control structure seems to be inherently less expressive than general recursion or even tail recursion.


Janos Makowsky
Title: 50 years of the spectrum problem
Abstract: We review the history of the spectrum problem, but not necessarily in chronological but in topical order. We show how the prevailing trends of a period shaped the questions and how the answers shaped in return further trends in logic and complexity.