Eva Rose
University of Copenhagen
The existence of a constant factor time hierarchy [2] within sets
decidable within a (time-constructible) time bound is a necessary
property for reasoning theoretically about linear time
optimisations. However, proving this property, typically involve
careful construction of custom interpreters or compilers, which is a
tedious affair. A more generic method to state the existence or not
is desirable.
We discussed some aspects of finite branching for a programming
language (viewed as a computation model) which are necessary for the
existence of a time-hierarchy assuming a realistic memory
organisation and implementation: a finite number of constructors,
variables, and functions, and finite branching of data and
control. Then, we analyse some languages for which the existence of a
constant factor time-hierarchy is already known. Finally, we drew the
analogy to traditional machine model theory.
This is an extension of the work on "Linear Time Hierarchies for a
Functional Language Machine Model" which showed that CAM (the
categorical abstract machine [1]) has a constant factor time
hierachy, reported at ESOP '96 ([3] also available through the URL
cited below).
-
G. Cousineaum P. L. Curien and M. Mauny. The categorical abstract
machine. In J.-P. Jouannaud, FPCA '85-IFIP International
Conference on Functional Programming Languages and Computer
Architecture, LNCS 201, pages 50-64. Nancy, France, 1985.
-
N. D. Jones. Constant time factors do matter. In Steven Homer,
editor, STOC '93. Symposium on Theory of Computing, pages
602-611. ACM Press, 1993.
-
E. Rose. Linear time hierachies for a functional language
machine model. In H. R. Nielson, editor, Programming Languages
and Systems - ESOP`96, volume 1058 of LNCS, pages 311-325,
Linkvping, Sweden, Apr 1996.
DIKU (Semantics group)
University of Copenhagen
Universitetsparken 1
DK-2100 Copenhagen {\O}
Denmark
Email:
evarose@diku.dk
Home page:
http://www.diku.dk/research-groups/topps/people/evarose.html
Back to the list of talks