A relationship between nondeterministic turing machines and 1-inkdot turing machines with small space

DOI10.1016/0020-0190(92)90205-AzbMath0789.68053MaRDI QIDQ1199887

Katsushi Inoue, Itsuo Takanami, Akira Ito

Publication date: 17 January 1993

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

computational complexitynondeterministic Turing machinesspace bounded computations1-inkdot Turing machines

Mathematics Subject Classification ID

Related Items (3)

On 1-inkdot alternating Turing machines with small space ⋮ A note on multi-inkdot nondeterministic Turing machines with small space ⋮ Alternation for sublogarithmic space-bounded alternating pushdown automata

Cites Work

• Space bounded computations: Review and new separation results
• Alternation
• Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A relationship between nondeterministic turing machines and 1-inkdot turing machines with small space