Characterizing Computation Models with a Constant Factor Time Hierachy

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).

  1. 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.
  2. 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.
  3. 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.

Eva Rose

DIKU (Semantics group)
University of Copenhagen
Universitetsparken 1
DK-2100 Copenhagen {\O}
Home page:

Back to the list of talks