Tape versus queue and stacks: The lower bounds
- 1 July 1988
- journal article
- Published by Elsevier in Information and Computation
- Vol. 78 (1) , 56-85
- https://doi.org/10.1016/0890-5401(88)90003-x
Abstract
No abstract availableKeywords
This publication has 13 references indexed in Scilit:
- Combinatorial lower bound arguments for deterministic and nondeterministic Turing machinesTransactions of the American Mathematical Society, 1985
- Two nonlinear lower bounds for on-line computationsInformation and Control, 1984
- On-line simulation of k + 1 tapes by k tapes requires nonlinear timeInformation and Control, 1982
- An information-theoretic approach to time bounds for on-line computationJournal of Computer and System Sciences, 1981
- Algorithmic Information TheoryIBM Journal of Research and Development, 1977
- On the Length of Programs for Computing Finite Binary SequencesJournal of the ACM, 1966
- Two-Tape Simulation of Multitape Turing MachinesJournal of the ACM, 1966
- On the computational complexity of algorithmsTransactions of the American Mathematical Society, 1965
- A formal theory of inductive inference. Part IInformation and Control, 1964
- Real time computationIsrael Journal of Mathematics, 1963