On multiply-exponential write-once Turing machines

الأصل · EN

In this work we analyze the multiply-exponential complexity classes for write-once Turing machines, i.e. machines that can write to a given tape cell at most once. We show that k-DExpWOSpace = k-DExpWOTime = k-ExpTime and the nondeterministic counterpart. For alternating machines we show that k-AExpWOTime = k-AExpTime = k-1-ExpSpace.