Transposition of an \(\ell \times \ell\) matrix requires \(\Omega\) (log \(\ell)\) reversals on conservative Turing machines

DOI10.1016/0020-0190(88)90163-9zbMath0658.68047OpenAlexW2095345626MaRDI QIDQ1111379

Walter W. Kirchherr

Publication date: 1988

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(88)90163-9

zbMATH Keywords

Turing machinematrix transpositionconservative k-tape machinepeppling game

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Reversal Complexity
• A Fast Computer Method for Matrix Transposing

This page was built for publication: Transposition of an \(\ell \times \ell\) matrix requires \(\Omega\) (log \(\ell)\) reversals on conservative Turing machines