scientific article; zbMATH DE number 3495593
From MaRDI portal
Publication:4077448
zbMath0316.68029MaRDI QIDQ4077448
Publication date: 1974
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Turing machines and related notions (03D10)
Related Items
On the simulation of many storage heads by one, Tape versus queue and stacks: The lower bounds, Alternating real-time computations, Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time, Deterministic realization of nondeterministic computations with a low measure of nondeterminism, An information-theoretic approach to time bounds for on-line computation, Possibilities of various types of alternating automata, Milking the Aanderaa argument, QRT FIFO automata, breadth-first grammars and their relations, On the power of several queues, \(k\) versus \(k+1\) index registers and modifiable versus non-modifiable programs, Real-time computations with restricted nondeterminism, Realtime subshifts, On heads versus tapes, 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
