The complexity of matrix transposition on one-tape off-line Turing machines with output tape

AbstractA series of existing lower bound results for deterministic one-tape Turing machines is extended to another, stronger such model suitable for the computation of functions: one-tape off-line Turing machines with a write-only output tape. (“Off-line” means: having a two-way input tape.) The following optimal lower bound is shown: Computing the transpose of Boolean l × l-matrices takes Ω(l52)=Ω(n54) steps on such Turing machines. (n=l2 is the length of the input.