scientific article; zbMATH DE number 3750291

MaRDI QIDQ3933743zbMATH OpenFDO

Authors Paul M. B. Vitányi

Publication date 1982

zbMATH Keywords

integer representationmulticounter machinereal-time simulation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited in

(8)

• Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit
• 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
• Tradeoffs for language recognition on alternating machines
• On the simulation of many storage heads by one
• On the power of real-time two-way multihead finite automata with jumps
• On two-tape real-time computation and queues
• Bit-optimal election in synchronous rings

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3933743)