COMPLEXITY MODELS FOR INCREMENTAL COMPUTATION

Authors
MILTERSEN PB SUBRAMANIAN S VITTER JS TAMASSIA R
Citation
Pb. Miltersen et al., COMPLEXITY MODELS FOR INCREMENTAL COMPUTATION, Theoretical computer science, 130(1), 1994, pp. 203-236
Citations number
24
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
130
Issue
1
Year of publication
1994
Pages
203 - 236
Database
ISI
SICI code
0304-3975(1994)130:1<203:CMFIC>2.0.ZU;2-N
Abstract
We present a new complexity theoretic approach to incremental computat ion. We define complexity classes that capture the intuitive notion of incremental efficiency and study their relation to existing complexit y classes. We show that problems that have small sequential space comp lexity also have small incremental time complexity.