A NOTE ON LANGUAGES ACCEPTED BY TIME-BOUNDED NONDETERMINISTIC MACHINES.

Abstract

For any time bound, the family of languages accepted by nondeterministic multitape Turing machines which operate within that time bound is characterized as the appropriate homomorphic image of the quasi-realtime languages. From this characterization it is seen that for acceptance by time-bounded nondeterministic Turing machines, it is sufficient to operate with just two storage tapes, one a stack and one a pushdown store. (Author)

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1969
Accession Number
AD0697757

Entities

People

  • Ronald V. Book
  • Sheila A. Greibach

Organizations

  • Harvard University

Tags

DTIC Thesaurus Topics

  • Automata
  • Language

Readers

  • Computer Science/Computer Engineering/Data Science/Digital Signal Processing.
  • Mathematical Modeling and Probability Theory.