 | |
All
sessions take place in auditorium 8.| 11:00- | 12:00
| Paul J. Voda, Comenius U, Slovakia
Invited
talk: Two simple intrinsic characterizations of main complexity
classes
We
give two simple uniform characterizations of the complexity
classes L, NL, P, and
NP by register machine programs. Both characterizations
are intrinsic because they do not refer to any time and space bounds. The
first characterization, which permits programs to peek into their
computational history, captures also, Pspace and it is
completely syntactical in that the restrictions on programs are decided
from their syntax. The programs computing predicates of larger classes are
permitted to access larger parts of their history. The second
characterization restricts the access of programs to parts of their input
which are then projected away by existential quantification. |
| 12:00- | 12:30
| Olivier Bournez, LORIA Nancy, France
Paulin
de Naurois, LORIA Nancy, France
Jean-Yves
Marion, LORIA Nancy, France
Safe
recursion and calculus over an arbitrary structure
In
this paper, we show that the Bellantoni and Cook
characterization of the polynomial time computable functions in terms of
safe recursive functions can be transfered to the model of computation over
an arbitrary structure developed by L. Blum,
M. Shub, and S. Smale.
Hence, we provide an implicit complexity characterization of functions
computable in polynomial time over any arbitrary structure. |
| 14:00- | 15:00
| Carl Christian Frederiksen, U Copenhagen,
Denmark
Neil D. Jones, U Copenhagen, Denmark
Invited
talk: Program analysis for implicit computational complexity
This
talk describes methods and practical work that brings
together two lines: automatic estimation of program running
times, and implicit computational complexity. Related
work has been done by Bellantoni and Cook, Benzinger, Hofmann, Jones, Crary
and Weirich, Leivant, Marion, Niggl, Schwichtenberg, and others. In this
work we identify a decidable class of algorithms such that all can be
executed within polynomial time (or logarithmic space). This class includes
many natural algorithms that are used in solving real problems. The class
is properly generalizes "safe recursion" and some related schemes provided by
other researchers. Runtime
bound information is extracted by program data-flow analysis algorithms
that extend the "size-change"
framework of our POPL 2001 paper to account for running times as well as
termination. The analysis allows automatic detection of programs that are
guaranteed to run (or be runnable) in polynomial time. |
| 15:00- | 15:30
| Lars Kristiansen, Oslo U College, Norway
New
recursion-theoretic characterizations of well known complexity
classes
In
this paper we give recursion-theoretic characterizations of
well-known complexity classes by schemes that neither contain
bounds nor any kind of variable segregation. We prove that the class of
problems decidable in logarithmic space is characterized by the closure of
a neat class of initial functions (projections and constants) under
composition and simultaneous recursion on notation. We also characterize
the class of number-theoretic 0-1 valued functions
computable in linear space as the 0-1 valued functions of the closure of a
neat class of initial functions (projections and constants) under
composition and simultaneous recursion. |
| 16:00- | 16:30
| Klaus Aehlig, U Munich, Germany
Jan
Johannsen, U Munich, Germany
An
elementary fragment of second-order lambda calculus
A
fragment of second-order lambda calculus (System F) is defined
that characterizes the elementary recursive functions. Type quantification
is restricted to be non-interleaved and stratified, i.e., the types are
assigned levels, and a quantified variable can only be instantiated by a
type of smaller level, with a slightly liberalized treatment of the level
zero. |
| 16:30- | 17:00
| Karl-Heinz Niggl, Techn. U of Ilmenau, Germany
Control
structures in programs and computational complexity
A
key problem in implicit complexity is to analyse the impact on
program run times of nesting (restricted) control structures, such as
recursion in all finite types in functional languages or for-do statements
in imperative languages. In particular, are there methods of extracting
information from the syntax of such programs so as to distinguish programs
that run in polynomial time from those that run in (iterated) exponential
time? If so, is there a general rationale behind these methods that gives
insight as to why some nesting of control structures may cause a blow up in
complexity, while others do not? This paper integrates various recent
solutions to these problems into a uniform approach to implicit
complexity. |
| |
![[previous]](../img/prev.gif){kind=small}
![[up]](../img/up.gif){kind=small}
![[next]](../img/next.gif){kind=small}
