The complexity of matrix transposition on one-tape off-line Turing machines with output tape*
T. Lepisto, A. Salomaa · 1993
Dietzfelbinger. hl. and W’ hlaass. The complexity of matrrx transposition on one-tape off-line Turing machines with output tape, Thcorettcal Computer Scrence 108 (1993) 271-290. A series of existing lower bound results for deterministic one-tape Turing machines is extended to another, stronger such model suttable for the computatton of functions: one-tape off-line Turing machines wtth a wrote-only output tape. (“OfT-line” means: havmg a two-way input tape.) The following optrmal lower bound is shown: Computrng the transpose of Boolean ix i-matrrces takes R(1”‘)=Rtt1”~) steps on such Turing machtnes. ()I= 1’ is the length of the input.)