Minimizing access pointers into trees and arrays

DOI10.1016/0022-0000(84)90019-9zbMath0542.68031OpenAlexW1576817182MaRDI QIDQ795505

Michael C. Loui

Publication date: 1984

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(84)90019-9

zbMATH Keywords

simulationtreestime complexityarraysaccess pointersmultidimensional Turing machinemultihead multidimensional machinesMultihead tree machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Information storage and retrieval of data (68P20)

Related Items

Linear speed-up does not hold on Turing machines with tree storages, A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes, On the worst case performance of buddy systems

Cites Work

• Unnamed Item
• Unnamed Item
• On time versus space. II
• An information-theoretic approach to time bounds for on-line computation
• Simulations among multidimensional Turing machines
• A fast implementation of a multidimensional storage into a tree storage
• Two fast simulations which imply some fast string matching and palindrome-recognition algorithms
• Zwei-Band Simulation von Turingmaschinen. (Two-tape simulation of Turing machines)
• Optimal Dynamic Embedding of Trees into Arrays
• New Real-Time Simulations of Multihead Tape Units
• Analysis of a General Mass Storage System
• Two-Tape Simulation of Multitape Turing Machines