Optimal On-Line Simulations of Tree Machines by Random Access Machines

DOI10.1137/0221056zbMath0757.68052OpenAlexW2041746306MaRDI QIDQ4015977

David R. Luginbuhl, Michael C. Loui

Publication date: 6 December 1992

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0221056

zbMATH Keywords

on-line simulationrandom access machinereal-time simulationtree machine

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Related Items (3)

Well-partitioned chordal graphs ⋮ Three problems on well-partitioned chordal graphs ⋮ Linear speed-up does not hold on Turing machines with tree storages

This page was built for publication: Optimal On-Line Simulations of Tree Machines by Random Access Machines