Accession Number:

ADA162661

Title:

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

Descriptive Note:

Master's thesis,

Corporate Author:

ILLINOIS UNIV AT URBANA COORDINATED SCIENCE LAB

Personal Author(s):

Report Date:

1986-01-01

Pagination or Media Count:

42.0

Abstract:

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.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE