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

Abstract

We present three simulations: a simulation of an alternating Turning 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).

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1986
Accession Number
ADA162661

Entities

People

  • Jerry L. Trahan

Organizations

  • University of Illinois Urbana–Champaign

Tags

DTIC Thesaurus Topics

  • Automata
  • Automata Theory
  • Computational Complexity
  • Computations
  • Computer Science
  • Contracts
  • Engineering
  • Illinois
  • Language
  • Machines
  • Parallel Computing
  • Parallel Processing
  • Simulations
  • Theoretical Computer Science
  • Trees (Data Structures)
  • Two Dimensional
  • Universities

Readers

  • Materials Science.
  • Mathematical Modeling and Probability Theory.
  • Parallel and Distributed Computing.