Minimizing access pointers into trees and arrays

DOI10.1016/0022-0000(84)90019-9MaRDI QIDQ795505zbMATH OpenOpenAlexFDO

Authors 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

access pointersarraysmultidimensional Turing machinemultihead multidimensional machinesMultihead tree machinessimulationtime complexitytrees

Mathematics Subject Classification ID

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

Review text

Multihead tree machines and multihead multidimensional machines are used to develop new methods for minimizing access pointers into trees and arrays. Every multihead tree machine of time complexity t(n) can be simulated on-line by a tree machine with only two access heads in time \(O(t(n) \log t(n)/\log \log t(n)).\) Every multihead e-dimensional machine of time complexity t(n) can be simulated on-line by a d-dimensional machine with two access heads in time \(O(t(n)^{1+1/d-1/de} \log t(n)).\) The simulation for trees is optimal.

Recommendations

• Narrowing Data-Structures with Pointers
• scientific article; zbMATH DE number 3876615
• Vectorization of tree traversals
• A space efficient direct access data structure
• scientific article; zbMATH DE number 1947390
• scientific article; zbMATH DE number 3907783

Cites work

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

Cited in

(4)

• On the worst case performance of buddy systems
• Optimal On-Line Simulations of Tree Machines by Random Access Machines
• 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

This page was built for publication: Minimizing access pointers into trees and arrays

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q795505)