Esta página aún no ha sido traducida. A continuación se muestra la página en inglés.

### viernes 23 de marzo de 2012

11:00am IMDEA conference room

**Neil Jones***, Profesor**, DIKU University of Copenhagen, Denmark*

### 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 the development in the late 1960s by Hartmanis, 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.