Linear speed-up does not hold on Turing machines with tree storages

DOI10.1016/0020-0190(93)90078-NzbMath0788.68060MaRDI QIDQ688445

Martin Hühne

Publication date: 20 December 1993

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

zbMATH Keywords

computational complexityTuring machinesKolmogorov complexitylower boundsspeed-uponline simulationtree storage

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimizing access pointers into trees and arrays
• On time versus space. II
• A fast implementation of a multidimensional storage into a tree storage
• Deterministic simulation of a single tape turing machine by a random access machine in sub-linear time
• Optimal Dynamic Embedding of Trees into Arrays
• Optimal On-Line Simulations of Tree Machines by Random Access Machines
• Relations Among Complexity Measures
• On the Computational Complexity of Algorithms
• Boolean Memories
• On the Minimum Computation Time of Functions

This page was built for publication: Linear speed-up does not hold on Turing machines with tree storages