Real time computation
From MaRDI portal
Publication:2526723
DOI10.1007/BF02759719zbMath0156.25603MaRDI QIDQ2526723
Publication date: 1963
Published in: Israel Journal of Mathematics (Search for Journal in Brave)
Related Items
COMBING NILPOTENT AND POLYCYCLIC GROUPS, WORD-HYPERBOLIC GROUPS HAVE REAL-TIME WORD PROBLEM, Unnamed Item, On the Computational Complexity of Algorithms, Unnamed Item, The theory of languages, Counter machines and counter languages, The theory of languages, A note on dense and nondense families of complexity classes, Computational complexity of random access stored program machines, On the Minimum Computation Time of Functions, On the power of several queues, On the power of real-time two-way multihead finite automata with jumps, On two-tape real-time computation and queues, Milking the Aanderaa argument, Complexity lower bounds for machine computing models, 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, 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, Complexity of algorithms and computations, An information-theoretic approach to time bounds for on-line computation, The halting problem for linear Turing assemblers, Recognition of a self-crossing of a plane trajectory by a Kolmogorov algorithm, Palindrome recognition in real time by a multitape Turing machine, Two tapes versus one for off-line Turing machines, Undecidability and chaos in word-coded symbolic dynamics, On the simulation of many storage heads by one, A theoretical analysis of the effects of amygdalectomy and of organismi motivation, Über einen Automaten mit Pufferspeicherung, Time-restricted sequence generation, Complexity problems in real time languages, On non-determinacy in simple computing devices, Tape-reversal bounded Turing machine computations, Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
Cites Work
