One-tape, off-line Turing machine computations
From MaRDI portal
Publication:5638291
DOI10.1016/S0019-9958(65)90399-2zbMath0231.02048OpenAlexW2029872977MaRDI QIDQ5638291
Publication date: 1966
Published in: Information and Control (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0019-9958(65)90399-2
Related Items
An optimal lower bound for nonregular languages, On the structure of one-tape nondeterministic Turing machine time hierarchy, New lower bounds for element distinctness on a one-tape Turing machine, A linear-time simulation of deterministic \(d\)-limited automata, State-complexity of finite-state devices, state compressibility and incompressibility, On pebble automata, On the bit complexity of distributed computations in a ring with a leader, Hierarchies of one-way multihead automata languages, [https://portal.mardi4nfdi.de/wiki/Publication:5587565 Klassifikation der Zufallsgesetze nach Komplexit�t und Ordnung], Complexity, combinatorial group theory and the language of palutators, Some remarks about the efficiency of polyautomata, Computational complexity of random access stored program machines, On restricted turing computability, Reversible Limited Automata, Subrecursiveness: Machine-independent notions of computability in restricted time and storage, A computation model with automatic functions and relations as primitive operations, New time hierarchy results for deterministic TMS, On languages accepted with simultaneous complexity bounds and their ranking problem, Weight-reducing Turing machines, Deterministic multitape automata computations, Data encodings and their costs, On alternation, Unnamed Item, Palindrome recognition using a multidimensional tape., Complexity of algorithms and computations, On the Minimum Computation Time of Functions, Descriptional complexity of limited automata, On the descriptional complexity of stateless deterministic ordered restarting automata, TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE, Unnamed Item, Two-way automata and length-preserving homomorphisms, The difference between one tape and two tapes: With respect to reversal complexity, Immunity and pseudorandomness of context-free languages, Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem, Unnamed Item, Unnamed Item, Verifying time complexity of Turing machines, RESTARTING TILING AUTOMATA, Alternating space is closed under complement and other simulations for sublogarithmic space, On the power of several queues, Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations, Linear-time limited automata, The complexity of matrix transposition on one-tape off-line Turing machines with output tape, LIMITED AUTOMATA AND REGULAR LANGUAGES, Verifying whether one-tape Turing machines run in linear time, ASMs and Operational Algorithmic Completeness of Lambda Calculus, The halting problem for linear Turing assemblers, On the sequential nature of functions, Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines, Complexity of Nondeterministic Multitape Computations Based on Crossing Sequences, THE ROLES OF ADVICE TO ONE-TAPE LINEAR-TIME TURING MACHINES AND FINITE AUTOMATA, Undecidability of the speed positiveness problem in reversible and complete Turing machines, Descriptional complexity of iterated uniform finite-state transducers, A formalization of multi-tape Turing machines, Multitape one-way nonwriting automata, Two-way pebble transducers for partial functions and their composition, Deterministic ordered restarting automata for picture languages, Alternating Demon Space Is Closed Under Complement and Other Simulations for Sublogarithmic Space, Automata with cyclic move operations for picture languages, A Hierarchy of Fast Reversible Turing Machines, k-Band-Simulation von k-Kopf-Turing-Maschinen. (k-tape simulation of k- head Turing machines), Time-bounded grammars and their languages, The speed of copying on one-tape off-line turing machines, Parallel turing machines with one-head control units and cellular automata, On the extension of Gladkij's theorem and the hierarchies of languages, Theory of one-tape linear-time Turing machines, On Simulation Cost of Unary Limited Automata, Two-dimensional Sgraffito automata, Complexity lower bounds for machine computing models, Deterministic Turing machines in the range between real-time and linear-time., A time lower bound for satisfiability, Converting nondeterministic two-way automata into small deterministic linear-time machines, The complexity of matrix transposition on one-tape off-line Turing machines, Bounds for the Element Distinctness Problem on one-tape Turing machines, Two tapes versus one for off-line Turing machines
