MULTITAPE AFA

Abstract

In previous papers the notion of a family of one-way nondeterministic devices was abstracted and studied extensively. A natural extension of a device with a particular type of storage tape is a multitape (storage) device, each tape of the same kind. In most familiar cases--counter, pushdown, stack--adding a second storage tape increases the power of the device to that of a Turing acceptor. By suitable restrictions on multitape devices, families can be obtained so that the associated languages do not include all recursively enumerable sets. The purpose of the paper is to abstract the notion of an 'abstract family of multitape acceptors' (abbreviated 'multitape AFA'), each storage tape not necessarily of the same kind, and examine the family of associated languages.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 02, 1969
Accession Number
AD0689821

Entities

People

  • Seymour Ginsburg
  • Sheila Greibach

Organizations

  • System Development Corporation

Tags

Communities of Interest

  • Space

DTIC Thesaurus Topics

  • Abstracts
  • Air Force
  • Automata
  • Computations
  • Computer Languages
  • Computer Science
  • Computers
  • Contracts
  • Formal Languages
  • Grammars
  • Language
  • Machines
  • Mathematics
  • Scientific Research
  • Sequences
  • Set Theory
  • Theorems

Readers

  • Mathematical Modeling and Probability Theory.