scientific article; zbMATH DE number 88942

MaRDI QIDQ4016519zbMATH OpenFDO

Authors Tao Jiang

Publication date 16 January 1993

zbMATH Keywords

1-tape alternating Turing machinerecursive functionrecursively enumerable setregular languages

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Recursively (computably) enumerable sets and degrees (03D25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On the complexity of 1-tape ATMs and off-line 1-tape ATMs running in constant reversals
• On the power of 1-tape off-line ATMs running in a bounded number of reversals
• Alternating multicounter machines with constant number of reversals
• On reversal bounded alternating Turing machines
• Reversal Complexity Classes for Alternating Turing Machines

Cited in

(5)

• Reversal Complexity Classes for Alternating Turing Machines
• scientific article; zbMATH DE number 1222596 (Why is no real title available?)
• On the power of 1-tape off-line ATMs running in a bounded number of reversals
• The complexity of matrix transposition on one-tape off-line Turing machines
• On the complexity of 1-tape ATMs and off-line 1-tape ATMs running in constant reversals

This page was built for publication:

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