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