scientific article; zbMATH DE number 3495593

zbMATH Open0316.68029MaRDI QIDQ4077448FDOQ4077448

Authors: Stål Aanderaa 

Publication date: 1974

Title of this publication is not available (Why is that?)

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Automata and formal grammars in connection with logical questions (03D05) Turing machines and related notions (03D10)

Cited In (16)

• Deterministic realization of nondeterministic computations with a low measure of nondeterminism
• Real-time computations with restricted nondeterminism
• Milking the Aanderaa argument
• Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time
• An information-theoretic approach to time bounds for on-line computation
• Alternating real-time computations
• On the power of several queues
• Possibilities of various types of alternating automata
• Tape versus queue and stacks: The lower bounds
• Realtime subshifts
• QRT FIFO automata, breadth-first grammars and their relations
• \(k\) versus \(k+1\) index registers and modifiable versus non-modifiable programs
• On heads versus tapes
• An \(n^{1.618}\) lower bound on the time to simulate one queue or two pushdown stores by one tape
• On two-tape real-time computation and queues
• On the simulation of many storage heads by one

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 Q4077448)