Eva Rose
University of Copenhagen
The existence of a constant factor time hierarchy [2] within sets
decidable within a (timeconstructible) 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 timehierarchy 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 timehierarchy 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 '85IFIP International
Conference on Functional Programming Languages and Computer
Architecture, LNCS 201, pages 5064. Nancy, France, 1985.

N. D. Jones. Constant time factors do matter. In Steven Homer,
editor, STOC '93. Symposium on Theory of Computing, pages
602611. 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 311325,
Linkvping, Sweden, Apr 1996.
DIKU (Semantics group)
University of Copenhagen
Universitetsparken 1
DK2100 Copenhagen {\O}
Denmark
Email:
evarose@diku.dk
Home page:
http://www.diku.dk/researchgroups/topps/people/evarose.html
Back to the list of talks