Weight-reducing Turing machines

DOI10.1016/J.IC.2023.105030arXiv2103.05486MaRDI QIDQ6040666

Daniel Průša, Giovanni Pighizzini, Luca Prigioniero, Bruno Guillon

Publication date: 19 May 2023

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2103.05486

zbMATH Keywords

descriptional complexityone-tape Turing machinesHennie machines

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Verifying time complexity of Turing machines
• Theory of one-tape linear-time Turing machines
• An NP-complete language accepted in linear time by a one-tape Turing machine
• Two-way automata and one-tape machines - read only versus linear time
• Converting nondeterministic two-way automata into small deterministic linear-time machines
• On Non-Computable Functions
• Nondeterminism and the size of two way finite automata
• Weight-Reducing Hennie Machines and Their Descriptional Complexity
• Computational Complexity of One-Tape Turing Machine Computations
• Deterministic context-sensitive languages: Part II
• Classes of languages and linear-bounded automata
• One-tape, off-line Turing machine computations

This page was built for publication: Weight-reducing Turing machines