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

Compressed postscript
Compressed dvi