IMDEA Software

IMDEA initiative

Home > Events > Invited Talks > 2012 > Kleenes Second Recursion Theorem (Work in Progress)

Neil Jones

Wednesday, March 21, 2012

11:00am IMDEA conference room

Neil Jones, Professor, DIKU University of Copenhagen, Denmark

Kleenes Second Recursion Theorem (Work in Progress)

Abstract:

Self-adjusting computation is a language-based approach to writing incremental programs that respond dynamically to input changes by maintaining a trace of the computation consistent with the input, thus also updating the output. For monotonic programs, i.e., where localized input changes cause localized changes in the computation, the trace can be repaired efficiently by insertions and deletions. However, non-local input changes can cause major reordering of the trace; in such cases, updating the trace can be asymptotically equal to running from scratch. We show how to eliminate the monotonicity restriction by generalizing the update mechanism to use trace slices, which are partial fragments of the computation that can be reordered with some bookkeeping.