Accession Number : AD0697757

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

Descriptive Note : Scientific rept.,

Corporate Author : HARVARD UNIV CAMBRIDGE MASS DIV OF ENGINEERING AND APPLIED PHYSICS

Personal Author(s) : Book,Ronald V. ; Greibach,Sheila A.

Report Date : OCT 1969

Pagination or Media Count : 11

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)

Descriptors :   (*COMPUTATIONAL LINGUISTICS, *AUTOMATA), CONTEXT FREE GRAMMARS, PROGRAMMING LANGUAGES

Subject Categories : Linguistics
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE