The complexity of on-line simulations between multidimensional turing machines and random access machines

DOI10.1007/BF01213861zbMath0780.68034MaRDI QIDQ4013406

David R. Luginbuhl, Michael C. Loui

Publication date: 27 September 1992

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

time complexityweight-balanced treeson-line simulations between multidimensional Turing machines and random access machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (1)

Sorting, linear time and the satisfiability problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Random access machines with multi-dimensional memories
• The problem of space invariance for sequential machines
• Simulations among multidimensional Turing machines
• Steady-paced-output and fractional-on-line algorithms on a RAM
• Two fast simulations which imply some fast string matching and palindrome-recognition algorithms
• Time bounded random access machines
• Optimal Dynamic Embedding of Trees into Arrays
• Fast Simulation of Turing Machines by Random Access Machines
• A nonlinear lower bound for random-access machines under logarithmic cost
• Storage Modification Machines
• Relations Among Complexity Measures
• On-Line Turing Machine Computations
• Binary Search Trees of Bounded Balance

This page was built for publication: The complexity of on-line simulations between multidimensional turing machines and random access machines