An information-theoretic approach to time bounds for on-line computation
From MaRDI portal
Publication:1156484
DOI10.1016/0022-0000(81)90009-XzbMATH Open0468.68055MaRDI QIDQ1156484FDOQ1156484
Authors: Janos Simon, Wolfgang J. Paul, Joel I. Seiferas 
Publication date: 1981
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Cites Work
- A formal theory of inductive inference. Part I
- Relations Among Complexity Measures
- Two-Tape Simulation of Multitape Turing Machines
- Counter machines and counter languages
- Boolean Memories
- Real-Time Simulation of Multihead Tape Units
- Title not available (Why is that?)
- On time versus space. II
- Real time computation
- Title not available (Why is that?)
- On the Minimum Computation Time of Functions
- New Real-Time Simulations of Multihead Tape Units
- Title not available (Why is that?)
- Real-time solutions of the origin-crossing problem
- Title not available (Why is that?)
Cited In (13)
- Minimizing access pointers into trees and arrays
- Milking the Aanderaa argument
- Three one-way heads cannot do string matching
- Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
- `Ideal learning' of natural language: positive results about learning from positive evidence
- On the power of several queues
- Tape versus queue and stacks: The lower bounds
- Simulations among multidimensional Turing machines
- On space-bounded synchronized alternating Turing machines
- An \(n^{1.618}\) lower bound on the time to simulate one queue or two pushdown stores by one tape
- On the structure of one-tape nondeterministic Turing machine time hierarchy
- On two-tape real-time computation and queues
- On the simulation of many storage heads by one
This page was built for publication: An information-theoretic approach to time bounds for on-line computation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1156484)
