scientific article; zbMATH DE number 3495593

MaRDI QIDQ4077448zbMATH OpenFDO

Authors Stål Aanderaa

Publication date 1974

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
• QRT FIFO automata, breadth-first grammars and their relations
• Realtime subshifts
• 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)