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