Simulations Among Multidimensional Iterative Arrays, Iterative Tree Automata, and Alternating Turning Machines.
ILLINOIS UNIV AT URBANA COORDINATED SCIENCE LAB
Pagination or Media Count:
We present three simulations a simulation of an alternating Turning machine ATM operating in time Tn by an iterative tree automation IITA, a simulation of a d-dimensional iterative array dIA operating in time Tn by an ATM and a simulation of an ITA operating in time Tn 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 OTn of Culik and Yu1984sub d 1. The second is stronger than the simulation of a dIA by an ATM in time OTn logTn of Seiferas 1977 and Dymond and Tompa 1985. Keywords iterative array, alternating turning machine, parallel computational, simulation, computational complexity theory. Thesis.
- Numerical Mathematics