Fast Simulation of Turing Machines by Random Access Machines
From MaRDI portal
Publication:3805901
DOI10.1137/0217005zbMath0657.68048MaRDI QIDQ3805901
Jan van Leeuwen, Martti Penttonen, Jyrki Katajainen
Publication date: 1988
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://dspace.library.uu.nl/handle/1874/16296
68Q25: Analysis of algorithms and problem complexity
Related Items
The problem of space invariance for sequential machines, Invariance properties of RAMs and linear time, Sorting, linear time and the satisfiability problem, The complexity of on-line simulations between multidimensional turing machines and random access machines