## On Languages Accepted with Simultaneous Complexity Bounds and
Their Ranking Problem

#### Alberto Bertoni, Carlo Mereghetti, and Giovanni Pighizzini

###### Dipartimento di Scienze dell'Informazione

Università degli Studi di Milano

via Comelico 39 -- 20135 Milano, Italy

##### Abstract

In this paper, we consider Turing machines having simultaneous bounds
on working space *s(n)*, input head inversions *i(n)* and
ambiguity degree *d(n)*.
Besides the standard notion of space complexity type 1, we
discuss a stronger notion type 2. In the deterministic case, we show
an optimal
*\Omega_{\infty}(\frac{\log n}{\log\log n})* bound on input head
inversions
for recognizing nonregular languages on type 1 machines that does not hold
for type 2 machines. Subsequently, the parallel complexity of
the ranking problem is studied. We prove that any language accepted on type
2 machines within *s(n),i(n),d(n)* simultaneous bounds such that
*s(n)\cdot i(n)\cdot d(n)=O(\log n)* can be ranked in DET.

**Download**

Compressed postscript

Compressed dvi