Simulations Among Multidimensional Iterative Arrays, Iterative Tree Automata, and Alternating Turning Machines

摘要

We present three simulations: a simulation of an alternating Turing machine (ATM) operating in time T(n) by an iterative tree automation (IITA), a simulation of a d-dimensional iterative array (dIA) operating in time T(n) by an ATM and a simulation of an ITA operating in time T(n) by an ATM. The first two improve previously known results. The first implies the simulation of a nondeterministic Turing machine by an ITA in time O(T(n)) of Culik and Yu(1984)sub d + 1. The second is stronger than the simulation of a dIA by an ATM in time O((T(n)) /logT(n)) of Seiferas (1977) and Dymond and Tompa (1985). Keywords: iterative array, alternating turning machine, parallel computational, simulation, computational complexity theory. (Thesis).