Array Automata and Array Grammars

Abstract

It is shown that grammars that rewrite arrays are equivalent to Turing machines having array "tapes'" and that "monotonic" array grammars (in which arrays never shrink in the course of a derivation) are equivalent to "array-bounded" machines. It is also shown that two alternative definitions of 'array-bounded' are in fact equivalent.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1970
Accession Number
AD0740142

Entities

People

  • Azriel Rosenfeld
  • David L. Milgram

Organizations

  • University of Maryland

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Abstracts
  • Automata
  • Boundaries
  • Computer Science
  • Computers
  • Displacement
  • Grammars
  • Information Systems
  • Language
  • Machines
  • Maryland
  • Simulations
  • Simulators
  • Terminals
  • Universities
  • Vocabulary

Fields of Study

  • Engineering

Readers

  • Computational Linguistics
  • Integrated Circuit Design and Technology.
  • Mathematical Modeling and Probability Theory.