An information-theoretic approach to time bounds for on-line computation
From MaRDI portal
Publication:1156484
DOI10.1016/0022-0000(81)90009-XzbMath0468.68055MaRDI QIDQ1156484
Janos Simon, Joel I. Seiferas, Wolfgang J. Paul
Publication date: 1981
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (13)
On the structure of one-tape nondeterministic Turing machine time hierarchy ⋮ On the simulation of many storage heads by one ⋮ `Ideal learning' of natural language: positive results about learning from positive evidence ⋮ Tape versus queue and stacks: The lower bounds ⋮ Milking the Aanderaa argument ⋮ Simulations among multidimensional Turing machines ⋮ Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity ⋮ On space-bounded synchronized alternating Turing machines ⋮ On the power of several queues ⋮ Minimizing access pointers into trees and arrays ⋮ On two-tape real-time computation and queues ⋮ An \(n^{1.618}\) lower bound on the time to simulate one queue or two pushdown stores by one tape ⋮ Three one-way heads cannot do string matching
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On time versus space. II
- Real time computation
- New Real-Time Simulations of Multihead Tape Units
- Relations Among Complexity Measures
- Boolean Memories
- Two-Tape Simulation of Multitape Turing Machines
- Counter machines and counter languages
- Real-time solutions of the origin-crossing problem
- On the Minimum Computation Time of Functions
- A formal theory of inductive inference. Part I
- Real-Time Simulation of Multihead Tape Units
This page was built for publication: An information-theoretic approach to time bounds for on-line computation
