One-tape, off-line Turing machine computations

Cited in

(83)

Theory of one-tape linear-time Turing machines
Complexity lower bounds for machine computing models
On the structure of one-tape nondeterministic Turing machine time hierarchy
On pebble automata
On the bit complexity of distributed computations in a ring with a leader
Hierarchies of one-way multihead automata languages
Complexity, combinatorial group theory and the language of palutators
Data encodings and their costs
On alternation
Complexity of algorithms and computations
Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations
The complexity of matrix transposition on one-tape off-line Turing machines with output tape
The halting problem for linear Turing assemblers
On the sequential nature of functions
Parallel turing machines with one-head control units and cellular automata
Two tapes versus one for off-line Turing machines
An optimal lower bound for nonregular languages
New lower bounds for element distinctness on a one-tape Turing machine
Deterministic multitape automata computations
Palindrome recognition using a multidimensional tape.
Bounds for the Element Distinctness Problem on one-tape Turing machines
Descriptional complexity of limited automata
On the descriptional complexity of stateless deterministic ordered restarting automata
The speed of copying on one-tape off-line turing machines
Deterministic Turing machines in the range between real-time and linear-time.
Verifying whether one-tape Turing machines run in linear time
Undecidability of the speed positiveness problem in reversible and complete Turing machines
Converting nondeterministic two-way automata into small deterministic linear-time machines
Multitape one-way nonwriting automata
k-Band-Simulation von k-Kopf-Turing-Maschinen. (k-tape simulation of k- head Turing machines)
Time-bounded grammars and their languages
On the extension of Gladkij's theorem and the hierarchies of languages
A time lower bound for satisfiability
A computation model with automatic functions and relations as primitive operations
Alternating demon space is closed under complement and other simulations for sublogarithmic space
A hierarchy of fast reversible Turing machines
Reversible limited automata
THE ROLES OF ADVICE TO ONE-TAPE LINEAR-TIME TURING MACHINES AND FINITE AUTOMATA
TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
ASMs and operational algorithmic completeness of lambda calculus
Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem
Two-way automata and length-preserving homomorphisms
Verifying time complexity of Turing machines
New time hierarchy results for deterministic TMS
On languages accepted with simultaneous complexity bounds and their ranking problem
Alternating space is closed under complement and other simulations for sublogarithmic space
Limited automata and regular languages
Complexity of nondeterministic multitape computations based on crossing sequences
Automata with cyclic move operations for picture languages
Two-dimensional Sgraffito automata
State-complexity of finite-state devices, state compressibility and incompressibility
Restarting tiling automata
On simulation cost of unary limited automata
scientific article; zbMATH DE number 3288590 (Why is no real title available?)
On the Minimum Computation Time of Functions
scientific article; zbMATH DE number 3305096 (Why is no real title available?)
Klassifikation der Zufallsgesetze nach Komplexit�t und Ordnung
Computational complexity of random access stored program machines
On restricted turing computability
Subrecursiveness: Machine-independent notions of computability in restricted time and storage
Recognizing picture languages by reductions to string languages
Descriptional complexity of iterated uniform finite-state transducers
Linear-time limited automata
Some remarks about the efficiency of polyautomata
Weight-reducing Turing machines
scientific article; zbMATH DE number 7770052 (Why is no real title available?)
Immunity and pseudorandomness of context-free languages
One-tape Turing machine and branching program lower bounds for MCSP
On the power of several queues
Explicit time and space efficient encoders exist only with random access
Power of counting by nonuniform families of polynomial-size finite automata
The word problem and growth of groups
Nondeterminism and the clique problem
Lower bounds on the running time of two-way quantum finite automata and sublogarithmic-space quantum Turing machines
Differentially oblivious Turing machines
One-tape Turing machine and branching program lower bounds for MCSP
A formalization of multi-tape Turing machines
Two-way pebble transducers for partial functions and their composition
Deterministic ordered restarting automata for picture languages
The complexity of matrix transposition on one-tape off-line Turing machines
A linear-time simulation of deterministic \(d\)-limited automata
The difference between one tape and two tapes: With respect to reversal complexity

This page was built for publication: One-tape, off-line Turing machine computations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5638291)