On-Line Reevaluation of Functions
DOI:
https://doi.org/10.7146/dpb.v21i380.6612Abstract
Given a finite set S and a function f : S^n -> S^m, we consider the problem of making a data structure which maintains a value of x in S^n and allows us to efficiently change an arbitrary coordinate of x and efficiently evaluate f_i(x) for arbitrary i. We both examine the problem for specific choices of f and relate the possibility of an efficient solution to general properties of f: expressibility as a formula, space complexity and time complexity.Downloads
Published
1992-01-01
How to Cite
Miltersen, P. B. (1992). On-Line Reevaluation of Functions. DAIMI Report Series, 21(380). https://doi.org/10.7146/dpb.v21i380.6612
Issue
Section
Articles
License
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.