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