Real time computation
From MaRDI portal
Publication:2526723
DOI10.1007/BF02759719zbMath0156.25603OpenAlexW2090627896MaRDI QIDQ2526723
Publication date: 1963
Published in: Israel Journal of Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02759719
Related Items
The theory of languages, Counter machines and counter languages, WORD-HYPERBOLIC GROUPS HAVE REAL-TIME WORD PROBLEM, On the structure of one-tape nondeterministic Turing machine time hierarchy, Undecidability and chaos in word-coded symbolic dynamics, On the simulation of many storage heads by one, The theory of languages, 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, Monitoring hyperproperties with circuits, A note on dense and nondense families of complexity classes, Computational complexity of random access stored program machines, A computation model with automatic functions and relations as primitive operations, Complexity of algorithms and computations, On the Minimum Computation Time of Functions, An information-theoretic approach to time bounds for on-line computation, Milking the Aanderaa argument, Unnamed Item, On the Computational Complexity of Algorithms, On the power of several queues, TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES, The halting problem for linear Turing assemblers, Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines, Recognition of a self-crossing of a plane trajectory by a Kolmogorov algorithm, Palindrome recognition in real time by a multitape Turing machine, Unnamed Item, 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, On the power of real-time two-way multihead finite automata with jumps, Complexity lower bounds for machine computing models, 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, COMBING NILPOTENT AND POLYCYCLIC GROUPS, Two tapes versus one for off-line Turing machines
Cites Work
