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 (75)
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
This page was built for publication: One-tape, off-line Turing machine computations
